【劍指offer】變态跳台階

轉載請注明出處：http://blog.csdn.net/ns_code/article/details/25367797

    斐波那契序列的變種，簡單題，在九度OJ上測試通過。

時間限制：1 秒

記憶體限制：32 兆

題目描述：

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

輸入：

輸入可能包含多個測試樣例，對于每個測試案例，

輸入包括一個整數n(1<=n<=50)。

輸出：

對應每個測試案例，

輸出該青蛙跳上一個n級的台階總共有多少種跳法。

樣例輸入：

6      

樣例輸出：

32      

    思路：

    先大緻分析下，假設跳上第n個台階有f(n)種方法，則f(1)=1,f(2)=2,f(3)=4,f(4)=8,我們隐約感覺到f(n)=2^(n-1)。但是需要證明下，同樣根據我們根據上篇文章中跳台階的思路，可以得到f(n)=f(n-1)+f(n-2)+....+f(1)+1,而f(n-1)=f(n-2)+....+f(1)+1,兩個式子相減，得到f(n) = 2f(n-1),很明顯可以得到f(n)=2^(n-1)。

    AC代碼如下：

#include<stdio.h>

long long Fibonacci(unsigned int n)
{
	if(n <= 0)
		return 0;
	if(n==1)
		return 1;
	long long FibN = 1;
	unsigned int i;
	for(i=2;i<=n;i++)
	{
		FibN *= 2;
	}
	return FibN;
}

int main()
{
	unsigned int n;
	while(scanf("%d",&n) != EOF)
		printf("%lld\n",Fibonacci(n));
	return 0;
}