14天阅读挑战赛
14天阅读挑战赛
努力是为了不平庸~
学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。
学习日记
目录
学习日记
一、斐波那契数列的概念
二、斐波那契的复现
1、递归实现
2、迭代实现
3、总结
三、兔子问题
一、斐波那契数列的概念
斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
斐波那契数列指的是这样一个数列：
0，1，1，2，3，5，8，13，21，34，55，89，144，233，377，610，987，1597，2584，4181，6765，10946，17711……
它的规律是：这个数列从第 3 项开始，每一项都等于前两项之和。
在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n – 1)+F(n – 2)（n ≥ 2，n ∈ N*），显然，斐波那契数列是一个线性递推数列。
我们给出斐波那契数列的推导公式：
二、斐波那契的复现
常用的实现斐波那契数列的方法分为两大类：递归和循环。
1、递归实现
#C语言版本
#include int F(int n) //斐波那契数列函数 递归形式{if(n == 0) //初始化return 0;if(n == 1 || n == 2)return 1;return F(n-1) + F(n-2);//如果n != 1 && n != 2 进行递归运算} int main(){int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n", F(n));}return 0;}#python版本
import timedef Fibonacci(i):if i==0:return 0elif i==1:return 1else:return Fibonacci(i-1)+Fibonacci(i-2)def main(): a=time.time()for i in range(1,101):print(Fibonacci(i))b=time.time()print("running time:%s Seconds"%(b-a))main()2、迭代实现
#C语言版本
#include int fibonacci(int n) //定义斐波那契函数{if(n == 0) //定义初始值return 0; if(n == 1 || n == 2)return 1;int a=1,b=1,c=0;//定义初始值//用一个for循环，a、b分别为前两项，c为前两项之和，得到c后进行交换更新a、b的值，进行n次交换即可。for(int i=3;i<=n;i++)//更新操作{c = a+b;a = b;b = c;}return c;//c即为结果输出} int main(){int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n", fibonacci(n));}return 0;}#python版本
import timedef fib(n):if n<=0:return 0if n == 1:return nfirst, second, third = 0, 1, 0for i in range(2, n+1):third = first + secondfirst = secondsecond = thirdreturn thirddef main():a=time.time()for i in range(1,101):print(fib(i))b=time.time()print("%s"%(b-a))main() 3、总结
因为递归算法存在着大量的重复计算，在N趋近于较大值时，可能会造成内存溢出或超时的情况，又因为使用迭代算法的情况下同样可以实现计算斐波那契数列第N项的功能，所以在N值很大时我们优先使用迭代算法。
三、兔子问题
题目描述
这是一个有趣的古典数学问题，著名意大利数学家Fibonacci曾提出一个问题：有一对小兔子，从出生后第3个月起每个月都生一对兔子。小兔子长到第3个月后每个月又生一对兔子。按此规律，假设没有兔子死亡，第一个月有一对刚出生的小兔子，问第n个月有多少对兔子？
输入：月数n（1<=n<=44）。输出：输出第n个月有多少对兔子。
样例输入 3样例输出2
#递归
#include int fib(int n) { if(n==1||n==2) return 1; else return fib(n-1)+fib(n-2); } int main() { int n ; scanf("%d",&n); printf("%d",fib(n)); }#循环
#includeint main () { int i,n,item,n1=1,n2=1; scanf("%d",&n); if(n==1||n==2) item=1; for(i=3;i<=n;i++) { item=n1+n2; n2=n1; n1=item; } printf("%d",item); }