1

私はフィボナッチ級数を再帰的に行う方法を知っています。それは非常に簡単です:

def F(n):
  if n == 1 or n == 2:
    return 1
  else:
    return k * F(n-2) + F(n - 1)

ただし、同じ値を何度も計算する必要があるため、これは非常に非効率的であることはわかっています。これを回避する方法は、何らかの形で値を保存することです。20 番目の値が必要だとします。F(13) が何であるかを計算したら、その値を保存して直接呼び出すことができます。すべての再帰レベルを調べて同じ答えを得る必要はありません。

辞書は、この問題に対する明白な解決策です。ただし、辞書に関する私の答えは機能しません。

U = {1:1, 2:1}
def F(n):
  global U
  if n in U:
    return U[n]
  else:
    U[n] = F(n - 2) + F(n - 1)

このコードが実行されたら、U[n] を表示するだけです。

ロジックを何度も実行しましたが、すべて問題ないように見えますが、次のエラーが発生し続けます。

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

a がどのように返されるべきかはわかりませんNoneが、問題の原因となっている辞書に関する何らかのニュアンスが欠けている可能性があることは認めます。

4

4 に答える 4

1

句にreturnステートメントがありません。else

def F(n):
  global U
  if n in U:
    return U[n]
  else:
    U[n] = F(n - 2) + F(n - 1)
    return U[n]

または簡略化：

def F(n):
  if n not in U:
    U[n] = F(n - 2) + F(n - 1)
  return U[n]

(globalは必要ありません。)

于 2013-05-17T03:11:33.793 に答える
0
  • が U にないときnは、また戻る必要があります。U[n]

ただ：

U = {1:1, 2:1}
def F(n):
    global U
    if n in U:
        return U[n]
    else:
        U[n] = F(n - 2) + F(n - 1)
        return U[n]
  • の場合efficient:
    • 一度やりたい場合、2番目の方法はスペースを犠牲にして時間を稼ぐことです。実際の開発環境ではどちらが優れているかわかりません。
    • U[n] を何度も取得したい場合は、a で保存するU方がよい

したがって、値を保存したい場合は、次のようになります。

U = {1:1, 2:1}
def F(n):
    for i in range(3, n+1):
        U[i] = U[i - 2] + U[i - 1]
    return U

fb = F(10)

print fb[3]
print fb[5]
print fb[10]
于 2013-05-17T03:35:09.357 に答える
0

メモ化を行う必要がある場合は、functools.lru_cache (>= python 3.2) を使用できます。関数を変更して追加のデータ構造を作成する必要がないことを除いて、まさにあなたが望むことを行います。

import functools

MAX_CACHE = 10**7

@functools.lru_cache(MAX_CACHE)
def F(n):
    if n == 1 or n == 2:
        return 1
    else:
        return F(n-2) + F(n - 1)

MAX_CACHE記憶する最新の呼び出しの数です。

于 2016-11-23T16:22:12.600 に答える
0

変更可能なデフォルトが一度だけ初期化されるという事実を使用した簡単な方法

def F(n, U={1: 1, 2: 1}):
  if n not in U:
    U[n] = F(n - 2) + F(n - 1)
  return U[n]

これによりU、グローバル名前空間にある必要がなくなります

于 2013-05-17T03:28:21.630 に答える