- 论坛徽章:
- 0
|
昨天看到一个网友发帖子计算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;
} |
|
免费注册
发表于 2008-09-27 09:31
