【题目】
CSP-J 2022 入门级 第一轮 阅读程序（2） 第22-27题
阅读程序
01 #include <algorithm>
02 #include <iostream>
03 #include <limits>
04
05 using namespace std;
06
07 const int MAXN = 105;
08 const int MAXK = 105;
09
10 int h[MAXN][MAXK];
11
12 int f(int n, int m)
13 {
14 if (m == 1) return n;
15 if (n == 0) return 0;
16
17 int ret = numeric_limits<int>::max();
18 for (int i = 1; i <= n; i++)
19 ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
20 return ret;
21 }
22
23 int g(int n, int m)
24 {
25 for (int i = 1; i <= n; i++)
26 h[i][1] = i;
27 for (int j = 1; j <= m; j++)
28 h[0][j] = 0;
29
30 for (int i = 1; i <= n; i++) {
31 for (int j = 2; j <= m; j++) {
32 h[i][j] = numeric_limits<int>::max();
33 for (int k = 1; k <= i; k++)
34 h[i][j] = min(
35 h[i][j],
36 max(h[i - k][j], h[k - 1][j - 1]) + 1);
37 }
38 }
39
40 return h[n][m];
41 }
42
43 int main()
44 {
45 int n, m;
46 cin >> n >> m;
47 cout << f(n, m) << endl << g(n, m) << endl;
48 return 0;
49 }
假设输入的 n 、 m 均是不超过 100 的正整数，完成下面的判断题和单选题：
判断题
22. 当输入为“ 7 3 ”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）
23. 输出的两行整数总是相同的。（ ）
24. 当 m 为 1 时，输出的第一行总为 n 。（ ）
单选题
25. 算法 g(n,m) 最为准确的时间复杂度分析结果为（ ）。
A.
O
(
n
3
2
/
𝑚
)
O(n^{\frac{3}{2}}/𝑚)
O(n23/m)
B.
O
(
n
m
)
O(nm)
O(nm)
C.
O
(
n
2
m
)
O(n^2m)
O(n2m)
D.
O
(
n
m
2
)
O(nm^2)
O(nm2)
26. 当输入为“ 20 2 ”时，输出的第一行为（ ）。
A. “ 4 ”
B. “ 5 ”
C. “ 6 ”
D. “ 20 ”
27. （4 分） 当输入为“ 100 100 ”时，输出的第一行为（ ）。
A. “ 6 ”
B. “ 7 ”
C. “ 8 ”
D. “ 9 ”
【题目考点】
1. 递推/递归 动态规划
2. C++11 numeric_limits
引入<limits>头文件后可以使用
-
numeric_limits<数据类型>::max()返回该数据类型可以表示的最大值 -
numeric_limits<数据类型>::min()返回该数据类型可以表示的最小值 -
numeric_limits<数据类型>::epsilon()返回该数据类型可以区分的两个数值的最小差值（即如果两个数值的差值小于该值，计算机认为这两个数值相等）
【解题思路】
观察代码可知
f函数使用递归算法：
- 递归关系：f(n,m)的值为：i从1循环到n，
max(f(n-i, m), f(i-1, m-1))+1的最小值 - 递归出口：m是1时f(n,m)值为n，n是0时f(n,m)值为0。
g函数使用了递推算法：
- 初始状态：j是1时h[i][j]值为i，i是0时h[i][j]值为0。
- 递推关系：h[i][j]的值为：k从1循环到i，
max(h[i-k][j], h[k-1][j-1])+1的最小值
对比二者，如果把f函数中的n替换为i，m替换为j，i替换为k。递归出口对应递推初始状态，递归关系对应递推关系。递推和递归本就是可以相互转化的两种方法。可以看出二者是解决相同问题的不同方法。
22. 当输入为“ 7 3 ”时，第 19 行用来取最小值的 min 函数执行了 449 次。（ ）
答：错误。
观察f函数，对于一次调用f(n,m)，for循环中内容就要执行n次，也就是说会调用min函数n次。统计所有的递归调用，将n加和即可。
记c(n,m)为f(n, m)运行时min函数的调用次数，为递归调用中min调用次数的加和，再加上f(n,m)中对min的n次调用。
用填表法，实际是递推的方式，从m，n值小的情况逐步推到值大的情况。
| c(n,m) | m=2 | m=3 |
|---|---|---|
| n=1 | c(0,2)+c(0,1)+1=1 | c(0,3)+c(0,2)+1=1 |
| n=2 | c(1,2)+c(0,2)+2=3 | c(1,3)+c(0,3)+c(0,2)+c(1,2)+2=4 |
| n=3 | c(2,2)+c(1,2)+3=7 | c(2,3)+c(1,3)+c(1,2)+c(2,2)+3=12 |
| n=4 | c(3,2)+c(2,2)+c(1,2)+4=15 | c(3,3)+c(2,3)+c(1,3)+c(1,2)+c(2,2)+c(3,2)+4=32 |
| n=5 | c(4,2)+…+c(1,2)+5=31 | c(4,3)+…+c(1,3)+c(1,2)+…+c(4,2)+5=80 |
| n=6 | c(5,2)+…+c(1,2)+6=63 | c(5,3)+…+c(1,3)+c(1,2)+…+c(5,2)+6=192 |
| n=7 | c(6,2)+…+c(1,2)+7=127 | c(6,3)+…+c(1,3)+c(1,2)+…+c(6,2)+7=448 |
其实算几个后就能看出规律了，其中
c
(
n
,
2
)
=
c
(
n
−
1
,
2
)
∗
2
+
1
，
c
(
n
,
3
)
=
2
∗
c
(
n
−
1
,
3
)
+
c
(
n
−
1
,
2
)
+
1
c(n,2)=c(n-1,2)*2+1，c(n,3)=2*c(n-1,3)+c(n-1,2)+1
c(n,2)=c(n−1,2)∗2+1，c(n,3)=2∗c(n−1,3)+c(n−1,2)+1。
得到运行f(7,3)时min的调用次数为448次，不是449次。
23. 输出的两行整数总是相同的。（ ）
答：正确。因为通过观察可知：f函数使用递归，g函数使用递推解决了相同的问题，结果是相同的。
24. 当 m 为 1 时，输出的第一行总为 n 。（ ）
答：正确。递归函数f中，如果m为1，会返回n。递推函数g中，当j为1时，h[i][j]为i。那么返回值h[n][m]一定为n。
25. 算法 g(n,m) 最为准确的时间复杂度分析结果为（ ）。
A.
O
(
n
3
2
/
𝑚
)
O(n^{\frac{3}{2}}/𝑚)
O(n23/m)
B.
O
(
n
m
)
O(nm)
O(nm)
C.
O
(
n
2
m
)
O(n^2m)
O(n2m)
D.
O
(
n
m
2
)
O(nm^2)
O(nm2)
答：选C
第25，26行循环n次，复杂度为O(n)
第27，28行循环m次，复杂度为O(m)
对于第30，31行，谁在内层谁在外层都不影响最内层代码执行的次数。
我们把for(int j = 2; j <= m; ++j)当做外层，这一层近似于循环m次，
对于第33行for(int k = 1; k <= i; ++k)，i是1时循环1次，i是2时循环2次，。。。，i是n时循环n次，那么在j固定时，i从1循环到n，最内层循环体执行次数为：
1
+
2
+
.
.
.
+
n
=
(
1
+
n
)
n
/
2
1+2+...+n=(1+n)n/2
1+2+...+n=(1+n)n/2
总执行次数为
m
⋅
n
(
1
+
n
)
/
2
m\cdot n(1+n)/2
m⋅n(1+n)/2
整段代码的时间复杂度为：
O
(
n
)
+
O
(
m
)
+
O
(
m
⋅
n
(
1
+
n
)
/
2
)
=
O
(
n
2
m
)
O(n)+O(m)+O(m\cdot n(1+n)/2)=O(n^2m)
O(n)+O(m)+O(m⋅n(1+n)/2)=O(n2m)
26. 当输入为“ 20 2 ”时，输出的第一行为（ ）。
A. “ 4 ”
B. “ 5 ”
C. “ 6 ”
D. “ 20 ”
答：选C
模拟运行递推算法g函数，填表表中第i行第j列为h[i][j]的值
j为1时，h[i][j]的值为1。
h[i][j]的值为：k从1循环到i，max(h[i-k][j], h[k-1][j-1])+1的最小值
算过几个后就可以找到规律：j=1这一列从i=0开始从上向下看，j=2这一列从i-1开始从下向上看，对应位置的数值求最大值，看哪一组求得的最大值最大，结果再加1，就是h[i][j]的值。
算出一些数字后，就能发现规律：1个1，2个2，3个3，…，6个6。
| h[i][j] | j=1 | j=2 |
|---|---|---|
| i=0 | 0 | 0 |
| i=1 | 1 | 1 |
| i=2 | 2 | 2 |
| i=3 | 3 | 2 |
| i=4 | 4 | 3 |
| i=5 | 5 | 3 |
| i=6 | 6 | 3 |
| i=7 | 7 | 4 |
| i=8 | 8 | 4 |
| i=9 | 9 | 4 |
| i=10 | 10 | 4 |
| i=11 | 11 | 5 |
| i=12 | 12 | 5 |
| i=13 | 13 | 5 |
| i=14 | 14 | 5 |
| i=15 | 15 | 5 |
| i=16 | 16 | 6 |
| i=17 | 17 | 6 |
| i=18 | 18 | 6 |
| i=19 | 19 | 6 |
| i=20 | 20 | 6 |
得到h[20][2]的值为6。
27. （4 分） 当输入为“ 100 100 ”时，输出的第一行为（ ）。
A. “ 6 ”
B. “ 7 ”
C. “ 8 ”
D. “ 9 ”
答：选B
尝试列出第三列，观察数值的变化规律
| h[i][j] | j=1 | j=2 | j=3 |
|---|---|---|---|
| i=0 | 0 | 0 | 0 |
| i=1 | 1 | 1 | 1 |
| i=2 | 2 | 2 | 2 |
| i=3 | 3 | 2 | 2 |
| i=4 | 4 | 3 | 3 |
| i=5 | 5 | 3 | 3 |
| i=6 | 6 | 3 | 3 |
| i=7 | 7 | 4 | 3 |
| i=8 | 8 | 4 | 4 |
| i=9 | 9 | 4 | 4 |
| i=10 | 10 | 4 | 4 |
| … |
举例：在填h[4][3]时，根据规则，j=2这一列从i=0开始向下看，j=3这一列从i=2开始向上看，先比较h[0][2]和h[3][3]，再分别比较h[1][2]与h[2][3]，h[2][2]与h[1][3]，h[3][2]与h[0][3]，最大值都是2，加1后是3。所以h[4][3]填3。
接下来用相同的方法填h[5][3], h[6][3],h[7][3]都是3。
填h[8][3]时就是4了，思考为什么数值增大了呢？正是因为当填h[8][3]时，j=2这一列i从0到4值是0,1,2,2。j=3这一列i从7到4的值为3,3,3,3，最大值都为3，加1后是4。
设想j=4时，i从0到7，h[i][4]的值与h[i][3]的值都相同，那么从h[8][4]开始，随着i的增大，需要填一些4，那么什么时候应该填5呢，需要让每个数对的最大值都是4，前面h[0][3]到h[7][3]是0,1,2,2,3,3,3,3，共8个数字，需要与后面8个数字4配对，这8个数字的位置应该为h[15][4]到h[8][4]，这样最大值都是4，接下来h[8][3]往下都是4，与j=4的一列较小值配对，最大值都是4。
因此第一个填5的位置应该是h[16][4]，在它前面一共有8个4。
j是2时确定了有2个2，j是3时确定了有4个3，j是4时就能确定有8个4，…，在j=100时，各项数值一定都已经进行了充分的计算，计算后，一列之中应该有1个0，1个1，2个2，4个3，8个4，16个5，32个6，64个7，。。。
列举出每个数字第一次出现的位置
h[1][100]=1
h[2][100]=2
h[4][100]=3
h[8][100]=4
h[16][100]=5
h[32][100]=6
h[64][100]=7
h[128][100]=8
因此h[100][100]的值为7。
【其他解法】
本题的原题实质是信息学奥赛一本通 1300：鸡蛋的硬度 | OpenJudge NOI 2.6 7627:鸡蛋的硬度，除非你做过这一问题，能通过看代码得知这是个扔鸡蛋问题，否则很难在考场上就能从扔鸡蛋的角度来思考这一问题。
该题求的是最坏情况下最少扔鸡蛋的次数。
在了解这个代码是扔鸡蛋问题后，第26题解法为：
只有2个鸡蛋，设最坏情况下扔鸡蛋测出楼层高度最少需要扔x次
第一次最高也只能在第x层，如果在更高层扔，如果鸡蛋碎了，那么剩下1个鸡蛋在扔x-1次未必能测出鸡蛋硬度。
在第x层扔，如果碎了，那么剩下一个鸡蛋从第1层开始扔，如果没碎，就在第2层扔，不断升高楼层，当鸡蛋在第i层碎了时，鸡蛋硬度为i-1。
第一次在第x层扔鸡蛋如果没碎，那么剩下x-1次机会，楼层数是20-x，确定鸡蛋的硬度。
接下来在第x+x-1层扔鸡蛋，如果没碎，那么剩下x-2次机会，楼层数是20-x-(x-1)，确定鸡蛋的硬度。
为了确定鸡蛋在20层楼内的硬度，需要x+(x-1)+(x-2)+…+1>=20
即(1+x)x/2 >= 20
x是整数，可以取到的最小值为6。文章来源：https://www.toymoban.com/news/detail-652911.html
第27题，100层楼有100个鸡蛋，确定鸡蛋硬度，鸡蛋足够了，就可以用二分查找的方法确定鸡蛋的硬度，二分查找最大比较次数为 ⌊ l o g 2 100 ⌋ + 1 = 7 \lfloor log_2100\rfloor+1=7 ⌊log2100⌋+1=7。文章来源地址https://www.toymoban.com/news/detail-652911.html
【答案】
- 错误
- 正确
- 正确
- C
- C
- B
到了这里，关于CSP-J 2022 入门级 第一轮 阅读程序（2） 第22-27题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
