如何写斐波纳契数列？

Question

我最初错误地编写了程序.我没有在一个范围(即startNumber 1,endNumber 20应该=只有1和20之间的数字)之间返回Fibonacci数,而是为程序编写了显示范围之间的所有Fibonacci数(即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))

有人在我的第二部分(因为重复而关闭 - /sf/ask/35293541/)指出我需要使用while循环通过生成器传递startNumber和endNumber.有人可以指点我如何做到这一点？欢迎任何帮助.

---

我是一名学习程序员,而且我遇到了一些混乱.我被要求编写一个程序,用于通过用户输入的起始编号和结束编号来计算和显示斐波纳契序列(即startNumber = 20 endNumber = 100,它将仅显示该范围之间的数字).诀窍是包含它(我不知道如何在Python中使用它？ - 我假设这意味着使用包含范围？).

到目前为止我所拥有的不是实际编码,而是:

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

我不知道从哪里开始,我正在询问如何写这个的想法或见解.我也尝试过编写Fib序列论坛,但我也迷失了.

Answer 1

关于维基百科和沃尔夫拉姆的斐波那契序列有很多信息.比你可能需要的要多得多.无论如何,学习如何使用这些资源来找到(如果可能的话)你需要的东西是一件好事.

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

另一种方法是遵循定义(来自维基百科):

序列的第一个数字是0,第二个数字是1,每个后续数字等于序列本身的前两个数字的总和,产生序列0,1,1,2,3,5,8等

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

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

仅从Fib序列显示startNumber到endNumber.

一旦你知道如何生成Fibonacci数字,你只需要循环数字并检查它们是否验证了给定的条件.

假设你现在写了af(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

我的提示是学会阅读你需要的东西.项目欧拉(google for it)将训练你这样做:P祝你好运,玩得开心!

Answer 2

Fibonacci序列的高效Pythonic发生器

我试图获得这个序列中最短的Pythonic生成时发现了这个问题(后来意识到我在Python增强提案中看到了类似的一个),我没有注意到其他人提出我的具体解决方案(尽管最佳答案)接近,但仍然不那么优雅,所以在这里,评论描述第一次迭代,因为我认为这可以帮助读者理解:

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的文档中,即使使用的变量a和b,我现在回想起写这个答案之前见过,但我觉得这样的回答表明了语言的更好的使用.)

递归定义的实现

该整数序列的在线百科全书递归定义斐波那契序列

F(n)= F(n-1)+ F(n-2),F(0)= 0且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版本可以达到100万,尽管它使用笔记本电脑的所有8 GB内存来执行此操作:

> length $ take 100000000 fib 
100000000

Answer 3

为什么不简单地执行以下操作？

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

Answer 4

Fibonacci序列背后的想法显示在以下Python代码中:

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

这意味着fib是一个可以做三件事之一的函数.它将fib(1)== 1,fib(0)== 0和fib(n)定义为:

fib(n-1)+ fib(n-2)

其中n是任意整数.这意味着例如fib(2)扩展为以下算法:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

我们可以用下面的算法以相同的方式计算fib(3):

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

这里要认识到的重要一点是,在不计算fib(2)的情况下无法计算fib(3),这是通过知道fib(1)和fib(0)的定义来计算的.像fibonacci函数一样调用函数就称为递归,这是编程中的一个重要主题.

这听起来像是家庭作业,所以我不打算为你做开始/结束部分.Python虽然是一种非常富有表现力的语言,所以如果你理解数学,这应该是有意义的,并且希望教你递归.祝好运!

编辑:我的代码的一个潜在批评是它不使用超级方便的Python函数yield,这使得fib(n)函数缩短了很多.我的例子有点更通用,因为Python之外的很多语言实际上并没有产生.

Answer 5

时间复杂度:

通过消除Fibonacci系列递归树中的重复,缓存功能减少了计算Fibonacci级数从O(2 ^ n)到O(n)的常规方法:

代码:

import sys

table = [0]*1000

def FastFib(n):
    if n<=1:
        return n
    else:
        if(table[n-1]==0):
            table[n-1] = FastFib(n-1)
        if(table[n-2]==0):
            table[n-2] = FastFib(n-2)
        table[n] = table[n-1] + table[n-2]
        return table[n]

def main():
    print('Enter a number : ')
    num = int(sys.stdin.readline())
    print(FastFib(num))

if __name__=='__main__':
    main()

Answer 6

使用O(log n)基本算术运算非常有效.

def fib(n):
    return pow(2 << n, n + 1, (4 << 2*n) - (2 << n) - 1) % (2 << n)

这个使用O(1)基本算术运算,但中间结果的大小很大,因此效率不高.

def fib(n):
    return (4 << n*(3+n)) // ((4 << 2*n) - (2 << n) - 1) & ((2 << n) - 1)

这个通过平方求幂来计算多项式环Z [X] /(X ^ 2 - X - 1)中的X ^ n.该计算的结果是多项式Fib(n)X + Fib(n-1),从中可以读取第n个Fibonacci数.

同样,这使用O(log n)算术运算并且非常有效.

def mul(a, b):
        return a[0]*b[1]+a[1]*b[0]+a[0]*b[0], a[0]*b[0]+a[1]*b[1]

def fib(n):
        x, r = (1, 0), (0, 1)
        while n:
                if n & 1: r = mul(r, x)
                x = mul(x, x)
                n >>= 1
        return r[0]

Answer 7

Canonical Python代码打印Fibonacci序列:

a,b=1,1
while True:
  print a,
  a,b=b,a+b       # Could also use b=a+b;a=b-a

对于问题"打印长度大于1000位的第一个Fibonacci数":

a,b=1,1
i=1
while len(str(a))<=1000:
  i=i+1
  a,b=b,a+b

print i,len(str(a)),a