在学校的anyview的时候，遇到了这个题：
【题目】已知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均以值调用的形式在函数参数表中出现。
要求实现下列函数：
Status Fibonacci(int k, int m, int &f);
/* 如果能求得k阶斐波那契序列的第m项的值f，则返回OK；*/
/* 否则（比如，参数k和m不合理）返回ERROR */
然后我自己想到的是用递归来做，一开始我用的是纯递归，大概思路就是n大于k-1的部分，都用递归解除，然后再把递归的结果累加，最后得到fn。然后提交的时候，虽然出来几个都是right，但速度极慢，可以说是很难跑完。
后来一个大佬帮我看了后，说这里递归好多次，太耗内存了，就好多结果重复算。（因为是累加的时候有很多重复）然后，就改装了一下，弄了个数组来存中间递归的数，来看代码：
/**********
【题目】已知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均以值调用的形式在函数参数表中出现。
**********/
int a[]; //数列是拿来记住结果的，不然我这种递归每一次都会很多重复
int beforek = ;
void addCount(int m)
{
for(int i=;i<=m+;i++)
a[i]=; } Status Fibonacci(int k, int m, int &f)
/* 求k阶斐波那契序列的第m项的值f */
{ if(k<=||m<) {
f = ;
return ERROR;
}
if(beforek==||beforek!=k) {
beforek=k;
memset(a,,sizeof(int)*(m+));
}
if(a[m]!=) {f=a[m];return OK;}
if(m<k){
if(m==(k-)){
f = ;
a[m] = f;
return OK;
} else {
f = ;
a[m] = f;
return OK;
}
}
else {//m>=k
int result = ;
int bound = m-k;
m--;
while(m>=bound) {
int temp = ;
Fibonacci(k,m,temp);
a[m] = temp;
result = result + temp;
m--;
}
f = result;
return OK;
}
}
后面有做到这个题，不过是要求用循环队列来做，然后就换个思路思考，
观察发现fn前面k-1个数的取值是0/1，然后fn的值当n大于k-1的时候，
它的值就会等于fn-1还有后面的一共k-1个数的和，所以我们让队列保持有k-1个
数，然后不断插入f，f的值是队列中k-1个数的和，插入后又踢掉一个，直到尾
巴指到n-1，然后再把这个队列末尾那个返回就行了，
看代码：
本题的循环队列的类型定义如下：
typedef struct {
ElemType *base; // 存储空间的基址
int front; // 队头位标
int rear; // 队尾位标，指示队尾元素的下一位置
int maxSize; // 最大长度
} SqQueue;
**********/ /*思路：观察发现fn前面k-1个数的取值是0/1，然后fn的值当n大于k-1的时候，
它的值就会等于fn-1还有后面的一共k-1个数的和，所以我们让队列保持有k-1个
数，然后不断插入f，f的值是队列中k-1个数的和，插入后又踢掉一个，直到尾
巴指到n-1*/ int InitSqQueue(SqQueue &Q,int n) { //初始化，建立空队列
Q.base = (ElemType *)malloc(sizeof(ElemType)*(n+));
if(Q.base==NULL) return ;
Q.front = ;
Q.rear = ;
Q.maxSize = n;
return ;
} int EnSqQueue(SqQueue &Q,ElemType e) {
if( (Q.rear+)%Q.maxSize==Q.front ) {
return ;
} else {
Q.base[Q.rear] = e;
Q.rear = (Q.rear+)%Q.maxSize;
return ;
}
} int DeSqQueue(SqQueue &Q,ElemType &e) {
if(Q.rear==Q.front) {
return ;
} else {
e = Q.base[Q.front];
Q.front = (Q.front+)%Q.maxSize;
return ;
}
} long Fib(int k, int n)
/* 求k阶斐波那契序列的第n+1项fn */
{
if(n<=k-)return ;
if(n==k-)return ;
/*下面的情况n一定是大于k-1的*/
SqQueue Q;
InitSqQueue(Q,n+k);//maxSize应该是无所谓的
int f,i,e;
for(i = ; i <= k- ; i ++) { //结束后循环队列里应该有k个元素
if(i<=k-) {
f = ;
} else if(i==(k-)) {
f = ;
}
EnSqQueue(Q,f);
}
int theRear = k-;//此时的rear元素是k-1
while(theRear <= n-) {
for(i = Q.front, f = ; i < Q.rear; i = (i+)%Q.maxSize) {
f = f + Q.base[i]; //求出的f是队列中k-1个元素的和
}
EnSqQueue(Q,f);//f入队
DeSqQueue(Q,e);//出一个队,保持队列中有k-1个元素
theRear++;
}
return Q.base[Q.rear-];//最后一个就是fn的值
}