K阶斐波那契数列（数据结构）

代码：

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

例如：k=2时，斐波那契序列为：0,1,1,2,3,5,8,13...

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

#include <stdio.h>
#include <stdlib.h>typedef struct  Queue
{int data[100];//数据int front;//头指示器int rear;//尾指示器
} SeqQueue;void Initqueue(SeqQueue*Q);//初始化循环队列
void Compute(int max,int k,SeqQueue*Q);//计算斐波那契数列
void Printfqueue(SeqQueue*Q,int k);//输出最后k项int main()
{SeqQueue queue;int Max,K;Initqueue(&queue);//初始化循环队列scanf("%d %d",&Max,&K);//输入约定的常数与阶数Compute(Max,K,&queue);//计算斐波那契数列Printfqueue(&queue,K);//输出最后k项return 0;
}/*初始化循环队列*Q：被初始化的队*/
void Initqueue(SeqQueue*Q)
{Q->front=Q->rear=0;
}/*计算斐波那契数列  f(0)到f(n);*max: f(n)<=max,f(n+1)>max*k: 要求输出的最后 k 项*Q：目标循环队列*/
void Compute(int max,int k,SeqQueue*Q)
{int sum1=0,sum2=1;//此时sum1是前k-1个数的和，sum2是前k个数和Q->rear=k-1;for(int i=0; i<k-1; i++){Q->data[i]=0;//前k-1个数置为0}Q->data[k-1]=1;//第k个数为1while(!(sum2>max&&sum1<=max))//sum1是f(n),sum2是f(n+1){int t=Q->data[Q->front],m,n;sum1=sum2;//下一个sum1等于sum2n=Q->rear=(Q->rear+1)%k;//形成只有k个数据的循环队列Q->data[Q->rear]=sum1;//入栈的是前k个数之和sum2=sum2-t+sum1;//下一个sum2 = 原来的sum2 - 队头：t + 新增的队尾：sum1m=Q->front=(Q->front+1)%k;//队头后移}
}/*输出最后k项*Q:目标队列*k：要求的项数*/
void Printfqueue(SeqQueue*Q,int k)
{for(int i=Q->front; i!=Q->rear; i++){i=i%k;printf("%d ",Q->data[i]);}printf("%d",Q->data[Q->rear]);//特殊处理
}