如何编写斐波那契数列？

Question

我最初对程序进行了错误的编码。我没有返回一个范围之间的斐波那契数（即 startNumber 1，endNumber 20 应该 = 仅那些介于 1 和 20 之间的数字），而是为程序编写了显示范围之间的所有斐波那契数（即 startNumber 1，endNumber 20显示 = 前 20 个斐波那契数）。我以为我有一个万无一失的代码。我也不明白为什么会这样。

 startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

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

print map(fib, range(startNumber, endNumber))

有人在我的第二部分中指出（由于重复而被关闭 - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii ）我需要使用 while 循环通过生成器传递 startNumber 和 endNumber。有人可以指点我如何做到这一点吗？欢迎任何帮助。

---

我是一名学习程序员，我遇到了一些混乱。我被要求编写一个程序，该程序将通过用户输入的开始数字和结束数字来计算和显示斐波那契数列（即 startNumber = 20 endNumber = 100，它将只显示该范围之间的数字）。诀窍是包容性地使用它（我不知道如何在 Python 中做到这一点？-我假设这意味着使用包容性范围？）。

到目前为止，我没有实际的编码，而是：

• 将 Fib 序列公式写入无穷大
• 仅从 Fib 序列显示 startNumber 到 endNumber。

我不知道从哪里开始，我正在寻求想法或洞察如何写这个。我也尝试过编写 Fib 序列论坛，但我也迷失了方向。

原文由 SD. 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在 wikipedia 和 wolfram 上有很多关于斐波那契数列的信息。比您可能需要的多得多。无论如何，学习如何使用这些资源来找到（如果可能的话，尽快）你需要的东西是一件好事。

将 Fib 序列公式写入无穷大

在数学中，它以递归形式给出：

在编程中， 无限 是不存在的。您可以使用递归形式直接在您的语言中翻译数学形式，例如在 Python 中它变为：

 def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

用你最喜欢的语言试试看，随着 n 变大，这种形式需要 很多 时间。事实上，这是 O(2 n ) 的时间。

继续我链接到你的网站，你会看到这个（在 wolfram 上）：

这个在 Python 中很容易实现并且计算速度非常非常快：

 from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

另一种方法是遵循定义（来自 维基百科）：

序列的第一个数字是 0，第二个数字是 1，随后的每个数字都等于序列本身的前两个数字之和，产生序列 0、1、1、2、3、5、8 ， ETC。

如果您的语言支持迭代器，您可以执行以下操作：

 def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

仅从 Fib 序列显示 startNumber 到 endNumber。

一旦您知道如何生成斐波那契数列，您只需要循环遍历这些数字并检查它们是否验证了给定的条件。

假设现在您编写了 af(n)，它返回斐波那契数列的第 n 项（如使用 sqrt(5) 的项）

在大多数语言中，您可以执行以下操作：

 def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

在 python 中，我会使用迭代器形式并使用：

 def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

我的提示是 学会阅读 你需要的东西。 Project Euler（谷歌）会训练你这样做：P祝你好运，玩得开心！

原文由 Andrea Ambu 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

斐波那契数列可以编码如下。

 n = int(input('Length: '))

def fibonacci(n):
    a, b = 0, 1
    for i in range(n):
        print(a)
        a, b = b, a+b

fibonacci(n)

输出：

 Length: 5
0
1
1
2
3

原文由 Randil Tennakoon 发布，翻译遵循 CC BY-SA 4.0 许可协议