定义Fibonacci数列如下: / 0 n=0 f(n)= 1 n=1 \ f(n-1)+f(n-2) n=2 输入n,用最快的方法求该数列的第n项。

时间:2022-01-02 22:38:04

定义Fibonacci数列如下:  
  / 0 n=0
f(n)= 1 n=1
  \ f(n-1)+f(n-2) n=2

输入n,用最快的方法求该数列的第n项。


unsigned int Fibonacci(unsigned int n)

{

    if (n == 0) return 0;

    if (n == 1) return 1;

    unsigned int odd, even;

    odd = 1;

    even = 0;


    while (--n > 1) {

        if (n & 0x1)

            odd+= even;

        else

            even+= odd;

    }

    return even + odd;

}