CSP-J 2022 入门级 第一轮 阅读程序（2） 第22-27题

【题目】

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>头文件后可以使用

1. numeric_limits<数据类型>::max()

   返回该数据类型可以表示的最大值

2. numeric_limits<数据类型>::min()

   返回该数据类型可以表示的最小值

3. 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
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
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。

第27题，100层楼有100个鸡蛋，确定鸡蛋硬度，鸡蛋足够了，就可以用二分查找的方法确定鸡蛋的硬度，二分查找最大比较次数为 ⌊ l o g 2 100 ⌋ + 1 = 7 \lfloor log_2100\rfloor+1=7 ⌊log2​100⌋+1=7。

【答案】

1. 错误
2. 正确
3. 正确
4. C
5. C
6. B