b***k
发帖数: 2673 | 1 ☆─────────────────────────────────────☆
crazystones (黑皮) 于 (Thu Mar 13 22:38:26 2008) 提到:
Consider the following C program for producing Fibonacci numbers:
int Fibonacci(int n)
{
if (n <= 0 || n == 1)
return 1;
else
return Fibonacci(n-1)+Fibonacci(n-2);
}
If for some large n, it takes 100 seconds to compute Fibonacci(n), how long
will it take to compute Fibonacci(n+1), to the nearest second?
☆─────────────────────────────────────☆
karon (卡龙) 于 (Thu Mar 13 22:47 | s*******e
发帖数: 432 | 2 T(n) = T(n-1) + T(n-2)--->
T(n)/T(n-1) = 1 + 1/(T(n-1)/T(n-2));
define Rn= T(n)/T(n-1)
Rn= 1 + 1/R(n-1)
Notice the limit exist=x
so one solve the following equation and pick the larger than 1 one:
x = 1 + 1/x
x= 1/2(1 + sqrt(5)) |
|
