C语言中经典算法 |
您所在的位置：网站首页 › C语言斐波那契数列前四十 › C语言中经典算法 |
C语言中经典算法
|
斐波那契数列的递推公式： 1、递归法 #include int fib(int m) { if(m>=3) { return fib(m-1)+fib(m-2); } else{ return 1; } } int main() { int n; scanf("%d",&n); printf("%d",fib(n)); return 0; }说明：在主调函数中，只写入输入输出，在fib()函数中实现计算的功能。 实参n把值传递给形参m，函数fib()开始分配内存空间。判断：当m>=3时，返回fib(m-1)+fib(m-2)；否则返回1； 例：n=6时 return fib(5)+fib(4); 怎么知道fib(5)和fib(4)的值呢？ fib(5)=fib(4)+fib(3)；fib(4)=fib(3)+fib(2)；fib(3)=fib(2)+fib(1)； ok！通过递推我们得到了fib(3)的值，这样，fib(4)、fib(5)的值也就得到了。 n为其他值时类似。 2、迭代法 #include int fib(int m) { if (m==1||m==2) return 1; int a=1,b=1,aw=0; while(m>=2) { aw=aw+a; a=b; b=aw; m=m-1; } return aw; } int main() { int n; scanf("%d",&n); printf("%d",fib(n)); return 0; }说明：主调函数同上，这一次在fib()里使用迭代的方法计算该数列。 通过递推公式我们不难看出， 设n=6， fib(5)=fib(4)+fib(3)；fib(4)=fib(3)+fib(2)；fib(3)=fib(2)+fib(1)； 倒过来看，可以将斐波那契数理解为前数的加和等于后数，则从第一项开始推起，每次向前叠加一个数，直到找到需要的项数。 while(m>=2) { aw=aw+a; a=b; //将前数的值赋给a,当前数赋给b，下一次循环时再相加。 b=aw; //b在这里起到中介容器的作用 m=m-1; //计数器 }3、数组法 与前两种方法类似，都是根据递推公式自上而下或自下而上递推出斐波那契数。引入数组的好处时，可以将计算出的数储存起来，方便在其他地方直接打印或调用。 #include int fib(int m) { int i; int bank[101]={0,1,1}; for(i=2;i |
我们尝试计算斐波那契数列的第n项并输出。【本文地址】
今日新闻 |
推荐新闻 |