斐波那契数列

Posted on | In | Comments: | Views: 
1
2
3
4
5
6
7
8
9
10
11
12
//时间复杂度O(N)  空间复杂度O(1)
long long fib(int n)
{
	long long fibarry[3] = { 0, 1, 0 };
	for (int i = 2; i <= n; i++)
	{
		fibarry[2] = fibarry[0] + fibarry[1];
		fibarry[0] = fibarry[1];
		fibarry[1] = fibarry[2];
	}
	return fibarry[2];
 }
1
2
3
4
5
6
7
8
9
//递归实现
long long fib(int n)
{
	if (n =1 || n== 2)
	{
		return 1;
	}
	return (fib(n - 2) + fib(n - 1));
}