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.4sort:由大到小就是加第三個參數 greater()。因為陣列是從 \(1\) 用起,範圍兩端都要跟著 \(+1\),寫成 sort(A + 1, A + 4, greater());

\(P\) 的三個 if 也可以收成一行:

1 + (A[1] == A[2]) + (A[2] == A[3])

A[1] == A[2] 這種比較式的結果是 truefalse,放進算式裡就自動變成 \(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)。這三筆都親眼看過正確,這題就穩了。

常犯錯誤
  1. 去重時比錯對象:把 if (A[1] != A[2]) cout << ' ' << A[2]; 寫成 if (A[1] != A[3]) ...三個範例全部都會過,只有「重複的是最大的那個」才現形——9 9 4 會印成 2 9 9 4。要不要印 \(A_2\),看的是它跟前一個一不一樣。

  2. \(P\) 的兩個判斷順序反了:先問「有沒有一組相鄰相等」再問「三個都一樣」,三個都一樣時就停在 \(2\) 出不來。範例 1 會印出 2 6

  3. 忘了去重,三個數字全印:範例 1 印 3 6 6 6、範例 2 印 2 9 7 7。這種寫法在「三個數字都不相同」時是對的——也就是子題組 1 保證的情況——但只要輸入出現重複就掛。

  4. 沒排序就直接判斷:照原本的輸入順序問 A[1] == A[2] || A[2] == A[3]7 9 7 的兩組相鄰都不相等,會印出 1 7 9 7。相同的數字擠在一起是排序之後才成立的事,整套判斷都靠它。

  5. \(P\) 算成「有幾種不同的數字」:這兩個數字在恰好兩個一樣時剛好相同(都是 \(2\)),所以範例 2 會過,但範例 1 印 1 6、範例 3 印 3 8 4 1。\(P\) 問的是次數不是種類數。

  6. 排成由小到大(做法二漏了 greater()):範例 2 印 2 7 9、範例 3 印 1 1 4 8