解析：阅读程序-2

问题描述

这段代码解决的是经典的扔鸡蛋问题。假设有一栋 n 层楼和 m 个鸡蛋，我们想知道最少需要扔几次鸡蛋，才能确定鸡蛋从哪一层楼扔下去会刚好碎。

算法实现

代码中给出了两种解决方法：递归和递推（动态规划）。

递归方法 f(n, m)

• 思路:
  • 对于每一层楼，我们可以选择从这一层扔鸡蛋。
  • 如果鸡蛋碎了，就继续在下面的楼层中找临界点。
  • 如果鸡蛋没碎，就在上面的楼层中继续找临界点。
  • 对所有可能的选择取最小值。
• 状态转移方程:f(n, m) = min(max(f(n-i, m), f(i-1, m-1)) + 1) for 1 <= i <= n
  • f(n, m) 表示对于 n 层楼和 m 个鸡蛋的最少扔鸡蛋次数。
  • max(f(n-i, m), f(i-1, m-1)) 表示在第 i 层扔鸡蛋后，两种情况（鸡蛋碎或没碎）下的最坏情况。
  • +1 表示当前这一次扔鸡蛋。
• 边界条件:
  • m == 1: 只能线性搜索，最坏情况需要扔 n 次。
  • n == 0: 没有楼层，不需要扔鸡蛋。

递推方法 g(n, m)

• 思路:
  • 使用二维数组 h[n][m] 来存储子问题的解。
  • 从小规模的子问题开始计算，逐步推导出大规模问题的解。
• 状态转移方程: 与递归方法相同。
• 边界条件:
  • h[i][1] = i: 只有一个鸡蛋时，只能线性搜索。
  • h[0][j] = 0: 没有楼层时，不需要扔鸡蛋。

代码解读

• MAXN 和 MAXK: 定义了楼层数和鸡蛋数的最大值。
• h[MAXN][MAXK]: 用于存储子问题的解，在递推方法中使用。
• f(n, m): 递归函数，实现递归解法。
• g(n, m): 递推函数，实现动态规划解法。
• main 函数: 读取输入的楼层数和鸡蛋数，调用两个函数并输出结果。

算法分析

• 时间复杂度:
  • 递归方法：由于存在大量的重复计算，时间复杂度较高，接近指数级。
  • 递推方法：通过动态规划，将时间复杂度降低到了 O(n * m)。
• 空间复杂度:
  • 递归方法：空间复杂度与递归深度有关。
  • 递推方法：需要一个二维数组来存储子问题的解，空间复杂度为 O(n * m)。

总结

动态规划方法通过存储子问题的解，避免了重复计算，显著提高了算法的效率。在解决这类问题时，动态规划是一种常用的且高效的方法。

代码分析：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

/**************************************************************** 
 * Description: 2022_CSP_R2
 * Author: Alex Li
 * Date: 2023-05-21 16:55:11
 * LastEditTime: 2024-09-14 21:24:06
****************************************************************/
#include <algorithm>
#include <iostream>
#include <limits>

using namespace std;

const int MAXN = 105;  // 定义问题中可能的最大楼层数
const int MAXK = 105;  // 定义问题中可能的最大鸡蛋数

int h[MAXN][MAXK];  // h数组用于存储动态规划中计算的结果

// 递归函数 f 用于求解在有 m 个鸡蛋的情况下，最坏情况下从 n 层楼中找到临界楼层所需的最少尝试次数
int f(int n, int m)
{
    if(m == 1) return n;  // 如果只有一个鸡蛋，最坏情况下需要从第1层开始一层层往上试
    if(n == 0) return 0;  // 如果没有楼层，则不需要任何尝试

    int ret = numeric_limits<int>::max();  // 初始化为一个很大的值，用于求最小值
    // 遍历从第 i 层扔鸡蛋的所有可能情况
    for (int i = 1; i <= n; i++)
       // 递归计算: 在第 i 层扔鸡蛋后，如果鸡蛋破了，问题转为在 i-1 层用 m-1 个鸡蛋继续尝试；
       // 如果没破，问题转为在 n-i 层继续用 m 个鸡蛋尝试。取两者最大值表示最坏情况。
       ret = min(ret, max(f(n-i, m), f(i-1, m-1)) + 1);  
    return ret;  // 返回最小的尝试次数
}

