重庆免费建站公司地址,重庆在线课程平台,小程序注册好了怎么办开始使用,生鲜网站建设规划书意大利的数学家列昂那多斐波那契在1202年研究兔子产崽问题时发现了此数列#xff0e;设一对大兔子每月生一对小兔子#xff0c;每对新生兔在出生一个月后又下崽#xff0c;假若兔子都不死亡#xff0e;问#xff1a;一对兔子#xff0c;一年能繁殖成多少对兔子#xff1…意大利的数学家列昂那多·斐波那契在1202年研究兔子产崽问题时发现了此数列设一对大兔子每月生一对小兔子每对新生兔在出生一个月后又下崽假若兔子都不死亡问一对兔子一年能繁殖成多少对兔子题中本质上有两类兔子一类是能生殖的兔子简称为大兔子新生的兔子不能生殖简称为小兔子小兔子一个月就长成大兔子求的是大兔子与小兔子的总和。月份ⅠⅡⅢⅣⅤⅥⅦⅧⅨⅩⅪⅫ大兔对数1123581321345589144小兔对数01123581321345589到十二月时有大兔子144对小兔子89对共有兔子 14489233对从上表看出① 每月小兔对数上月大兔对数。②每月大兔对数等于上个月大兔对数与小兔对数之和综合①②两点我们就有每月大兔对数等于前两个月大兔对数之和如果用 un 表示第 n 月的大兔对数则有un un-1 un-2,n 2每月大兔对数un 排成数列为1123581321345589144此数列称为斐波那契数列递归法使用公式f[n]f[n-1]f[n-2]依次递归计算递归结束条件是f[1]1f[2]1。代码示例#includeusing namespace std;long long Fib(int n){if (n 0){return 0;}else if (n 1){return 1;}else if(n 1){return Fib(n - 1) Fib(n - 2);}//return n 1 ? Fib(n - 1) Fib(n - 2) : n; //条件运算符简单一行代码即可}void Test(){int N 0;scanf(%d, N);int ret Fib(N);printf(%d\n, ret);}int main(){Test();system(pause);return 0;}但是递归法解决此问题并非高效下面我们看看非递归法。非递归法迭代实现是最高效的时间复杂度是n*1 0(n)空间复杂度是0(1)。#includeusing namespace std;long long Fib(int n){if (n 0){return 0;}else if (n 1){return 1;}else if (n 1){int a 1;int b 1;int c 1;for (int i 2; i {c a b;a b;b c;}return c;}}void Test(){int N 0;scanf(%d, N);int ret Fib(N);printf(%d\n, ret);}int main(){Test();system(pause);return 0;}
