數字遊戲 題解|APCS 2022 年 6 月初級 第 1 題
簡潔題意
給三個整數 \(A_1\)、\(A_2\)、\(A_3\)。先輸出 \(P\)=出現最多次的那個數字出現了幾次,接著把去掉重複後的數字由大到小輸出,全部印在同一行(\(1 \le A_1, A_2, A_3 \le 9\))
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(60\) 分):三個數字皆不相同。
- 子題組 2(\(40\) 分):無額外限制。
先排序:一次解決兩件事
題目要兩樣東西:\(P\)(出現最多次的數字出現幾次)和去重後由大到小的數列。這兩件事看起來沒關係,但只要先把三個數字由大到小排好,它們會同時變簡單:
- 輸出的順序就是排好的順序,不用再想;
- 排好之後,相同的數字一定會擠在一起,所以「誰跟誰重複」只要看相鄰的兩對就好:第 \(1\) 個對第 \(2\) 個、第 \(2\) 個對第 \(3\) 個。
排好之後只剩三種長相:
| 排好的樣子 | 相鄰相等有幾組 | \(P\) | 去重後要印幾個 |
|---|---|---|---|
| 三個都一樣 | \(2\) 組 | \(3\) | \(1\) 個 |
| 恰好兩個一樣 | \(1\) 組 | \(2\) | \(2\) 個 |
| 三個都不一樣 | \(0\) 組 | \(1\) | \(3\) 個 |
\(P\) 那一欄就是「相鄰相等的組數加一」——這張表等一下算 \(P\) 會一直用到。
三次比較排好,再照三種長相分類
三個數讀進 a、b、c(就是題目的 \(A_1\)、\(A_2\)、\(A_3\))。排序三個數在上冊 3.12 教過:三次比較,每次順序不對就用暫存變數 t 交換。3.12 排的是由小到大,這裡要由大到小,所以把三個 > 都改成 <,條件變成「前面的比較小就換」:
if (a < b) { // 第 1 步:讓 a 不比 b 小
int t = a;
a = b;
b = t;
}
if (a < c) { // 第 2 步:做完後 a 就是三者中最大的
int t = a;
a = c;
c = t;
}
if (b < c) { // 第 3 步:最後排好 b、c
int t = b;
b = c;
c = t;
}
排完之後 a 最大、c 最小。
\(P\) 照著上面的表格分類,但兩個問題的順序不能反:要先問「三個都一樣嗎」,再問「有沒有一組相鄰相等」。因為三個都一樣時 a == b 同樣成立,先問後面那句就會停在 \(2\) 出不來(else if 由上往下只會中一個,上冊 3.5)。
去重輸出:a 一定要印;b 只有在它跟前一個 a 不一樣時才印;c 同理,跟它的前一個 b 比。判斷「這個數字要不要印」看的永遠是它的前一個,比錯對象是這題最隱蔽的錯(收在下面的常犯錯誤第 1 條)。
#include <iostream>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
// 三次比較,排成由大到小(3.12 的三個 > 都改成 <)
if (a < b) {
int t = a;
a = b;
b = t;
}
if (a < c) {
int t = a;
a = c;
c = t;
}
if (b < c) {
int t = b;
b = c;
c = t;
}
int num = 1; // 三個都不一樣的話 P 就是 1
if (a == b && b == c) {
num = 3;
} else if (a == b || b == c) {
num = 2;
}
cout << num << " " << a;
if (a != b) cout << " " << b; // 跟前一個不一樣才印
if (b != c) cout << " " << c;
cout << endl;
return 0;
}
\(P\) 也可以縮成一行
上面算 \(P\) 的那串 if 也可以收成一個算式:
1 + (a == b) + (b == c)
a == b 這種比較式的結果是 true 或 false,放進算式裡就自動變成 \(1\) 或 \(0\)(上冊 3.8 的「把條件當數字用」)。所以這條式子在數的正是「相鄰相等有幾組」,再加 \(1\) ——對回上面那張表,三種長相全部都對。把 num 那一段整個拿掉,輸出的第一行改成:
cout << 1 + (a == b) + (b == c) << " " << a;
兩個小括號不能省:<< 的優先順序比 == 高(上冊 3.4),少了括號,編譯器會先把 cout << 1 + a 算完再拿去跟 b 比,然後對你說 no match for 'operator=='。兩種寫法都是滿分解,挑自己看得順的那一種就好。
測過再交:三個範例少了「重複的是最大的那個」
先盤點範例蓋到了什麼:範例 1(6 6 6)是三個都一樣、範例 2(7 9 7)是恰好兩個一樣、範例 3(4 1 8)是三個都不一樣——上面表格的三種長相都有了,所以大部分的邏輯錯都會當場現形。
但是範例 2 排好之後是 9 7 7,重複的是最小的那個數。「重複的是最大的那個」(排好之後長 9 9 4 這樣)三個範例一次都沒出現——而去重那兩個 if 比錯對象時,剛好只會在這種輸入上翻車。
自己補這幾筆再交:
| 想測什麼 | 輸入 | 正確輸出 |
|---|---|---|
| 重複的是最大的那個數(排好後前兩個一樣) | 9 9 4 |
2 9 4 |
| 輸入本來就由小到大(驗排序真的有做) | 1 5 9 |
1 9 5 1 |
| 重複的是最小的那個數,而且用到值域兩端 | 1 1 9 |
2 9 1 |
第一列就是專門堵常犯錯誤第 1 條的(比錯對象的版本在這筆會印出 2 9 9 4)。這三筆都親眼看過正確,這題就穩了。
常犯錯誤
-
去重時比錯對象:把
if (a != b) cout << " " << b;寫成if (a != c) ...。三個範例全部都會過,只有「重複的是最大的那個」才現形——9 9 4會印成2 9 9 4。要不要印b,看的是它跟前一個一不一樣。 -
\(P\) 的兩個判斷順序反了:先問「有沒有一組相鄰相等」再問「三個都一樣」,三個都一樣時就停在 \(2\) 出不來。範例 1 會印出
2 6。 -
忘了去重,三個數字全印:範例 1 印
3 6 6 6、範例 2 印2 9 7 7。這種寫法在「三個數字都不相同」時是對的——也就是子題組 1 保證的情況——但只要輸入出現重複就掛。 -
沒排序就直接判斷:照原本的輸入順序問
a == b || b == c。7 9 7的兩組相鄰都不相等,會印出1 7 9 7。相同的數字擠在一起是排序之後才成立的事,整套判斷都靠它。 -
\(P\) 算成「有幾種不同的數字」:這兩個數字在恰好兩個一樣時剛好相同(都是 \(2\)),所以範例 2 會過,但範例 1 印
1 6、範例 3 印3 8 4 1。\(P\) 問的是次數不是種類數。 -
排成由小到大(照抄 3.12、忘了把三個
>改成<):範例 2 印2 7 9、範例 3 印1 1 4 8。 -
交換時沒有暫存變數:寫成
a = b; b = a;兩行,第一行就把a原本的值蓋掉了,兩個變數最後都是b的值。三段交換都這樣寫的話,範例 3(4 1 8)會印成3 8;範例 2 碰巧是對的。