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
第二种方法 非递归方法
此种方法和递归方法的执行顺序正好相反，递归方法先去计算
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
1  1
1   0
初始值为 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