最后修改于2008-2-12 16:54:00

  最后修改于2008-2-13 14:56:00

引用：

To SonicLing

Where did I need max(n)?

Will you please shut-up your garbage???

Thanks!

PS. I will stop arguing on this thread, it is just wasting my time to argue with people who know-nothing but pretend knowing everything...

I quit!

引用：

我试过了，你满意了

n=1000000，就可以把内存吃得卡不动了，1分多钟没有反应；这不是语言的问题。

  最后修改于2008-2-13 15:23:00

引用：

Nobody needs to do fib in your job, if you really need, call a math library.

  最后修改于2008-2-13 16:10:00

引用：

#include <stdio.h>

unsigned long long fib[200]={0, 1, 1};

unsigned long long Fibonacci(unsigned n)
{
    unsigned a, b;
    if (fib[n]) return fib[n];
    b = (a=n>>1) + (n&1);
    return fib[n]=Fibonacci(a)*Fibonacci(b-1) + Fibonacci(a+1)*Fibonacci(b);
}

int main(void)
{
    unsigned n;
    scanf("%u", &n);
    printf("%llu\n", Fibonacci(n));
    return 0;
}

引用：

引用：

#include <stdio.h>

unsigned long long fib[200]={0, 1, 1};

unsigned long long Fibonacci(unsigned n)
{
    unsigned a, b;
    if (fib[n]) return fib[n];
    b = (a=n>>1) + (n&1);
    return fib[n]=Fibonacci(a)*Fibonacci(b-1) + Fibonacci(a+1)*Fibonacci(b);
}

int main(void)
{
    unsigned n;
    scanf("%u", &n);
    printf("%llu\n", Fibonacci(n));
    return 0;
}

这个方法是正确的吗?

引用：

有没有人注意到我在１０楼所回复的？再贴一遍
分成两个接近的数（差１），近似于二分计算

#include <stdio.h>

unsigned long long fib[200]={0, 1, 1};

unsigned long long Fibonacci(unsigned n)
{
    unsigned a, b;
    if (fib[n]) return fib[n];
    b = (a=n>>1) + (n&1);
    return fib[n]=Fibonacci(a)*Fibonacci(b-1) + Fibonacci(a+1)*Fibonacci(b);
}

int main(void)
{
    unsigned n;
    scanf("%u", &n);
    printf("%llu\n", Fibonacci(n));
    return 0;
}

  最后修改于2008-2-16 13:22:00

引用：

Q. How to calculate big number (such as 1000000) fibonacci number in O(log(n)) time without using out all the memory, and not causing stack overflow?

A: This algorithm is provided by MasterRaySoul

Its correctness can be easily proved by induction. The time complexity is O(log(n)). 

The original code was in C, and had space complexity of O(n), because the huge nature of fibonacci number, it will run out of memory very fast. 

Now, I combined the algorithm with Andrew Johnson's memory on demand Hash implemetation, space complexity is also reduced to O(log(n)), made fib[1000000] without stack overflow and no memory problem either. 

Here is the code. Enjoy!

fib_d = Hash.new{ |h, n| 
  if (n<2) 
    h[n] = n
  elsif n == 2
    h[n]=1
  else
    a = n/2
    b = a + n%2
    h[n] = h[a]*h[b-1] + h[a+1]*h[b]
  end
}
puts fib_d[1000000]

  最后修改于2008-2-16 14:17:00

  最后修改于2008-2-16 14:18:00