C求k阶裴波那契数列的第m项值的函数

2025-02-13 05:14:44

推荐回答（2个）

回答1：

/*
这道题目求解推荐使用非递归算法！！！
递归的方法不能充分利用以前计算的结果，存在大量的重复计算。
随着 k,m 增大，运算次数层指数级增加！！！

如 k=10，m=100,用【递归】的方法将会计算很长时间！！！
一楼用的是递归算法，而我用的是非递归算法，楼主可以比较一下性能，从中体会一下递归带来的好处和坏处。

比较两种算法时推荐测试数据（结果没有溢出）
k m
------
5 100
6 60
7 70

*****************************************************************

已知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均以值调用的形式在函数参数表中出现。

算法：
当 m<=(k-1)，直接根据定义就能求出 f(m)
当 m>=k，f(m)为它前面的k项f(m-1),f(m-2)...f(m-k)求和

改进；
我们观察式子：
a)f(m)=f(m-1)+f(m-2)+…+f(m-k),
b)f(m+1)=f(m)+f(m-1)+f(m-2)+…+f(m-k+1)
=f(m)+{f(m-1)+f(m-2)+…+f(m-k+1)+f(m-k)}-f(m-k)
=f(m)+f(m)-f(m-k)
=2*f(m)-f(m-k)

f(m)=2*f(m-1)-f(m-k-1),(m-k-1)>=k,即 m>=2*k+1

这时把求 f(m) 由 k 次加法运算变换成一次乘法和一次减法，加快了求解速度。

*/
#include
#include
#include
__int64 int F(int K,int M)
{
int i;
//__int64 的范围是 -2^63-1~2^63
__int64 int * data ;
int data_p;
int SIZE = K+1;
int counter;
__int64 int result;

data = ( __int64*)malloc(sizeof( __int64)*SIZE);
memset(data,0,sizeof(data));
for(i=0;i data[K-1]=1;

data_p = K;
counter = K-1;

if(M {
return data[M];
}

while(counter < M)
{
if(counter<=2*K)
{
data[data_p]=0;
for(i=1;i<=K;i++)
{
data[data_p]+=data[(data_p-i+SIZE)%SIZE];
}
}
else
{
data[data_p]=2*data[(data_p-1+SIZE)%SIZE]-data[(data_p-1-K+SIZE)%SIZE];
}
counter++;
if(data[data_p]<0)
{
printf("结果溢出！！！\n");
return -1;
}
if(counter == M)
{
result = data[data_p];
}
data_p=(data_p+1)%SIZE;

}

free(data);
return result;

}
int main(int argc, char *argv[])
{
int m,k;
while(scanf("%d%d",&k,&m)!=EOF)
{
printf("k=%d m=%d ,r=%I64d\n",k,m,F(k,m));
}
return 0;
}

/*
2 0
2 1
2 2
2 3
2 4
2 5
2 6
3 5
4 6
5 7
6 8

5 100
6 60
7 70

*/