课后作业

第二十五课

1. 一个农业科研机构正在研究一种新型的植物，该植物在特定的生长条件下，他们发现该植物的生长规律是这样的：第一周和第二周每株植物都会产生1个新芽，第三周开始，每周每株植物会产生前两周新芽数量之和的新芽。请编写一个C++程序，计算第N周时每株植物的新芽数量。

// 示例输入：
请输入周数N: 5

// 示例输出：
5

• ❌

• 历史解析

  • 没必要使用数组，而且你的数组声明错了，C++中不允许直接使用运行时输入的值作为标准数组的大小，因为标准数组的大小必须在编译时确定
  • 你的斐波那契数列的迭代实现中，函数部分中判断可以简写
  • 根据题目要求，输出N周时每株植物的新芽数量即可，没必要输出每周的新芽数量

• 参考答案

#include <iostream>
using namespace std;

int main() {
    int N;
    cout << "请输入周数N: ";
    cin >> N;

    if (N == 1 || N == 2) {
        cout << 1 << endl;
        return 0;
    }

    int a = 1, b = 1, c;
    for (int i = 3; i <= N; i++) {
        c = a + b;
        a = b;
        b = c;
    }

    cout << c << endl;
    return 0;
}

2. 假设有一系列数字序列a_n满足：

a₁=1
a₂=2
a_n=a_n-1 * (n+1) - a_n-2 * n

请编写一个C++程序，计算并输出前10个序列a_n的值

// 示例输入：
// 无，直接运算打印前10个序列即可

// 示例输出：
序列的前 10 项是：
a_1 = 1
a_2 = 2
a_3 = 5
a_4 = 17
a_5 = 77
a_6 = 437
a_7 = 2957
a_8 = 23117
a_9 = 204557
a_10 = 2018957

• ✅
• 历史解析
  • 整体思路正确，对于已知递推关系的情况下，使用递归快速实现，没有问题💯

3.现有一个特殊的二项式系数问题，其递推公式为：

T(n, k) = T(n-1, k) + T(n-1, k-1) + T(n-1, k-2)

其中初始条件为 T(n, 0) = T(n, n) = 1 以及当 k < 0 或 k > n时T(n, k) = 0

请设计一个递推算法来计算这个特殊二项式系数 T(n, k) 的值

// 示例输入：
请输入 n 和 k 的值：5 2

// 示例输出：
T(5, 2) = 13

• ❌

• 历史解析

  • 你的输出T(n, k)的值是错误的，应该是T(5, 2) = 13，而不是T(5, 2) = -2147451070
  • 代码没有处理 k < 0 或 k > n 的情况，当 k < 0 或 k > n 时，T(n, k) = 0
  • 没有充分考虑到边界条件,dp[i][j - 2] 可能会导致数组越界,当 j < 2 时，dp[i][j - 2] 访问的是非法内存
  • int dp[n + 1][n + 1];这种方式初始化二维数组是非法的，因为编译器无法在栈上初始化变长数组，应该使用vector来创建动态数组

• 参考答案

#include <iostream>
#include <vector>

using namespace std;

// 记忆化数组，用于存储已经计算过的值，因为递归会有很多重复计算
vector<vector<int>> memo;

int specialBinomialCoefficient(int n, int k) {
    // 处理初始条件
    if (k < 0 || k > n) return 0;
    if (k == 0 || k == n) return 1;
    
    // 如果值已经计算过，直接返回
    if (memo[n][k] != -1) return memo[n][k];
    
    // 使用递推公式计算并存储值
    memo[n][k] = specialBinomialCoefficient(n - 1, k) + 
                 specialBinomialCoefficient(n - 1, k - 1) + 
                 specialBinomialCoefficient(n - 1, k - 2);
    
    return memo[n][k];
}

int main() {
    int n, k;
    cout << "请输入 n 和 k 的值：";
    cin >> n >> k;
    
    // 初始化记忆化数组
    memo = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
    
    int result = specialBinomialCoefficient(n, k);
    cout << "T(" << n << ", " << k << ") = " << result << endl;
    
    return 0;
}