Chinaunix

标题: 一个貌似简单的算法题 [打印本页]

作者: xwolff 时间: 2008-09-27 09:31
标题: 一个貌似简单的算法题
昨天看到一个网友发帖子计算1/1+1/2+2/3+3/5+5/8...，这个数列其实是Fibonacci数列前项与后项的比值。通常思路就是用计算Fibonacci数列的方法来计算该值。但是，Fibonacci数列发散极快，呈指数级增长，计算到第47项时已超出int型变量的存储范围，也就是说采用int型变量存储Fibonacci数列值，中间结果即使强制转换为double型，也只能计算出Fibonacci数列前46项的值，也就是求和数列前45项的和值。如果采用double型变量存储中间结果，由于Fibonacci数列的指数级增长，到第1476项时，Fibonacci数列的值已超出double型变量的存储范围。也就是说只能计算出求和数列前1474项的和值。解决这个问题的思路有两个：一个是用数组存储Fibonacci数列的中间计算结果，要解决的是大数加法、除法问题。这个思路计算量大，效率低下。第二个思路就是从数学理论上分析这个看似简单的求和数列，找出计算和值的递推公式，然后迭代或循环求值。Fibonacci数列的通项公式为(f(1) = 1, f(2) = 1) f(n) = ( ((1+sqrt(5))/2)^n + (( 1+sqrt(5) )/2)^n )/sqrt(5)，从该式我们可以求出f(n)/f(n+1) = 2*( 1 - ( (sqrt(5)-3)/2 )^n )/( 1+sqrt(5) - (1-sqrt(5))*( (sqrt(5)-3)/2 )^n )，即为求和数列的一般通项公式。当n趋向于无穷大是，f(n)/f(n+1) = (1+sqrt(5))/2（黄金分割值）。这样就消除了计算机变量存储范围的限制，当n到一定值时，通项值趋于理论极限，可以化复杂计算为简单的加法运算，当n值特别大时可以用一次简单的乘法运算即可解决。示例代码及运行示例如下：
程序代码：(C语言实现)

#include <stdio.h>
#include <math.h>
#define N 200
double fun_1( int );
void main( void )
{
int n;
double sum = 0.0;
for ( n = 1; n < N+1; n++ )
{
  sum += ( 1-fun_1(n) )/( 1+sqrt(5) - (1-sqrt(5))*fun_1(n) )*2;
  printf("前%-5d项和是%-20.15lf程序计算增量为%-20.15lf", n, sum, ( 1-fun_1(n) )/( 1+sqrt(5) - (1-sqrt(5))*fun_1(n) )*2);
  printf("理论极限增量为%-20.15lf\n", ( sqrt(5) - 1 )/2);
}
}
double fun_1( int n )
{
int i;
double p = 1.0;
for ( i = 0; i < n; i++ ) p *= ( sqrt(5)-3 )/2;
return p;
}

作者: 5毛党党员 时间: 2008-09-27 09:52
呵呵这个已经从算法问题变成归纳数学公式了

作者: xwolff 时间: 2008-09-27 10:01
标题: 运行示例
前30 项和是18.840600687172167  程序计算增量为0.618033988749648 理论极限增量为0.618033988749895
前31 项和是19.458634675922156  程序计算增量为0.618033988749989 理论极限增量为0.618033988749895
前32 项和是20.076668664672013  程序计算增量为0.618033988749859 理论极限增量为0.618033988749895
前33 项和是20.694702653421921  程序计算增量为0.618033988749909 理论极限增量为0.618033988749895
前34 项和是21.312736642171810  程序计算增量为0.618033988749890 理论极限增量为0.618033988749895
前35 项和是21.930770630921707  程序计算增量为0.618033988749897 理论极限增量为0.618033988749895
前36 项和是22.548804619671600  程序计算增量为0.618033988749894 理论极限增量为0.618033988749895
前37 项和是23.166838608421497  程序计算增量为0.618033988749895 理论极限增量为0.618033988749895
从运行结果可以看出，当n大于等于38时通项已等于理论极限值，因而可以大大减少计算量，提高效率。改进后代码如下：
#include <stdio.h>
#include <math.h>
#define N 20000000
double fun_1( int );
void main( void )
{
int n;
double sum = 0.0;
double t;

for ( n = 1; n < 37; n++ )
{
  t = ( 1-fun_1(n) )/( 1+sqrt(5) - (1-sqrt(5))*fun_1(n) )*2;
  sum += t;


}
if ( N >= 37 ) sum += (N-36)*(sqrt(5)-1)/2;
printf(" 前%-6d项和为：%-20.15lf\n", N, sum);
}
double fun_1( int n )
{
int i;
double p = 1.0;
for ( i = 0; i < n; i++ ) p *= ( sqrt(5)-3 )/2;
return p;
}

运行示例：
前20000000项和为：12360680.074578924000000

作者: xwolff 时间: 2008-09-27 10:05
标题: 回复 #2 5毛党党员的帖子
算法本身就是数学问题，能用数学解决的就自己用数学解决，实在解决不了的再交给计算机去解决。当n值在1500以上时我真的想不出更高效的算法思路...

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)