如果计算机计算1+1得出的结果是3,那么你们的算法就全错了

[quote]#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;
}[/quote]

这个方法是正确的吗?

测试过很多数据，是正确的。

[quote][quote]#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;
}[/quote]

这个方法是正确的吗?[/quote]

没有细细研究，不过fib[n]=Fibonacci(a)*Fibonacci(b-1) + Fibonacci(a+1)*Fibonacci(b);好像是矩阵乘法。

如果把数组去掉，第归改循环，好像就是F数列的矩阵算法，原理差不多。

[quote]
有没有人注意到我在１０楼所回复的？再贴一遍
分成两个接近的数（差１），近似于二分计算
[code=c]
#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;
}
[/code][/quote]


[color=blue][b]To MasterRaySoul:

Your algorithm is correct and excellent, its correctness can be easily proved by induction.

However, your implementation is using array, which uses too much memory.

It will explode just like mine in ruby, criticized by rickone.

I think you should use STL Hash Table to use memory on demand.

I have implemented your algorithm in Ruby, it is fast and easily reached fib(1000000).

Thank you for providing the excellent algorithm. I will credit you on my website for my ruby implementation. 

The link will be provided when it is ready.

Thanks a lot![/b][/color]

Now, it is uploaded

[quote]
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!

[code=c]
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]
[/code]
[/quote]

Copied from 
[url]http://bobcat.webappcabaret.net/javachina/faq/ruby_01.htm#ruby_Q016[/url]

Thanks MasterRaySoul!!!!
[em1][em1][em1]

这贴很邪恶...