定义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;
}