HUST程序设计竞赛(新生赛)-同步赛-Q-小乐乐走台阶

题目描述
小乐乐上课需要走n阶台阶，因为他腿比较长，所以每次可以选择走一阶或者走两阶，那么他一共有多少种走法？
输入描述:
输入包含一个整数n (1 ≤ n ≤ 30)
输出描述:
输出一个整数，即小乐乐可以走的方法数。

因为走到第三个楼梯的时候可以从第一阶和第二阶直接走上来

同理，第四个楼梯的时候可以从第二阶和第三阶直接走上来

第五个楼梯的时候可以从第三阶和第四阶直接走上来
… …

所以可以得出公式

a[i]=a[i-1]+a[i-2]

特判a[0][1]=0a[1[1]=1,a[2][1]=1

可以得出结论这是一个斐波那契数列

因为数据比较水(1 ≤ n ≤ 30)

所以可以打表A题

下面是打表代码

#include <iostream>

using namespace std;

int fib(int n)
{
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

int main()
{
    int i;
    cout << "a[31] = {0";
    for (i = 1; i <= 30; i++)
        cout  << ", "<< fib(i);
    cout << "};";
    return 0;
}

下面是使用打表数据的代码

# include <iostream>
using namespace std;
int main()
{
    int a[31] = {1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269};
    int n;
    cin >> n;
    cout << a[n];
    return 0;
}