如何写出斐波那契数列？

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。有人能告诉我怎么做吗？欢迎任何帮助。

---

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

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

• 将Fib序列公式写到无穷大
• 仅从Fib序列显示开始编号到结束编号。

我不知道从哪里开始，我想知道如何写这篇文章。我也试过为umla写Fib序列，但我也迷路了。

Answer 1

Fibonacci序列的高效Pythonic发生器

我在试图得到这个序列中最短的Pythonic代时发现了这个问题（后来意识到我在aPython Enhancement Proposal中看到过类似的一个），我没有注意到其他人提出我的具体解决方案（虽然最上面的答案很接近，但仍然不太优雅），所以这里有一些评论描述了第一次迭代，因为我认为这可能有助于读者理解：

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

使用方法：

for index, fibonacci_number in zip(range(10), fib()):
     print('{i:3}: {f:3}'.format(i=index, f=fibonacci_number))

印刷品：

  0:   0
  1:   1
  2:   1
  3:   2
  4:   3
  5:   5
  6:   8
  7:  13
  8:  21
  9:  34
 10:  55

（出于归因的目的，我最近注意到Python文档中有一个关于模块的similar implementation，甚至使用了变量a和b，我现在还记得在编写这个答案之前看到过这个变量）。但我认为这个答案证明了语言的更好使用。）

递归定义的实现

Online Encyclopedia of Integer Sequences递归地将Fibonacci序列定义为

F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1

在Python中递归地简洁地定义它可以如下所示：

def rec_fib(n):
    '''inefficient recursive function as defined, returns Fibonacci number'''
    if n > 1:
        return rec_fib(n-1) + rec_fib(n-2)
    return n

但是对于大于30的数字来说，数学定义的这种精确表示是非常低效的，因为每个被计算的数字也必须计算它下面的每个数字。您可以使用以下方法演示其速度有多慢：

for i in range(40):
    print(i, rec_fib(i))

记忆递归提高效率

可以记住它以提高速度（此示例利用了这样一个事实，即每次调用函数时，默认关键字参数都是同一个对象，但通常不会使用可变默认参数，原因正是这样的）：

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

你会发现备忘录版本更快，而且在你想起来喝咖啡之前，会很快超过你的最大递归深度。通过执行以下操作，您可以看到它在视觉上的速度有多快：

for i in range(40):
    print(i, mem_fib(i))

（看起来我们可以执行以下操作，但实际上它不允许我们利用缓存，因为它在调用setdefault之前调用自己。）

def mem_fib(n, _cache={}):
    '''don't do this'''
    if n > 1:  
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

递归定义的生成器：

在我学习Haskell的过程中，我在Haskell中遇到了这个实现：

fib@(0:tfib) = 0:1: zipWith (+) fib tfib

我认为目前在Python中最接近这一点的是：

from itertools import tee

def fib():
    yield 0
    yield 1
    # tee required, else with two fib()'s algorithm becomes quadratic
    f, tf = tee(fib()) 
    next(tf)
    for a, b in zip(f, tf):
        yield a + b

这证明了这一点：

[f for _, f in zip(range(999), fib())]

不过，它只能达到递归限制。通常是1000，而Haskell版本可以达到百万分之一百，尽管它使用了我笔记本电脑的所有8GB内存：

> length $ take 100000000 fib 
100000000

Answer 2

为什么不简单地做以下事情呢？

x = [1,1]
for i in range(2, 10):  
    x.append(x[-1] + x[-2]) 
print(', '.join(str(y) for y in x))

Answer 3

关于wikipedia和wolfram上的Fibonacci序列有很多信息。比你需要的多得多。无论如何，学习如何利用这些资源（如果可能的话，可以很快）找到你需要的东西是件好事。

将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))

另一种方法是遵循定义（从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序列显示开始编号到结束编号

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

假设现在你写了一个f（n），它返回Fibonacci序列的第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

我的建议是学习阅读你所需要的东西。Euler项目（google for it）将培训您这样做：P 祝你好运，玩得开心！