1.求楼梯走法数问题。一个楼梯有n个台阶，上楼可以一步上一个台阶，也可以一步上两个台阶。编写一个实验程序求上楼梯共有多少种不同的走法，求n=47时各种解法的执行时间。

对于求楼梯走法数的问题，我们通常会使用动态规划来优化递归解决方案，因为它避免了重复计算。在C++中，我们可以用一个数组`dp`来存储已经计算过的走法数，其中`dp[i]`表示到达第`i`个台阶的不同走法数。以下是一个简单的动态规划程序：

#include <vector>
#include <chrono>

int climbStairs(int n, vector<int>& dp) {
    // 基线条件
    if (n == 0 || n == 1)
        return n;
    // 如果结果已计算，直接返回
    if (dp[n] != -1)
        return dp[n];

    // 递归计算并存储结果
    dp[n] = climbStairs(n - 1, dp) + climbStairs(n - 2, dp);  // 步一步和一步二步上楼
    return dp[n];
}

void experiment(int n) {
    vector<int> dp(n, -1);  // 初始化dp数组，-1表示未计算
    auto start = chrono::high_resolution_clock::now();
    climbStairs(n, dp);
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(end - start).count();
    cout << "当n=" << n << "时，不同走法的数量为: " << dp[n] << ", 执行时间约为: " << duration << " 微秒\n";
}

int main() {
    int n = 47;
    experiment(n);
    return 0;
}

运行此程序时，它将首先计算所有可能的走法，并记录下当n=47时的执行时间。