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'

每当我尝试大于 3 的数字时。我不知道None应该如何返回 a，但我承认我可能遗漏了导致问题的字典的某种细微差别。

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

使用可变默认值仅初始化一次这一事实的简单方法

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 回答
0
  • n不在U的时候，你也应该返回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：
    • 如果你想做一次，你的第二种方法是牺牲空间，争取时间，我不知道在真实的开发环境中哪个更好。
    • 如果您想多次获得 U[n]，U则存储 a 更好

因此，如果您想存储该值，则可能是：

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 回答