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