1

Python の場合:

def g(n):  
    if n <=3:        
        return n   
    return g(n-1) + 2 * g(n-2) + 3 * g(n-3)

この関数が何をしているのかは理解していますが、反復させる方法がわかりません。助けてください。可能であれば、問題を完全に理解できるように説明を含めてください。

4

4 に答える 4

8

これはフィボナッチ数列の問題に似ており、反復的に実装するのは簡単ではありません。宿題のようにも見えるので、フィボナッチ反復を取得する手順を投稿します。それを問題に適用できるはずです。

ご存じない方のために説明すると、フィボナッチは次のように定義されています。

def fib(n):
    if n <= 1:  # technically, this is not 100% correct, but it's fine for n>=0
        return n
    return fib(n-1) + fib(n-2)

それでは分析してみましょうfib(n)。n <= 1まず、 との 2 つの異なるケースがあることがわかりますnot n <= 1。n <= 1にfib(n)は依存関係がないため、次のように評価できます。

def fib_iter(n):
    if n <= 1:
        return n

次に、他のケースをカバーする必要があります。まず、依存関係の分析を行いましょう。には何が必要fib(n)ですn > 1か? fib(n-1)とを呼び出しますfib(n-2)。反復言語では、これらは前の 2 つの値になります。したがって、明らかに、それらを追跡する必要があります。その 1 つの 2 つの些細なケースから始めます。

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1

これがかなり明白であることを願っています。次に、再帰的アプローチで解決された順序で関数を解決します。再帰を巻き戻して関数を分析すると、評価される最初の非自明な値はもちろん であることがわかりますfib(2)。その後fib(3)、 に到達するまで続きますn。再帰的なアプローチのため、いくつかの値が複数回評価されますが、反復的なアプローチでは必要ありません。値が加算され、次のコードが得られます。

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for i in xrange(2, n+1):
        curr = prev1 + prev2        # calculate fib(i)
        prev1, prev2 = prev2, curr  # shift previous value cache

欠けているのは戻り値だけです。これはcurrループが終了した時点のものです。xrange(2, n+1)事前に確認するようにn <= 1、ループは少なくとも 1 回実行さcurrれるため、ループの外側で定義されます。

def fib_iter(n):
    if n <= 1:
        return n
    prev1, prev2 = 0, 1
    for i in xrange(2, n+1):
        curr = prev1 + prev2
        prev1, prev2 = prev2, curr
    return curr

(これは私の最初の宿題の答えです。SO コミュニティは、私が甘やかしすぎたらもっとうまくできたかもしれないというフィードバックをくれるかもしれません)

于 2012-06-29T16:58:43.197 に答える
4 
def g(n):
    if n <= 3:
        return n
    a, b, c = 1, 2, 3
    for i in range(3, n):
        a, b, c = b, c, (a * 3 + b * 2 + c)
    return c
于 2012-06-29T18:00:43.253 に答える
3

再帰関数は次のように読み取ることができます

To find the value of g(30), find the value of g(29), g(28), and g(27)
  To find the value of g(29), find the value of g(28), g(27), and g(26)
    To find the value of g(28), find the value of g(27), g(26), and g(25)
      ...
        (repeat until all sub-finds have completed)

反復関数はもう一方の端から始まります。

I know the values of g(1), g(2), and g(3) -> calculate g(4)
I know the values of g(2), g(3), and g(4) -> calculate g(5)
I know the values of g(3), g(4), and g(5) -> calculate g(6)
...
(repeat until the desired g(n) is reached)
于 2012-06-29T18:25:41.507 に答える
1

これは楽しすぎて解けませんでした...

def g(n, *, _cache=[0, 1, 2, 3]):
    for _ in range(n - len(_cache) + 1):
        _cache.append(sum(i * _cache[-i] for i in (1, 2, 3)))
    return _cache[n]

うまくいけば、あなたはすでに解決策を見つけているでしょう。

于 2012-06-29T17:33:13.530 に答える