您好,欢迎访问一九零五行业门户网

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 return 1;    else{    matrix_power(1ul,1ul,1ul,0ul,n-2,&a,&b,&c,&d);    return a+b; }}
扩充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全部程序如下:#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数的运行结果
其它类似信息

推荐信息