fib.cpp.bak

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

//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 ) .                                  */
/*作者：想飞翔的鱼 [e-mail]   整理于2005.07.28                        */
/*******************************************************************************/


#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");
}


/*******************************************************************************/
/*斐波那契数列来自于斐波那契的一个计算兔子数量的数学题                         */
/*K阶斐波那契数列的前K-1项均为0，第k项为1，以后的每一项都是前K项的和           */
/*试利用循环队列编写求k阶斐波那契序列中前n+1项（f0, f1 , f2 ,… fn )的程序     */
/*要求满足f(n) ≤max而f(n+1) >max ，其中max为某个约定的常数。                  */
/*请利用公式f(i+1) = 2*f(i) - f(i-k)，队列的容量为k+1                      
/*作者：想飞翔的鱼 [e-mail]   整理于2005.07.28                        */
/*******************************************************************************/

/*#include
#include

#define  enoughsize 100

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

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



void GetFib_CyQueue(int k,int n)//求k阶斐波那契序列的前n+1项 
{ 
  InitCyQueue(Q); //其MAXSIZE设置为k 
  for(i=0;i<k-1;i++) Q.base[i]=0; 

  Q.base[k-1]=1; //给前k项赋初值 
  for(i=0;i<k;i++) printf("%d",Q.base[i]); 
  for(i=k;i<=n;i++) 
  { 
    m=i%k;sum=0; 
    for(j=0;j<k;j++) sum+=Q.base[(m+j)%k]; 
    Q.base[m]=sum; //求第i项的值存入队列中并取代已无用的第一项 
    printf("%d",sum); 
  } 
}//GetFib_CyQueue 


#include<stdio.h>
#define List_init_size 100
#define Listincrement 20
*/