笔试题中考到：斐波那契数列的快速实现方法
如题！
望大家指教 谢谢
[解决办法]
利用特征方程
线性递推数列的特征方程为：
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
则F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2
C1*X1^2 + C2*X2^2
解得C1=1/√5，C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】
方法二:
考虑矩阵?A
1 1
0 1,
你求A^n试试
方法三:
递归(非常慢)
方法四:
用两个数a,b,然后一个for循环,你懂的
[解决办法]
#include <stdio.h>
unsigned int fib(unsigned int x)
{
if (x <= 1)
return x;
return fib(x - 1) + fib(x - 2);
}
int main(int argc, char *argv[])
{
unsigned i;
for (i = 0; i <= 20; i++)
printf("%u ", fib(i));
printf("\n");
return 0;
}
long long fib(unsigned int n, long long acc1, long long acc2)
{
if(n == 0)
return acc2;
return fib(n-1, acc1+acc2, acc1);
}
long long Fibonacci(unsigned int n)
{
long long fibNMinusOne = 1;
long long fibNMinusTwo = 0;
long long fibN = 0;
unsigned int i = 0;
if(n < 2)
return n;
for(i=2; i<=n; ++i)
{
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}
