祺哥刷题日记(五)数楼梯

题目 P1255 数楼梯

题目描述

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

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

输入格式

一个数字,楼梯数。

输出格式

输出走的方式总数。

输入输出样例

  • 输入
4
  • 输出
5

说明/提示

  • 对于 60 % 60\% 60% 的数据, N ≤ 50 N \leq 50 N50
  • 对于 100 % 100\% 100% 的数据, N ≤ 5000 N \leq 5000 N5000

题解过程

通过观察法可以得到 f ( x ) = f ( x − 1 ) + f ( x − 2 ) f(x) = f(x-1) + f(x-2) f(x)=f(x1)+f(x2),经典斐波那契数列题目,从小于等于5000就能看出这题不能用递归,而且要使用高精加法,不过下面还是依次尝试了各个方法。

1. 递归解法(超时)

代码如下:

#include

int stepUp(int num){
    if(num == 1) return 1;
    if(num == 0) return 0;
    else return stepUp(num - 1) + 1 + stepUp(num - 2) + 1; 
}

int main(){
    int n;
    scanf("%d", &n);
    printf("%d", stepUp(n));
}

祺哥刷题日记(五)数楼梯_第1张图片

2. 递推法 (溢出)

#include

int main(){
    int n;
    long long step[3] = {1,2,3};
    scanf("%d", &n);
    if(n == 0 || n == 1 || n == 2) printf("%d", n);
    else{
        for(int i = 3; i < n; i++){
            step[0] = step[1];
            step[1] = step[2];
            step[2] = step[0] + step[1];
        }
        printf("%lld", step[2]);
    }
}

祺哥刷题日记(五)数楼梯_第2张图片

从这里其实可以看出来递推已经不会超时了,WA是因为溢出(这里用了long long,所以必须使用高精度加法)

3. 递推+高精(AC)

#include
#include

using namespace std;

string highAccAdd(string a, string b){
    string res;
    int lenA = a.size();
    int lenB = b.size();

    //补0
    if(lenA < lenB){
        for(int i = lenA; i < lenB; i++){
            a = "0" + a;
        }
    }    
    else{
        for(int i = lenB; i < lenA; i++){
            b = "0" + a;
        }
    }

    int len = max(lenA, lenB);
    int c = 0;
    int temp;
    for(int i = len - 1; i >=0; i--){
        temp = a[i] - '0' + b[i] - '0' + c;
        c = temp / 10;
        temp = temp % 10;
        res = char(temp + '0') + res;
    }
    if(c != 0) res = char(c + '0') + res;
    return res;
}

int main(){
    int n;
    string step[3] = {"1","2","3"};
    scanf("%d", &n);
    if(n == 0 || n == 1 || n == 2) printf("%d", n);
    else{
        for(int i = 3; i < n; i++){
            step[0] = step[1];
            step[1] = step[2];
            step[2] = highAccAdd(step[0], step[1]);
        }
        cout << step[2];
    }
}

祺哥刷题日记(五)数楼梯_第3张图片

总结

这道题总体难度不大,还是要加强高精度运算的板子熟练度。

你可能感兴趣的