fib.cpp

数据结构算法：使用循环队列

//K阶斐波那契数列
                                         

/*******************************************************************************/
/*K阶斐波那契数列的前K-1项均为0，第k项为1，以后的每一项都是前K项的和           */
/*试利用循环队列编写求k阶斐波那契序列中前n+1项（f0, f1 , f2 ,… fn )的程序     */
/*要求满足f(n) ≤max而f(n+1) >max ，其中max为某个约定的常数。                  */
/*注意本题所用循环队列的容量仅为k,则在算法执行结束时，留在循环队列中的元素应是 */
/*k阶斐波那契序列中的最后k项fn-k+1 ,… fn ) .                                  */
/*******************************************************************************/


#include <stdio.h>
#include <stdlib.h>

#define  enoughsize 100

typedef struct 
{
 int *base;
 int front;
 int rear;
}SqQueue;

int AddSum(int n,int *q)
{
 int sum=0;
 int i;
 for(i=0;i<n;i++)  sum+=q[i];
 return sum;
}

void main()
{
 SqQueue Q;
 int k,max,i,n,*store;
 printf("请输入此斐波那契的阶数:");
 scanf("%d",&k);
 printf("请输入边界数:");
 scanf("%d",&max);
 Q.base=(int*)malloc(k*sizeof(int));
 store=(int*)malloc(enoughsize*sizeof(int));
 if((!Q.base)||(!store))
 {
  printf("Error!");
  return;
 }
 for(i=0;i<k;i++)
 {
  store[i]=0;
  Q.base[i]=0;
 }
 store[k-1]=1;
 Q.base[k-1]=1;
 store[k]=AddSum(k,Q.base);
 Q.front=0;
 Q.rear=k-1;
 n=k;
 while(store[n]<=max)
 {
  Q.rear=(Q.rear+1)%k;
  Q.base[Q.rear]=store[n];
  n++;
  store[n]=AddSum(k,Q.base);
 }
 printf("The first %d%s%d%c%s",n," numbers are less than ",max,'.',"\n");
 printf("The numbers are:\n");
 for(i=0;i<n;i++)  printf("%d%c",store[i],' ');
 printf("\n");
}