题目描述

一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。

输入格式
共一行，包含一个整数 n。

输出格式
共一行，包含一个整数，表示方案数。

数据范围
1≤n≤15

样例

输入样例：
5
输出样例：
8

算法1

先列举前面几项，找出规律

发现是斐波那契数列

C++ 代码

#include <iostream>

using namespace std;

int a(int n)
{
    if (n==1)
    return 1;
    else if (n==2)
    return 2;
    else
    return a(n-2)+a(n-1);
}
int main()
{
    int n;
    cin>>n;
    cout<<a(n);
}

算法2

先打个草稿，画树找下规律

此类题采用枚举法+递归法(需自己输入开头的常数)+全局变量+函数调用

C++ 代码

#include <iostream>

using namespace std;

int n;
int res;

void a(int k)
{
    if (k==n)
    res++;
    else if (k<n)
    {
        a(k+1);
        a(k+2);
    }
}
int main()
{
    cin>>n;
    a(0);
    cout<<res;
}