『西工大-数据结构-NOJ』 010-k阶斐波那契数列(严3.32) 『西北工业大学』

解题思路：

这道题要求使用循环队列求斐波那契数列不大于max的最后k项的值。 循环列表通常情况包含以下结构：

typedef struct node{ int *data; int front; int rear; int N; }Queue; void CreatQueue(Queue *Q, int n） void AddElem(Queue *Q, int num) int Pop(Queue *Q) int Push(Queue *Q)

这道题，难道是不难，但是感觉这题有毒，按我的理解好像是要输出斐波那契数列不大于max的最后n项，也就是输入(14,3)应该输出(5,8,13),这是我写的代码可以实现的。结果提交后显示PE。去网上参考了一下别人AC的代码，发现他们输入(14,3)输出(4,7,13)然而AC了。 这就很迷惑，可能是我语文不好没读懂题？好吧，为了通过只能先用别人的一段核心函数了(FAKE_Fibonacci)，一部分我一开始写的函数主函数中没有用到。 具体操作见代码，代码中有部分注释。

题解代码：

#include<stdio.h> #include<stdlib.h> typedef struct node{//定义一个循环队列，队列中要有一个空储存单元用于判空 int *data;//int型数组data int front; int rear; int N; }Queue; void CreatQueue(Queue *Q, int n){//N值不定，动态申请 Q->N = n+1; Q->data = (int*)malloc(sizeof(int)*(Q->N)); Q->front = Q->rear = 0; } void AddElem(Queue *Q, int num){//队列添加元素 if((Q->rear+1)%(Q->N)==Q->front){//加减后要取mod return;//若判满，则无法添加元素 } else{ Q->rear = (Q->rear+1)%(Q->N); Q->data[Q->rear] = num; } } int DeleteFrontElem(Queue *Q){//删除队头元素,并弹出 Q->front = (Q->front+1)%Q->N; return Q->data[Q->front]; } //这题有毒，按我的理解好像是要输出斐波那契数列不大于max的最后n项，也就是输入(14,3)应该输出(5,8,13),这是我写的代码可以实现的。 //结果提交后显示PE。去网上参考了一下别人AC的代码，发现他们输入(14,3)输出(4,7,13)然而AC了。 //这就很迷惑，可能是我语文不好没读懂题？好吧，为了通过只能先用别人的一段核心函数了(FAKE_Fibonacci)，一部分我一开始写的函数主函数中没有用到。 //*****以下函数在主函数中未使用*****// int PopRear_N(Queue *Q){//弹出队尾元素 return Q->data[Q->rear]; } int PopRear_Nsub1(Queue *Q){//弹出队尾元素 return Q->data[(Q->rear+Q->N-1)%(Q->N)];//这里有一点小疑惑，直接(Q->rear-1)%(Q->N)]是错的 } void Fibonacci(Queue *Q, int max, int n){ //斐波那契循环数列 int i,j=0,num,current_num=1; //fibonacci数列初始化 for(i=0;i<n;i++){//用0和1填满循环数列 if(i==n-1){//让第n个是1，之后的第一次操作，由于current_num=1，n+1个也是1 AddElem(Q,1); } else{ AddElem(Q,0); } } while(current_num<=max){//current_num就是下一个斐波那契数列的元素值 DeleteFrontElem(Q); AddElem(Q,current_num); current_num = PopRear_N(Q)+PopRear_Nsub1(Q); } for(i=0;i<n;i++){ //把最后的数列输出 num = DeleteFrontElem(Q); printf("%d ",num); AddElem(Q,num); } } //*****以下函数在主函数中未使用*****// void FAKE_Fibonacci(Queue *Q, int max, int k){//为了AC，借鉴一下别人的函数 int i, item, t = 1,j = 0; CreatQueue(Q,k); for(i = 0; i<k; i++) if(i == k-1) AddElem(Q,1); else AddElem(Q,0); while(t <= max){ j++; DeleteFrontElem(Q); AddElem(Q,t); t = 0; for(i = 0; i<k; i++){ item = DeleteFrontElem(Q); t += item; AddElem(Q,item); } } for(i = 0; i<k; i++){ item = DeleteFrontElem(Q); printf("%d ", item); AddElem(Q,item); } } int main(){ int max,n; scanf("%d %d",&max,&n); Queue *Q; Q = (Queue*)malloc(sizeof(Queue)); CreatQueue(Q,n); //Fibonacci(Q,max,n); FAKE_Fibonacci(Q,max,n); return 0; }