fibonacci.cpp

费波纳切序列

/*
 *Fibonacci序列
 */

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

int k;

typedef struct 
	{
		int *num;
		int front, rear;
	}queue2;

int enQueue(queue2 &Q, int n) {
	if ((Q.rear + 1) % (k + 1) == Q.front)
	{
		return 0;
	} else
	{
		Q.num[Q.rear] = n;
		Q.rear = (Q.rear + 1) % (k + 1);
		return 1;
	}
}

int deQueue(queue2 &Q, int &n) {
	if (Q.front == Q.rear)
	{
		return 0;
	} else
	{
		n = Q.num[Q.front];
		Q.front = (Q.front + 1) % (k + 1);
		return 1;
	}
}

void main () {			
	queue2 que;
	int temp, p, no, kn, succ, i;
	printf("请输入Fibonacci数列的除数k:\n");
	scanf("%d", &k);
	printf("请输入要求的Fibonacci数列的项数no:\n");
	scanf("%d", &no);
	que.num = (int *)malloc(sizeof(int)*(k+1));
	for (i = 0; i < k - 1; i++)
	{
		que.num[i] = 0;
	}
	que.num[k-1] = 1;
	que.front = 0;
	que.rear = k;	
	for (i = k; i <= no; i++)
	{
		p = que.front;
		temp = 0;
		while (p != que.rear)
		{
			temp = temp + que.num[p];
			p = (p + 1) % (k + 1);
		}
		succ = deQueue(que,kn);
		if (succ)
		{
			printf("一个元素出队: %d\n", kn);
		}
		succ = enQueue(que,temp);
		if (succ)
		{
			printf("成功插入一个元素: %d\n",temp);
		}
	}
	printf("最后k个元素:\n");
	p = que.front;
	while (p != que.rear)
	{
		printf("%d\n", que.num[p]);
		p = (p + 1) % (k + 1);
	}
	getch();
}