fib.cpp

n阶费波纳契数列求值

#include<iostream.h>
#include<malloc.h>
#include "Fib.h"



void main()
{
	int i,k;
	cout<<"请输入您想求的菲波纳契数列的阶数 : "<<endl<<endl<<"i : ";
	cin>>i;
	cout<<endl;
	cout<<"请输入您想求的菲波纳契数列的第 n 项 : "<<endl<<endl<<"n : ";
	cin>>k;
	cout<<endl;
	if((i < 0) || (k < 0) || (k <= i))
		cout<<"数据错误！"<<endl<<endl;
	else
		NewFib(i,k);
}

void NewFib(int i, int n)
{
	int k, sum;                                            
	Fib *head, *p;
	head = (Fib*)malloc(sizeof(Fib));	//生成k阶循环链表
	head->data = 0;
	p = head;
	for(k = i - 1; k > 0; k--)
	{
		p->Next = (Fib*)malloc(sizeof(Fib));
		p->Next->data = 0;
		p = p->Next;
	}
	p->data = 1;
	p->Next = head;


	for(int j = n - i; j > 0; j--)	//进行菲波纳契运算
	{
		sum = 0;
		p = head;
		while(p->Next != head)
		{
			sum = sum + p->data;
			p = p->Next;
		}
		sum = sum + p->data;
		p = head;
		while(p->Next != head)
		{
			p->data = p->Next->data; 
			p = p->Next;
		}
		p->data = sum;
	}
	p = head;
	while(p->Next != head)
		p = p->Next;
	cout<<endl<<"第 "<<n<<"项数值是 : "<<p->data<<endl;
	
	p = head;
	free(p);
	p = NULL;
}