k阶斐波那契数列的实现.docVIP

斐波那契（Fibonacci）数列 1 算法分析： 1 算法的实现： 1 计算一元多项式： 2 斐波那契（Fibonacci）数列 算法分析： 首先看这样一个有趣的问题：假定一个月大小的一对兔子（雄和雌的），对于繁殖还太年轻，但两个月大小的兔子便足够成熟。又假定从第二个月开始，每个月它们都繁殖一对新的兔子（正好是雌雄一对），如果每一对兔子的繁殖按上面所说的方式，从开始起每个月有多少对兔子呢？??? 解答：?? 我们可以用合适的图示来表明题意：?? ???1，1，2，3，5，8，13，21，34… 其规律是从第三项起，每一项都是前两项的和．用递推公式表达就是： a1]=a[2]=1， an]＝an-1]十an-2] (n=3) 此处k=2； 作业上的递推公式： f[0]=0, f[1]=0, ……, f[k-2]=0, f[k-1]=1 f[n]=f[n-1]+f[n-2]+……+f[n-k], n=k,k+1,…… 此处k为大于3的任意整数； 算法的实现： #include stdafx.h #include iostream.h #include stdlib.h // Fibonacci函数 int fibonacci(int k, int m) //k为阶数，m为待计算项 { int *f; //数列数组 int i; //计算数列项控制变量 int j; if (k2 || m0) return -1; //判断数据取值超出界限否 f=(int *)malloc(m*sizeof(int)); //申请数列使用空间 if (f==NULL) return -1; else { for (i=0; ik-1; i++) f[i]=0; //预置为0项 f[k-1]=1;// 预置为1项 for (i=k; i=m; i++) //计算f[k]~f[m]项 { f[i]=0; for (j=1;j=k;j++) //计算f[n]=f[n-1]+f[n-2]+…+f[n-k] f[i]=f[i]+f[i-j]; } } return f[m];//返回计算结果 } //主程序 int main(int argc, char* argv[]) { int k; //Fibonacci数列的阶数 int m; //求解的数列通项项数 int result; //输入数据 coutEnter k=; cink; coutendl; coutEnter m=; cinm; //调用函数 result=fibonacci(k, m); //输出结果 if (result==-1) coutINPUT ERROR!!endl; else coutresult OKendl; return 0; } #includestdio.h #define maxsize 50 main() { int m, n,d,i,count; int A[maxsize]; printf(\n请输入n,m的值，以逗号分开:); scanf(%d,%d,n,m); for(i=0;in;i++) A[i]=i+1; printf(出队前:); for(i=0;in;i++) printf(%d,A[i]); printf(\n); printf(出队后:); count=0; d=0; while(dn) for(i=0;in;i++) if (A[i]!=0) { count++; if(count==m) { printf(%d,A[i]); A[i]=0; count=0 ; d++; } }printf(\n); }