Editorial for 數字遊戲 (APCS 2022-06 初級)
簡潔題意
給三個整數 \(A_1\)、\(A_2\)、\(A_3\)。先輸出 \(P\)=出現最多次的那個數字出現了幾次,接著把去掉重複後的數字由大到小輸出,全部印在同一行(\(1 \le A_1, A_2, A_3 \le 9\))
依正確通過的測試資料筆數給分,其中:
- 子題組 1(\(60\) 分):三個數字皆不相同。
- 子題組 2(\(40\) 分):無額外限制。
先排序:一次解決兩件事
題目要兩樣東西:\(P\)(出現最多次的數字出現幾次)和去重後由大到小的數列。這兩件事看起來沒關係,但只要先把三個數字由大到小排好,它們會同時變簡單:
- 輸出的順序就是排好的順序,不用再想;
- 排好之後,相同的數字一定會擠在一起(下冊 11.1 的表格正是在講這件事),所以「誰跟誰重複」只要看相鄰的兩對就好:\(A_1\) 對 \(A_2\)、\(A_2\) 對 \(A_3\)。
排好之後只剩三種長相:
| 排好的樣子 | 相鄰相等有幾組 | \(P\) | 去重後要印幾個 |
|---|---|---|---|
| 三個都一樣 | \(2\) 組 | \(3\) | \(1\) 個 |
| 恰好兩個一樣 | \(1\) 組 | \(2\) | \(2\) 個 |
| 三個都不一樣 | \(0\) 組 | \(1\) | \(3\) 個 |
\(P\) 那一欄就是「相鄰相等的組數加一」——這張表等一下兩種做法都會用到。
做法一:三次比較排好,再照三種長相分類
排序三個數在上冊 3.9 教過:三次比較,每次不對就交換。這裡要由大到小,所以條件寫成「前面的比較小就換」:
if (A[1] < A[2]) swap(A[1], A[2]);
if (A[1] < A[3]) swap(A[1], A[3]);
if (A[2] < A[3]) swap(A[2], A[3]);
swap 住在 <algorithm>(上冊 7.6)。陣列開 int A[4] 卻從 A[1] 開始用,是題目講「第幾個數字」時最好對照的寫法(6.3)——要從 \(1\) 用起就得開 \(4\) 格,開 int A[3] 再去碰 A[3] 是越界(6.8,-Wall 也會警告你)。
\(P\) 照著上面的表格分類,但兩個問題的順序不能反:要先問「三個都一樣嗎」,再問「有沒有一組相鄰相等」。因為三個都一樣時 A[1] == A[2] 同樣成立,先問後面那句就會停在 \(2\) 出不來(else if 由上往下只會中一個,上冊 3.5)。
去重輸出:\(A_1\) 一定要印;\(A_2\) 只有在它跟前一個不一樣時才印;\(A_3\) 同理,跟它的前一個 \(A_2\) 比。判斷「這個數字要不要印」看的永遠是它的前一個,比錯對象是這題最隱蔽的錯(收在下面的常犯錯誤第 1 條)。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int A[4];
cin >> A[1] >> A[2] >> A[3];
if (A[1] < A[2]) swap(A[1], A[2]); // 三次比較,排成由大到小
if (A[1] < A[3]) swap(A[1], A[3]);
if (A[2] < A[3]) swap(A[2], A[3]);
int num = 1; // 三個都不一樣的話 P 就是 1
if (A[1] == A[2] && A[2] == A[3]) {
num = 3;
}
else if (A[1] == A[2] || A[2] == A[3]) {
num = 2;
}
cout << num << ' ' << A[1];
if (A[1] != A[2]) cout << ' ' << A[2]; // 跟前一個不一樣才印
if (A[2] != A[3]) cout << ' ' << A[3];
cout << '\n';
return 0;
}
做法二:交給 sort,\(P\) 也縮成一行
排序的部分交給下冊 11.4 的 sort:由大到小就是加第三個參數 greater()。因為陣列是從 \(1\) 用起,範圍兩端都要跟著 \(+1\),寫成 sort(A + 1, A + 4, greater());。
\(P\) 的三個 if 也可以收成一行:
1 + (A[1] == A[2]) + (A[2] == A[3])
A[1] == A[2] 這種比較式的結果是 true 或 false,放進算式裡就自動變成 \(1\) 或 \(0\)(上冊 3.7 的「把條件當數字用」)。所以這條式子在數的正是「相鄰相等有幾組」,再加 \(1\) ——對回上面那張表,三種長相全部都對。
兩個小括號不能省:<< 的優先順序比 == 高(上冊 3.4),少了括號,編譯器會先把 cout << 1 + A[1] 算完再拿去跟 A[2] 比,然後對你說 no match for 'operator=='。
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
int A[4];
cin >> A[1] >> A[2] >> A[3];
sort(A + 1, A + 4, greater()); // 由大到小;1-base 所以兩端都 +1
cout << 1 + (A[1] == A[2]) + (A[2] == A[3]) << ' ' << A[1];
if (A[1] != A[2]) cout << ' ' << A[2];
if (A[2] != A[3]) cout << ' ' << A[3];
cout << '\n';
return 0;
}
去重輸出那兩行跟做法一一字不差——因為前提沒變,sort 排出來的一樣是由大到小。兩種做法都是滿分解:做法一只用上冊的東西,把「排序」和「分類」都自己寫一遍;做法二把排序交給 sort、把分類交給算式,剩下的只有輸出。
測過再交:三個範例少了「重複的是最大的那個」
先盤點範例蓋到了什麼:範例 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[1] != A[2]) cout << ' ' << A[2];寫成if (A[1] != A[3]) ...。三個範例全部都會過,只有「重複的是最大的那個」才現形——9 9 4會印成2 9 9 4。要不要印 \(A_2\),看的是它跟前一個一不一樣。 -
\(P\) 的兩個判斷順序反了:先問「有沒有一組相鄰相等」再問「三個都一樣」,三個都一樣時就停在 \(2\) 出不來。範例 1 會印出
2 6。 -
忘了去重,三個數字全印:範例 1 印
3 6 6 6、範例 2 印2 9 7 7。這種寫法在「三個數字都不相同」時是對的——也就是子題組 1 保證的情況——但只要輸入出現重複就掛。 -
沒排序就直接判斷:照原本的輸入順序問
A[1] == A[2] || A[2] == A[3]。7 9 7的兩組相鄰都不相等,會印出1 7 9 7。相同的數字擠在一起是排序之後才成立的事,整套判斷都靠它。 -
\(P\) 算成「有幾種不同的數字」:這兩個數字在恰好兩個一樣時剛好相同(都是 \(2\)),所以範例 2 會過,但範例 1 印
1 6、範例 3 印3 8 4 1。\(P\) 問的是次數不是種類數。 -
排成由小到大(做法二漏了
greater()):範例 2 印2 7 9、範例 3 印1 1 4 8。