斐波纳契数

/****************************************************
题目：写一个函数，输入n，求斐波那契数列的第n项。
斐波那契数列的定义如下：
		0			  n=0
f(n) =  1			  n=1
	   f(n-1)+f(n-2)  n>1
****************************************************/
/*
//效率低下的解法
long long fibonacci(unsigned int n)
{
	if(n<=0)
		return0;
	if(n=1)
		return 1;
	else
		return fibonacci(n-1)+fibonacci(n-2);
}
效率低下是因为在求解过程中，会重复求解相同的数字。用二叉树表示如下
			f(10)
		   /              f(9)    f(8)
		/    \   /   	   f(8)	f(7)F(7) F(6)
*/
#include<iostream>
using namespace std;
long long fibonacci(unsigned int n)
{
	if(n==0)
		return 0;
	if(n==1)
		return 1;

	long long fibNMinusOne = 0;
	long long fibNMinusTwo = 1;
	long long fibN = 0;
	for(unsigned int i=2;i<=n; ++i)
	{
		fibN = fibNMinusOne + fibNMinusTwo;
		fibNMinusOne = fibNMinusTwo;
		fibNMinusTwo = fibN;
	}
	return fibN;
}
//f(10)
void test1()
{
	long long f = fibonacci(10);
	cout<<f<<endl;
}
//f(1)
void test2()
{
	long long f = fibonacci(1);
	cout<<f<<endl;
}
//f(0)
void test3()
{
	long long f = fibonacci(0);
	cout<<f<<endl;
}
int main()
{
	test1();
	test2();
	test3();
	return 0;
}

上面的改进办法是从下往上计算，首先根据f(0)和f(1)计算出f(2),再根据
f(1)和f(2)计算出f(3)....以此类推就可以计算出f(n),时间复杂度为O(n).
类似的题目：
1：一直青蛙因此可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级
台阶总共有多少中办法？
扩展：如果条件改为一直青蛙可以跳上1级，也可以2级，也可以3级....也可
以n级，此时青蛙跳上一个n级的台阶总共有多少种跳法？可以用数学归纳法证、
明f(n) = 2^(n-1)
2.我们可以用2*1的小矩形或者竖着去覆盖更大的矩形。请问用8个2*1的小矩形
无重叠覆盖一个2*8的大矩形，总共有多少种方法？

斐波纳契数,布布扣,bubuko.com

斐波纳契数

原文：http://blog.csdn.net/walkerkalr/article/details/20561953