2.9

该问题出自《C语言名题精选百则技巧篇》

Fabonacci数列f1,f2,...,fn的定义是这样的：

第一种方法 递归方法

unsigned long fibonacci(int n)
{
    if(n 

第二种方法 非递归方法

此种方法和递归方法的执行顺序正好相反，递归方法先去计算

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 

第三种方法，快速计算方法

f(n) = f(n-1) + f(n-2)

f(n-1) = f(n-1)

f(n),f(n-1)和f(n-1) ,f(n-2)之间存在一个矩阵T

初始值为 f(2)=1,f(1)=1.

我们要求f(n)和f(n-1)，只要将矩阵T^(n-2) 再和f(2),f(1)相乘。问题可以转化为求T^(n-2).

和求x^(n-2)类似。

一个2*2的矩阵，很简单，直接把矩阵元素写在参数里，并且直接相乘。矩阵的自乘算法

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)
{
 	 unsigned long a,b,c,d;
 	 if(n 	 return 1;
    else{
 	     matrix_power(1UL,1UL,1UL,0UL,n-2,&a,&b,&c,&d);
 	     return a+b;
 	 }
} 

扩充Fabonacci数

F(i) = 1 i=0

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 

全部程序如下：

#include  
#include  
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;
	
}
 




 

 
运行结果：
 


 扩充Fabonacci数的运行结果 


      
查看更多关于2.9的详细内容...
        

          
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did98695