关于k阶裴波那契序列的两种解法

在学校的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的值
}
上一篇:python对文件写操作报错UnicodeEncodeError


下一篇:python 基础之文件读操作