郑州知名网站推广,东莞计算机培训机构哪个最好,wordpress快速建站教程视频教程,北京的招聘网站有哪些斐波那契数列数列是我们学习递归的入门问题#xff0c;是一种非常经典的题型#xff0c;也衍生出了一些更复杂的题型#xff0c;这一节就让我们彻底理解斐波那契数列系列问题。 一、概念介绍
1、什么是斐波那契数列#xff1f; 斐波那契数列#xff08;Fibonacci sequenc… 斐波那契数列数列是我们学习递归的入门问题是一种非常经典的题型也衍生出了一些更复杂的题型这一节就让我们彻底理解斐波那契数列系列问题。 一、概念介绍
1、什么是斐波那契数列 斐波那契数列Fibonacci sequence又称黄金分割数列因数学家莱昂纳多·斐波那契Leonardo Fibonacci以兔子繁殖为例子而引入故又称为“兔子数列”指的是这样一个数列1、1、2、3、5、8、13、21、34、……在数学上斐波那契数列以如下被以递推的方法定义F(0)0F(1)1, F(n)F(n - 1)F(n - 2)n ≥ 2n ∈ N 2、怎么定义斐波那契数列 斐波那契数列指的是这样一个数列1123581321345589… 递推公式 斐波那契数列1123581321345589… 斐波纳契数列以如下被以递归的方法定义 f[0] 0, f[1] 1f[n] f[n -1] f[n - 2](n 2) 这个数列从第三项开始每一项都等于前两项之和。 显然这是一个线性递推数列。 4、斐波那契数列系列问题详解
最入门的斐波那契数列问题 分析题意是最基本的斐波那契数列问题问的就是第n个斐波那契数列的值是多少并且输出出来。 根据我们的递推方程 : f[0] 0, f[1] 1f[n] f[n -1] f[n - 2](n 2)即可求出
递归示意图 1. 递归。该递归属于多分支递归会造成栈溢出。
//递归
#includestdio.hint Fib(int n)
{if (n 1 || n 2)//数列前两项{return 1;}else//从第三项开始{return Fib(n - 1) Fib(n - 2);}return 0;
}
int main()
{int n 0;scanf(%d, n);//输入一个数int ret Fib(n);//计算斐波那契数列printf(%d\n, ret);//打印结果return 0;
}
2非递归。非递归较递归效率更高避免了重复计算的时间和空间。
//非递归
int main()
{int n 0;printf(请输入一个整数);scanf(%d, n);if (n 1 || n 2) {return 1;}else {int f1 1;int f2 1;int f3 -1;for (int i 3; i n; i) {f3 f1 f2;f1 f2;f2 f3;}printf(该整数的Fib数列为%d, f3);}return 0;
}
3数组。 //数组法
#includestdio.hint Fib(int n)
{int i;int arr[100] { 0,1,1 };for (i 2; i n; i)//从第一项开始{arr[i] arr[i - 1] arr[i - 2];}return arr[n];
}
int main()
{int n;scanf(%d, n);printf(%d, Fib(n));return 0;
}
