0

合計を求める必要がある一連の数値があります。最初の反復操作の値は 1 で、2 番目は 20 です。その後のすべての反復では、式 n * (n + 1) / 2 で前の結果が使用されるため、3 番目の反復では i03 = 20 * (20 + 1) / 2、そして 4 番目の i04 = i03 * (i03 + 1) / 2. これは、i20 = i19 * (i19 + 1) / 2 の 20 回目の反復まで続きます。メモ化を使用してこれを実行したいと考えています。これは私のコードです:

def outFun():
    def sumFun(squares, total = 0, CONST = 20):
        if squares > 2:
            total = sumFun(squares - 1) * int((sumFun(squares - 1) + 1) / 2)
        elif not squares - 2:
            total = CONST
        return total

    return 1 + sumFun(20)

私は何を間違っていますか？

4

2 に答える 2

1

これが私があなたの問題をどのように理解するかです:x_n = x_{n-1} * (x_{n-1} + 1)/2再帰ベースが定義された式がありますx_1 = 20(またはx_2 = 20? あなたの説明からは明らかではありません)。再帰を解決する最も効率的な方法は、ボトムアップ アプローチであり、 で開始しx_1、次に を計算するx_2などです。代わりに、動的プログラミング/記憶を使用することもできます。

mem={}
def f(x):
    if x == 1:   # base case
        return 20
    if not x in mem:    # if we did not calculate it before - calculate
        mem[x] = f(x-1) * (f(x-1) +1) / 2
    return mem[x]   # otherwise return it

print f(1)    
print f(2)
print f(3)

版画

20
210
22155

f(20)印刷するには少し大きいので、桁数を印刷します。

print "number of digits: %s" % len(str(f(20)))

number of digits: 530115

デスクトップでコードを実行するのに約 9 秒かかりました。

import timeit
mem={}
print "Execution time: %s" % timeit.Timer("len(str(f(20)))",
                            setup = "from __main__ import f").timeit(1)
于 2013-02-21T02:50:27.920 に答える
1

あなたが呼んでいる

sumFun(squares - 1)

二回！

結果を格納する変数を導入してみませんか? 何かのようなもの：

if squares > 2:
    nextResult = sumFun(squares - 1)
    total = nextResult * ((nextResult + 1) / 2)
于 2013-02-20T20:03:41.927 に答える