Fibonacci数列是指1， 1， 2， 3， 5， 8， 13， 21， 34， ····这样的数列。用式子描述即f1, f2, fn, f1=1, f2=1, 其后fn=fn-1+fn-2。
现在考虑，如何写一个程序，接受参数n，返回第n个fibonacci数值呢？
通常的办法是用递归：即从n开始，依次调用自身求出f(n-1)和f(n-2)。代码如下：
unsigned long fibonacci(int n)
{
if(n==2 || n==1)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
{
if(n==2 || n==1)
return 1;
else
return fibonacci(n-1) + fibonacci(n-2);
}
虽然一目了然，但是效率实在太低。比如计算fibonacci(8)时，递归调用计算f(7)与f(6)，而计算f(7)时，又计算f(6)与f(5）,那么f(6)的计算就重复了！如此一出来，计算f(n)时，将会重复计算n-3次！n不需要很大时，计算出f(n)都已经是相当慢的！
根据fibonacci的性质，可以设计一种非递归的方法。效率会高一些。取代递归的，当然是循环。
思路：因为计算f(n）时，需要计算f(n-1)+f(n-2)。如果程序保留了f(n),f(n-1),f(n-2)。那么计算f(n+1)时。需要计算f(n）+ f(n-1)。那么要保留f(n-1)与f(n)丢掉f(n-2)。程序中，用f1与f2代表fn-2与fn-1，temp是fn-2，当计算出f2后，调整f2与f1的值，进行新的f1与f2的计算。
代码如下：
unsinged long fibonacci(int n)
{
unsigned long temp, f1, f2;
int i;
for(f1=f2=1, i=3; i<=n; i++)
{
temp = f1+f2;
f1=f2;
f2=temp;
}
return f2;
}
{
unsigned long temp, f1, f2;
int i;
for(f1=f2=1, i=3; i<=n; i++)
{
temp = f1+f2;
f1=f2;
f2=temp;
}
return f2;
}
其实求f(n)时还有一个可行的办法，可以马上得到值，而不用花费太多时间。那就是先将所求范围内的f[n]数列的结果算出来。存到数组里面。直接通过下标访问即可。
#define MAX 1000
unsigned long fib[MAX];
void genfib()
{
int i;
fib[0] = fib[1] = 1;
for(i=2;i<MAX;i++)
{
fib[i] = fib[i-1]+fib[i-2];
}
}
usigned long fibonacci(int n)
{
return fib[i];
}
unsigned long fib[MAX];
void genfib()
{
int i;
fib[0] = fib[1] = 1;
for(i=2;i<MAX;i++)
{
fib[i] = fib[i-1]+fib[i-2];
}
}
usigned long fibonacci(int n)
{
return fib[i];
}
这个算法很简单，也很高效，但是要预先耗费太多的内存！
C语言不熟哦
其实和其他语言一样。没有用到特性的地方。完全可以用其他语言实现。
老兄看来精通此道，我三月要C语言考试了，真的有点担心哎。我是从梵妮博客过来的。
God, 学习唯恐不及，焉敢被称作精通。
int f(int x){
double golden=(1+sqrt(5))/2;
int r=(int) round(pow(golden,x)/sqrt(5));
return r;
}
//———————————//
int Fib(int x){
double golden=(1+sqrt(5))/2;
int r= (int)(pow(golden,x)/sqrt(5))+x%2;
return r;
}
恩？要贴代码的话，弄完整点吧。