该问题出自《C语言名题精选百则技巧篇》 Fabonacci数列f1,f2,...,fn的定义是这样的： f(n) = 1 n=1 f(n) = 1 n=2 f(n) = f(n-1)f(n-2) n2 第一种方法 递归方法 unsigned long fibonacci(int n){ if(n=2) return 1; else return fibonacci(n-1)+fibonacci(n-2
该问题出自《C语言名题精选百则技巧篇》
Fabonacci数列f1,f2,...,fn的定义是这样的：
f(n) = 1 n=1
f(n) = 1 n=2
f(n) = f(n-1)+f(n-2) n>2
第一种方法 递归方法
unsigned long fibonacci(int n)
{
if(n<br>
<strong>第二种方法 非递归方法</strong>
<p>此种方法和递归方法的执行顺序正好相反，递归方法先去计算</p><pre class="brush:php;toolbar:false">fibonacci(n-1)+fibonacci(n-2)再调用更小的数来计算，下一级是被动向上一级传递结果。而本方法是先计算最小的，下级主动向上一级报告结果。
数列的计算是两个值的和的计算，用两个变量代表这两个加数，初始值为f0 = f1 =1，i从3开始，表示从f3开始计算。
unsigned long fibonacci(int n)
{
unsigned long f0,f1,temp;
int i;
if(i<strong>第三种方法，快速计算方法</strong>
<p>f(n) = f(n-1) + f(n-2)</p>
<p>f(n-1) = f(n-1)</p>
<p>f(n),f(n-1)和f(n-1) ,f(n-2)之间存在一个矩阵T</p>
<p>1 1</p>
<p>1 0</p>
<p>初始值为 f(2)=1,f(1)=1.</p>
<p>我们要求f(n)和f(n-1)，只要将矩阵T^(n-2) 再和f(2),f(1)相乘。问题可以转化为求T^(n-2).</p>
<p>和求x^(n-2)类似。</p>
<p>一个2*2的矩阵，很简单，直接把矩阵元素写在参数里，并且直接相乘。矩阵的自乘算法</p>
<pre class="brush:php;toolbar:false">void matrix_power(unsigned long a,unsigned long b,
unsigned long c,unsigned long d,int n,
unsigned long *aa,unsigned long *bb,
unsigned long *cc,unsigned long *dd)
{
unsigned long xa,xb,xc,xd;
if(n==1)
*aa = a,*bb = b,*cc=c,*dd=d;
else if(n&0x01 == 1){ //奇数
matrix_power(a,b,c,d,n-1,&xa,&xb,&xc,&xd);
*aa = a*xa+b*xc;
*bb = a*xb+b*xd;
*cc = c*xa+d*xc;
*dd = c*xb+d*xd;
}else{ //偶数
matrix_power(a,b,c,d,n>>1,&xa,&xb,&xc,&xd);
*aa = xa*xa+xb*xc;
*bb = xa*xb+xb*xd;
*cc = xa*xa+xd*xc;
*dd = xc*xb+xd*xd;
}
}f(n) = f(n-1) +f(n-2) = aa +bb.
unsigned long m_fibonacci(int n)
{
<span style="white-space:pre"> </span>unsigned long a,b,c,d;
<span style="white-space:pre"> </span>if(n return 1;
else{
<span style="white-space:pre"> </span> matrix_power(1UL,1UL,1UL,0UL,n-2,&a,&b,&c,&d);
<span style="white-space:pre"> </span> return a+b;
<span style="white-space:pre"> </span>}
}F(i) = 1 i=0
F(i) = 1 i=1
F(i) = X*F(i-2) + Y*F(i-1) i>1
X=Y=1时就变成了一般的Fabonacci数，现在要求写一个函数，接受一个n值，不用数组与递归的方法计算出下面的结果：
F(0) * F(n) + F(1) *F(n-1) + ... + F(i)*F(n-i) + ...+ F(n-1)*F(1) +F(n)*F(0).
分析：
通过推算可以得出：
然后参照上面的方法2，程序如下:
unsigned long ext_fabonacci(int n,int x,int y)
{
unsigned long f0,f1;
unsigned long a0,a1;
unsigned long temp1,temp2;
int i;
if(n==0)
return 1;
else if(n==1)
return 2;
else{
for(f0=f1=1,a0=1,a1=2,i=2;i全部程序如下：
<pre class="brush:php;toolbar:false"><pre name="code" class="objc">#include <stdio.h>
#include <stdlib.h>
unsigned long fibonacci(int n)
{
unsigned long f0,f1,temp;
int i;
if(i>1,&xa,&xb,&xc,&xd);
*aa = xa*xa+xb*xc;
*bb = xa*xb+xb*xd;
*cc = xa*xa+xd*xc;
*dd = xc*xb+xd*xd;
}
}
unsigned long m_fibonacci(int n)
{
unsigned long a,b,c,d;
if(n");
scanf("%d",&n);
#if 1
answer = fibonacci(n);
//answer = r_fibonacci(n);
//answer = m_fibonacci(n);
printf("The answer of Fibonacci array is:\nf(%d) = %ld",n,answer);
#endif
#if 0
answer = ext_fabonacci(n,1,1);
printf("The answer of extend Fibonacci array is:\nF0*Fn+F1*Fn-1+...+Fi*Fn-i+...+Fn-1*F1+Fn*F0 = %ld",answer);
#endif
while(1)
getchar();
return 0;
}
</stdlib.h></stdio.h>运行结果：
扩充Fabonacci数的运行结果
