fibonacci数列第n项的非递归求解.cpp

递归和分治法解一系列经典算法

//Fibonacci数列第n项的非递归求解

#include <stdio.h>
#include <math.h>
void main()
{
	int i,n=-1;
	double s0=sqrt(5),s1=1,s2=1;
	printf("请输入一个非负整数n: ");
	while(n<0) scanf("%d",&n);
	for(i=0; i<=n; i++)
	{
		s1*=(1+s0)/2;
		s2*=(1-s0)/2;
	}
	i=(int)((s1-s2)/s0);
	printf("F(%d)= %d\n",n,i);
}