fb.cpp

K阶菲波那契算法

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

#define OVERFLOW -2
#define OK 1
#define	MAXSIZE 100

typedef struct
{
	int *elem;
	int font;
    int rear;
}SqQueue;

void InitQueue(SqQueue &Q,int k)
{
	Q.elem=(int *)malloc(k*sizeof(int));
	if(!Q.elem) 
		exit(OVERFLOW);
	Q.font=Q.rear=0;
}

void fb(int k,int max)
{
	int n;
	SqQueue cq;
	int *f;
	InitQueue(cq,k);
	f=(int *)malloc(MAXSIZE*sizeof(int));
	if(!f)
		exit(OVERFLOW);
	for(int i=0;i<=k-2;i++) 
	{
		f[i]=0;
		cq.elem[i]=0;
	}
	cq.elem[k-1]=cq.elem[k]= 1;   
	cq.rear=k;   
	n=k+1;    
	f[k-1]=f[k]=1;
	while(cq.elem[cq. rear]<max)
    {
		int j= (cq. rear+1)  %  (k+1);
        f[n]= cq.elem[cq. rear]*2- cq.elem[j];
        cq.elem[j]=f[n];    
		cq.rear=j;   
		n++;
    }
   if(cq.elem[cq.rear]>max)  
	   n=n-2; 
   else 
	   n=n-1;
   if (max==1)
   {
	   n=k;
	   f[k]=1;
   }
   if (max==0) 
	   n=k-2;
   for(i=0;i<=n;i++)
   {
	   printf("%d  ",f[i]);
	   if((i+1)%k==0)
		   printf("\n");
   }
}

main()
{
	int k,max;
	printf("请输入阶数k:");
	scanf("%d",&k);
	printf("请输入max:");
	scanf("%d",&max);
	fb(k,max);
	printf("\n");
}