【剣指offer】変態ジャンプステップ

1652 ワード
FF
転載は出典を明記してください.http://blog.csdn.net/ns_code/articale/detail/25367797
    フィボナッチのシーケンスの変更は、簡単な問題は、OJの9度のテストに合格した.
時間制限:1秒
メモリ制限:32兆
テーマ描写叙述:
カエルは1回だけで1段の階段を上がることができ、2段の階段を上がることができます.この蛙が一つのn級の階段に上がることを求めて、全部で何種類のジャンプ法を持ちますか?
入力:
入力には複数のテスト例が含まれています.各テストケースに対して、
入力には整数nが含まれています.
出力:
それぞれのテストケースに対応して、
この蛙を出力して、一つの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)+1、f(n-1)=f(n-2)+.+f(1)+1、2つの式子を減らして、f(n)=2 f(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
",Fibonacci(n));
	return 0;
}
/**************************************************************    Problem: 1389    User: mmc_maodun    Language: C    Result: Accepted    Time:0 ms    Memory:912 kb****************************************************************/
MQ初体験