python - 如何编写斐波那契数列？

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 序列论坛，但我也迷路了。

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ⁿ) 时间。

在我链接到你的网站上继续，你会看到这个(在 wolfram 上):

这个很容易实现，并且在 Python 中计算非常非常快:

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

另一种方法是遵循定义(来自 wikipedia):

The first number of the sequence is 0, the second number is 1, and each subsequent number is equal to the sum of the previous two numbers of the sequence itself, yielding the sequence 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。

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

假设现在您编写了一个 f(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 祝你好运，玩得开心!