剣指offer面接問題9——階段を跳ぶ(非ロネ数列)

タイトル1388:階段を跳ぶ
時間制限:1秒
メモリ制限:32メガ
特殊問題:いいえ
提出:3487
解決:1406
タイトルの説明:
1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
 
入力:
入力には、各テストケースについて、複数のテストケースが含まれる場合があります.
入力は整数n(1<=n<=70)を含む.
 
出力:
各テストケースに対応し、
出力カエルがn段の階段を飛び上がるのに何種類の飛び方があるのか.
 
サンプル入力:

5

サンプル出力:

8

質疑応答:
問題を解くのに問題がありますか.解題の心得を分かち合いますか?このトピックについては、次のトピックを参照してください.
http://t.jobdu.com/thread-8111-1-1.html
この問題は最初は非ロネ数列とは思わなかったが,直接硬算すると,1ステップをx,2ステップをyとする.プロセス中、x+2 y=n、y値をとるとCx、n=n!x!*(n-x)!
でもきっとだめだよ.

#include<iostream>

using namespace std;



long long int Njiecheng(long long int n)

{

	if(n==0)

		return 1;

	long long int a=1;

	for(long long int i=0;i<n;i++)

		a=a*(i+1);

	return a;

}

long long int CN_N(long long int n,long long int x)

{

	long long int last;

	last=Njiecheng(n)/(Njiecheng(x)*Njiecheng(n-x));

	return last;

}

long long int IntToInt(long long int a)

{

	if(a==1)

		return 1;



	long long int x=0;

	long long int y=0;

	long long int last=0;

	for(long long int i=0;i<=a/2;i++)

	{

		x=a-2*i;

		y=i;

		last=last+CN_N(x+y,x);

	}

	return last;

}

int main()

{

	long long int n;

	while(cin>>n)

		cout<<IntToInt(n)<<endl;

	return 0;

}

次にフィロつま数列を採用しますが、構築時に最も簡単な再帰方法を採用しました.このようにデータが大きくなったら非常に遅く、時間の複雑さが大きすぎてだめだと気づきました.

#include <iostream>

using namespace std;

typedef long long int LLint;

LLint fi(LLint n)

{

	if(n==1)

		return 1;

	if(n==2)

		return 2;

	return fi(n-1)+fi(n-2);

}

int main()

{

	long long int n;

	while(cin>>n)

		cout<<fi(n)<<endl;

	return 0;

}

低から高までフィロつま数列を計算すべきで、時間の複雑さを大幅に低減することができます

#include <iostream>

using namespace std;

typedef long long int LLint;

int main()

{

    int n;

    while(cin>>n)

    {

        if(n==1||n==2)

            {

                cout<<n<<endl;

                continue;

        }

        int i=2;

        LLint last1=1;

        LLint last2=2;

        LLint last=0;

        while(i<n)

        {

            last=last1+last2;

            i++;

            last1=last2;

            last2=last;

        }

        cout<<last<<endl;

    }

    return 0;

}

/**************************************************************

    Problem: 1388

    User:  12138

    Language: C++

    Result: Accepted

    Time:10 ms

    Memory:1520 kb

****************************************************************/