fib.cpp

数据结构中的非波那起序列

#include <malloc.h>
#include <iostream.h>
#include <stdio.h>
#define maxsize 15
#define k 14
void main()
{
typedef struct 
{
  int *base;
  int front,rear;
}fib;
  fib Q;
  Q.base=(int *)malloc(maxsize*sizeof(int));
  Q.front=Q.rear=0;
  printf("input max:");
  int max=0;
  scanf("%d",&max);
  int a[100];
  for(int i=0;i<maxsize-1;i++)
  {
    a[i]=Q.base[i]=0;  
  }
   Q.base[k]=Q.base[k+1]=1; 
   Q.rear=k+1;      int n=k+1;      a[k-1]=a[k]=1;
   while(Q.base[Q.rear]<max)
   {  int j= (Q.rear+1)  %  (k+1);
         a[n]= Q.base[Q.rear]*2- Q.base[j];
         Q.base[j]=a[n];     
		 Q.rear=j;   
		 n++;
   }
   if(Q.base[Q.rear]>max) 
	   n=n-2; 
   else
	   n=n-1;
   if (max==1)  {n=k;a[k]=1;}
   if (max==0)  { n=k-2;}
   for(int x=0;x<=n;x++)
   {printf("%d ",a[x]);}
}