P1255 数楼梯【递推+大数】

数楼梯

题目描述

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

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

输入格式

一个数字，楼梯数。

输出格式

输出走的方式总数。

样例 #1

样例输入 #1

4

样例输出 #1

5

提示

• 对于 $60\%$ 的数据，$N\le 50$；
• 对于 $100\%$ 的数据，$1\le N\le 5000$。

问题链接： P1255 数楼梯
问题分析： 递归或地推问题，需要用到大数计算。这里用地推来解决。
参考链接： （略）
题记： （略）

AC的C++语言程序如下：

/* P1255 数楼梯 */

#include <iostream>
#include <cstring>

using namespace std;

const int M = 2000;
char f1[M], f2[M], t[M];

int main()
{
    int n;
    cin >> n;
    if (n == 1) cout << 1;
    else if(n == 2) cout << 2;
    else {
        memset(f1, 0, sizeof f1);
        memset(f2, 0, sizeof f2);
        f1[0] = 1, f2[0] = 2;
        int len = 1;
        for (int i = 3; i <= n; i++) {
            char carry = 0;
            for (int j = 0; j < len; j++) {
                t[j] = f1[j] + f2[j] + carry;
                carry = t[j] / 10;
                t[j] %= 10;
            }
            if (carry) t[len++] = carry;
            memcpy(f1, f2, len);
            memcpy(f2, t, len);
        }
        for (int i = len - 1; i >= 0; i--)
            cout << int(f2[i]);
    }
    cout << endl;
    return 0;
}