2.9

该问题出自《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;
	}
}

a,b,c,d为初始矩阵T,*aa,*bb,*cc,*dd为n个矩阵乘完以后矩阵元素值的地址。

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>}
}

扩充Fabonacci数

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数的运行结果