问题

费波那契数列(意大利语:Successione di Fibonacci),又译费波拿契数、斐波那契数列、斐波那契数列、黄金分割数列。

在数学上,费波那契数列是以递归的方法来定义:

  1. F0 =0(n=0)
  2. F1 =1(n=1)
  3. Fn= F[n-1]+ F[n-2](n=>2)

关于Fibonacci的精彩解释,请看下列视频:

TED-神奇的斐波那契数列

如果要查看文字解释,请看维基百科词条:斐波那契数列

思路说明

几乎所有的高级语言都要拿Fibonacci数列为例子,解释递归、循环等概念。这里,我要用Python来演示一下,各种不同的写法,供参考。

解决(python)

递归——按照定义直接写

这种方法不是一个好方法,因为它的开销太大,比如计算fib1(100),就需要耐心等待较长一段时间了。所以,这是一种不实用的方法。但是,因为简单,列为第一种。

  1. def fib1(n):
  2. if n==0:
  3. return0
  4. elif n==1:
  5. return1
  6. else:
  7. return fib1(n-1)+ fib1(n-2)

递归,进行初始化

fib1的慢,就是因为每次都要计算前面已经算过的项目.这里将上述算法进行稍微改进。速度快了很多。

  1. memo ={0:0,1:1}
  2. def fib2(n):
  3. ifnot n in memo:
  4. memo[n]= fib2(n-1)+fib2(n-2)
  5. return memo[n]

迭代

  1. def fib3(n):
  2. a, b =0,1
  3. for i in range(n):
  4. a, b = b, a+b
  5. return a

直接理论数学结论

维基百科的词条 里面,已经列出了不同形式的Fibonacci数列的数学结果,可以直接将这些结果拿过来,通过程序计算,得到斐波那契数。此类程序,本文略。

这种方法来自网络

  1. print('!* Fibonacci Sequence python \n')
  2. defFibonacci_Series():
  3. x = input('Enter Series length to print fibonacci sequence')
  4. d,e=0,1
  5. a =[]
  6. a.append(d)
  7. a.append(e)
  8. while(x!=2):
  9. c = d + e
  10. d = e
  11. e = c
  12. a.append(c)
  13. x = x -1
  14. print(a)