// 动态规划函数 g 用于用动态规划的方法求解相同问题
int g(int n, int m){
    // 初始化，只有一个鸡蛋的情况下，最坏情况下需要从第一层开始逐层尝试
    for (int i = 1; i <= n; i++)
        h[i][1] = i;
    // 初始化，若楼层为0层，则不需要任何尝试
    for (int j = 1; j <= m; j++)
        h[0][j] = 0;
    
    // 开始填充 h 表，对于每个楼层数 i 和鸡蛋数 j 的组合
    for (int i = 1; i <= n; i++){
        for (int j = 2; j <= m; j++){
            h[i][j] = numeric_limits<int>::max();  // 初始化为一个很大的值，用于求最小值
            // 遍历在第 k 层扔鸡蛋的所有可能情况
            for(int k = 1; k <= i; k++)
                // 动态规划的转移方程，与递归类似
                h[i][j] = min(h[i][j], max(h[i-k][j], h[k-1][j-1]) + 1);
        }
    }
    return h[n][m];  // 返回最少的尝试次数
}

int main(){
    int n, m;
    cin >> n >> m;  // 输入楼层数 n 和鸡蛋数 m
    // 输出递归法和动态规划法的结果
    cout << f(n, m) << endl << g(n, m) << endl << endl;
    return 0;
}
/* 
代码分析：
1. 这个问题是一个经典的“鸡蛋掉落”问题，目的是在最坏情况下，使用 m 个鸡蛋在 n 层楼中找到临界楼层，
即从该层往上扔鸡蛋会碎，从该层往下扔鸡蛋不会碎。目标是最小化最坏情况下的尝试次数。
2. 函数 f 使用递归的方法进行求解，函数 g 则通过动态规划进行求解，避免了递归中的重复计算。
3. 两个函数的核心思想都是通过在某一层楼扔鸡蛋，计算最坏情况下需要的尝试次数，并取最小的最坏情况。
4. 动态规划比递归效率更高，因为它避免了重复计算，直接利用了已经求得的子问题的解。
*/

关于limits

头文件#cinclude <limits>和第17行ret=numeric_limits<int>::max();
是为了获得整型int的最大值给到ret变量。

问题一：当输入为“7 3”时，第 19 行用来取最小值的 min 函数执行了 449 次。

下表为f(n, m)函数在不同参数下，对应min函数执行的次数。用f_m(n, m)表示。

f_m(6,2)=6+f(5,2)+f(4,2)+f(3,2)+f(2,2)+f(1,2)=6+31+15+7+3+1=63
f_m(3,3)=3+f(2,3)+f(1,3)+f(1,2)+f(2,2)=3+4+1+1+3=12
f_m(7,3)=7+f(6,3)+f(0,2)+f(5,3)+f(1,2)+f(4,3)+f(2,2)+f(3,3)+f(3,2)+f(2,3)+f(4,2)+f(1,3)+f(5,2)+f(0,3)+f(6,2)
=7+192+0+80+1+32+3+12+7+4+15+1+31+0+63=448

问题二：输出的两行整数总是相同的。

f()函数是递归函数，g()函数是递推函数，实现的功能是一样的。递归和递推可以认为是一种逆运算。

问题三：当 m 为 1 时，输出的第一行总为 n。

根据f()函数和g()函数的代码，当m=1时，输出n

问题四：g(n,m) 最为准确的时间复杂度分析结果为（ ）。

在g()函数里，有三个for循环，一个和m有关，一个和n有关，所以最后是O(n^2m)

问题五：当输入为“20 2”时，输出的第一行为（ ）。

for (int i = 1; i <= n; i++)
f(n,m)=ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);

for (int i= 1; i <= n; i++){
         for (int j= 2; j <= m; j++){
             h[i][j] = numeric_limits<int>::max();
             for (int k = 1;k <= i;k++)
             h[i][j]= min(h[i][j],max(h[i - k][j],h[k - 1][j - 1]) +1);
         }

f(20,2)
i=1, ret=min(ret, max(f(19,2), f(0,1))+1)=min(ret,max(6, 0)+1)=7
i=2, ret=min(ret, max(f(18,2), f(1,1))+1)=min(7, max(6, 1)+1)=7
i=3, ret=min(ret, max(f(17,2), f(2,1))+1)=min(7, max(6, 2)+1)=7
i=4, ret=min(ret, max(f(16,2), f(3,1))+1)=min(7, max(6, 3)+1)=7
i=5, ret=min(ret, max(f(15,2), f(4,1))+1)=min(7, max(5, 4)+1)=6
i=6, ret=min(ret, max(f(14,2), f(5,1))+1)=min(6, max(5, 5)+1)=6
i=7, ret=min(ret, max(f(13,2), f(6,1))+1)=min(6, max(5, 6)+1)=6
i=8, ret=min(ret, max(f(12,2), f(7,1))+1)=min(6, max(5, 7)+1)=6
i=9, ret=min(ret, max(f(18,2), f(1,1))+1)=min(6, max(6, 8)+1)=6
…………..ret都是6
i=20, ret=min(ret, max(f(0,2), f(19,1))+1)=min(6, max(0, 19)+1)=6

问题六：当输入为“100 100”时，输出的第一行为（ ）。

参见动态规划之扔鸡蛋问题