由来:
斐波那契数列的发明者,是意大利数学家列昂纳多·斐波那契(Leonardo Fibonacci),斐波纳契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……在数学上,斐波纳契数列以如下被以递归的方法定义:F0=0,F1=1,Fn=F(n-1)+F(n-2)(n>=2,n∈N*)
有趣问题:
1,有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?
答:这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种方法……所以,1,2,3,5,8,13……登上十级,有89种。
2,数列中相邻两项的前项比后项的极限是多少,就是问,当n趋于无穷大时,F(n)/F(n+1)的极限是多少?
答:这个可由它的通项公式直接得到,极限是(-1+√5)/2,这个就是所谓的黄金分割点,也是代表大自然的和谐的一个数字。
数学表示:
Fibonacci数列的数学表达式就是:
F(n) = F(n-1) + F(n-2)
F(1) = 1
F(2) = 1
我们的第一个问题如果用人去实验可能会累得半死,但用这个数据表达式在一页纸上就能轻松的算出结果,假如我们要算的是100梯呢,那么可能就得花上好几百页和几十个小时,但是我们有了计算机这就是分分钟的事情,python递归代码如下:
def f(n):
return 1 if n in (0, 1) else f(n-1)+f(n-2)
解决问题啦,100梯也不是问题,可是我们不能高兴得太早,作为一个程序员用一行代码就要运行几分钟才能得出结果,肯定是个笑话,而且当楼梯在高点到1000这个程序也无能力了。
通过分析代码发现这个递归代码做了很多重复的运算,加以改进:
result = [0 for i in xrange(1000)]
result[0] = result[1] = 1
def f(n):
global result
if result[n] != 1:
return result[n]
else:
result[n] = f(n-1)+f(n-2)
return result[n]
上面这个代码显示利用了计算机的空间来换时间的做法,但是随着递归深度的增加,计算机缓存总有被撑满的时候,有没既快又省空间的方法呢,答案是肯定的,通过更一步改进我们得到了如下迭代式:
def f(n):
a, b = 0, 1
for i in xrange(n):
a, b = b, a+b
return b
这个迭代式我们只需要缓存两个字就OK了,在运行百万级的阶梯都没有问题,再高点的梯子人类还没修出来呢
分享到:
相关推荐
Fibonacci数列斐波那契数列PPT学习教案.pptx
C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++斐波那契数列C++...
斐波那契数列: 在数学上它以递归的方式进行定义,指这样的一个数列:0、1、1、2、3、5、8、13、21、34、55、89、144……,即前两个数为分别为0和1,从第3项开始,每项的值都等于其前两项之和。斐波那契数列Fib(n)用...
一 生小兔问题引起的二 它们也产生斐波那契数列三 通项的其他表达式四 斐波那契数列是二阶循环数列五 斐波那契数列的数论性质六 斐波那契数列的其他性质七 某些斐波那契数列之和八 斐波那契数列与连分数九 斐波那契...
Fibonacci(斐波那契)数列的JAVA解法,包含了斐波那契数列常见问题的一些算法。
本代码使用C++语言书写,编译环境VS2013。...斐波那契数列(Fibonacci Sequence)又称黄金分割数列,指的是这样一个数列:0、1、1、2、3、5、8、13、21、…… 本代码是练习作品,如有错误或修改,请指正,感谢感谢。
使用C++非递归实现fibonacci数列,对正在学习算法的同学应该挺有帮助的
斐波那契数列(肥不拉几数列)斐波那契数列(肥不拉几数列)斐波那契数列(肥不拉几数列)斐波那契数列(肥不拉几数列)斐波那契数列(肥不拉几数列)斐波那契数列(肥不拉几数列)斐波那契数列(肥不拉几数列)...
# 题目:斐波那契数列。 # 程序分析:斐波那契数列(Fibonacci sequence),从1,1开始,后面每一项等于前面两项之和。图方便就递归实现,图性能就用循环。
递归方法实现斐波那契数列
封装的Fibonacci 斐波那契数列。输入想要的斐波那契数列的长度,输出结果数列
递归方法 def fibonacci(n): if n <= 1: return n else: return fibonacci(n-1) + fibonacci(n-2) n = int(input("请输入要计算的斐波那契数列的项数:")) print("斐波那契数列的第", n, "项为:", fibonacci(n)) 2...
编写一个Java程序,用于输出Fibonacci数列的前20项。
【问题描述】编写函数f,功能是用递归的方法求斐波那契数列的第n项,函数原型为 int f(int n),在主函数中输入一个正整数n,调用函数f求出斐波那契数列的第n项,并在主函数中输出。 斐波那契数列:1,1,2,3,5,8,13,...
里面是【斐波那契数列】的前100项,可以当做学习过程中对照是否正确等使用,加油!
自斐波那契数列创立以来,它在数学理论和应用上不断显露出至关重要的地位。随着时代的进步,数学家们发掘了其中的数学联系。这无疑地激发了人们进一步探索数学的兴趣,也使人们对数学的了解更加的系统化。斐波那契...
Fibonacci数列,用c++编写的,非递归的函数调用求Fibonacci数列的第n项
斐波那契数列实现的C++代码;代码易懂易扩展。
(新课标)2020年高考数学 题型全归纳 斐波那契数列.doc
算法-数论- 斐波那契数列(Fibonacci).rar