【严蔚敏】【数据结构题集(C语言版)】1.17 求k阶斐波那契序列的第m项值的函数算法

已知k阶斐波那契序列的定义为

    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阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。

k阶斐波那契序列定义:第k和k+1项为1,前k - 1项为0,从k项之后每一项都是前k项的和

如:k=2时,斐波那契序列为:0,1,1,2,3,5,...

k=3时,斐波那契序列为:0,0,1,1,2,4,7,13,...

算法一:数组法

判断m和k-1的大小,通过数组来存储斐波那契序列:

  m<=k-1时,所有项均为0;

  m>k-1时,前k-1项为0,k项之后的值通过循环和叠加依次写入数组,注意:数组中的下标从0开始;

 #include <stdio.h>
#include <stdlib.h> int E[],f; //数列E用来存储斐波那契序列,f表示第m项的值
int Fibonacci(int k,int m){
int i,j,sum;
if (m<=k-) f=;
else {
for(i=;i<k-;i++)
E[i]=; //前k-1项为0
E[k-]=; //第k项为1
for(i=k;i<=m;i++){ //前k项的和
sum=;
for(j=i-k;j<=i;j++)
sum +=E[j];
E[i]=sum;
}
f=E[m-]; //第m项
}
}
int main() {
int k,m;
scanf("%d%d",&k,&m);
Fibonacci(k,m);
printf("%d",f);
system("PAUSE"); //防止程序运行结束后编辑窗口关闭,此函数包含在stblib.h中
return ;
}

方法二:递归法

由定义知递推公式:f(n)=f(n-1)+f(n-2)+...+f(n-k)

                    又:f(n-1)=f(n-2)+f(n-3)+...+f(n-k)+f(n-k-1)   (n>k+1时成立)

由以上两式可得:f(n)=2f(n-1)-f(n-k-1)  (n>k+1)

所以:

    m<=k-1时,f(n)=0;

    m=k,k+1时,f(n)=1;

    m>k+1时,f(n)=2f(n-1)-f(n-k-1).

 #include<stdio.h>
#include<stdlib.h> int Fibonacci(int k,int m){
if(m<=k-) return ;
else if((m==k)||(m==k+)) return ;
else return *Fibonacci(k,m-)-Fibonacci(k,m-k-); // m>k+1时,公式成立
}
int main(){
int k,m;
scanf("%d%d",&k,&m);
printf("%d",Fibonacci(k,m));
system("PAUSE");
}
上一篇:YTU 2421: C语言习题 矩形法求定积分


下一篇:YTU 2405: C语言习题 牛顿迭代法求根