目录
斐波那契数列 引出C语言代码实现——递归C语言代码实现——非递归斐波那契数列 引出
斐波那契数列的应用十分广泛,这里不再列举。
C语言代码实现——递归
同时也有许多种代码实现方式,这里仅列举C语言的实现方法:
核心思想是使用“递归”。
//C语言:递归实现 Fibonacci数列//输入n,求 Fibonacci[n] (在数学中,常常写作Fibonacci(n) ) #include <stdio.h>#define N 100long Fibonacci(int n);int main(){int n;long k;printf("请输入n:");scanf("%d",&n);k=Fibonacci(n);putchar('\n');printf("Fibonacci(%d)=%ld\n",n,k);return 0;}long Fibonacci(int n){if(n==1||n==2){return 1;}else{return Fibonacci(n-1)+Fibonacci(n-2);}}
几个测试:
下面这个例子,数据太大时,应当会出错:由于精度问题、表示范围问题。
正解:Fibonacci(50) = 12 586 269 025
而且注意下面的耗时,也很长。
查看课本可知,long int
的表示范围是:
-2 147 483 648 ~ 2 147 483 647
(10位数)。而上面Fibonacci(50)结果是11位数,当然会出错!
同样,下面结果也不对:
也是因为表示范围问题。
正解:Fibonacci(49) = 7 778 742 049
下面来测试个正确
的结果:↓ ↓ ↓
在本机测试中,第46项即Fibonacci(46)应当是 long int 能测试的最大值了。
耗时8.822秒。
C语言代码实现——非递归
//非递归实现Fibonacci数列#include <stdio.h>long Fibonacci(int n);int main(){int n;long k;printf("请输入n:");scanf("%d",&n);k=Fibonacci(n);putchar('\n');printf("Fibonacci(%d)=%ld\n",n,k);return 0;}//非递归实现Fibonacci数列 long Fibonacci(int n){int n1=1,n2=1;int t=0,i=0;if (n<3){//即如果n为1或者2的话,那么Fibonacci(1) = Fibonacci(2)=1 return 1;}else //下面举个例子,便于理解: {//例如n为6,我们知道Fibonacci数列为:1、1、2、3、5、8...//此时对于下面for循环,则i=0,i<4。开始时n1和n2都是1,即第一和第二项 for(i=0; i<n-2; i++){t = n1 + n2; //t就是数列第三项,为 1+1=2 n1 = n2; //注意:令n2赋值给n1,即n1和n2分别 后移一位,这时新的n1即第二项F(2)=1 n2 = t;//这里同理,t作为新的n2,即F(3)=2 //依次类推,即可实现求每一项,然后得到 Fibonacci(6),即 Fibonacci(n) }//注意:如果还不好理解,那么动笔写一下就会理解啦! return t;}}
我觉得我把注释写的已经比较清楚了,如果不明白的话,看一下下面这个图,应该会很好理解:
那么接下来还是几个测试:
事实证明,上面的结果是正确的。
(另外,对于斐波那契数列的前100项,我将以一个txt的格式上传到“资源
”中,可以直接下载。)
至于选用哪个,建议初学者还是使用递归的方式,更便于理解。