找出第一个大于 100 万的斐波那契数

Question

目前正在学习一门编程课程，并作为一项任务找到了超过一百万的第一个斐波那契数，但我在寻找具体数字时遇到了一些麻烦。我还应该在 n:th 数达到 100 万时找到它的索引。我对编码很陌生，但这是我到目前为止想出的，只是很难弄清楚如何实际计算数字是多少。

我猜你会用 while 循环关闭 for-while，但还没有弄清楚如何让它全部工作。

提前致谢:)

def fib_seq(n):
    if n <= 2:
       return 1
    return fib_seq(n-1) + fib_seq(n-2)


lst = []
for i in range(1, 20):
    lst.append(i)
    print(fib_seq(i), lst)

Answer 1

几点：

您不需要构建列表。你只被要求 return 一个指数和相应的斐波那契数。
Fibonnacci 的递归算法不是最佳实践，除非您使用一些记忆。否则必须一遍又一遍地重新计算相同的数字。请改用迭代方法。

这是它的样子：

def fib(atleast):
    a = 0
    b = 1
    i = 1
    while b < atleast:
        a, b = b, a+b
        i += 1
    return i, b


print(fib(1000000)) # (31, 1346269)

Answer 2

如果您需要通过一些递归查找来执行此操作，您应该尽量避免在每次迭代中调用两次递归。这是复杂性爆炸式增长的经典示例。一种方法是记住已经计算出的结果。另一种是使用函数参数来维护状态。例如，这将提供答案并且只调用该函数 32 次：

def findIndex(v, prev = 0, current = 1, index = 0):
    if v < prev:
        return (prev, index)
    return findIndex(v, current, prev+current, index + 1 )


findIndex(1000000)  # (1346269, 31)

找出第一个大于 100 万的斐波那契数

Find the first fibonacci number above 1 million

python

fibonacci

python-3.x