P1255 数楼梯

题目描述

楼梯有N阶，上楼可以一步上一阶，也可以一步上二阶。

编一个程序，计算共有多少种不同的走法。

输入输出格式

输入格式：

一个数字，楼梯数。

输出格式：

走的方式几种。

输入输出样例

输入样例#1：

4

输出样例#1：

5

说明

用递归会太慢，需用递推

（60% N<=50 ,100% N<=5000)

思路:

　　题目中说明中提及递归太慢,所以用递推做的.但是又因为范围是到5000,范围太大,所以需要用高精来做.

坑点:

　　斐波那契第0项的值为0,是根据题目的意思来判断的.

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

const int M = ;

int n;

string f[M];

string J(string aa,string bb)

{

    if(aa.length()<bb.length())

    {

        string tmp=aa;

        aa=bb;

        bb=tmp;

    }

    int i,j;

    for(i=aa.length()-,j=bb.length()-;i>=;i--,j--)

    {

        aa[i]=char(aa[i] + ( j >=  ? bb[j]-'' : ));

        if(aa[i]-''>=)

        {

            aa[i]=char((aa[i]-'')%+'');

            if(i) aa[i-]++;

            else aa=''+aa;

        }

    }

    return aa;

}

int main()

{

    int j=;

    scanf("%d",&n);

    f[]='';

    f[]='';

    f[]='';

    while(j<=n)

    {

        f[j]=J(f[j-],f[j-]);

        j++;

    }

    cout<<f[n];

    return ;

}

End.

luoguP1255 数楼梯 x的相关教程结束。