數字遊戲 題解|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)。這三筆都親眼看過正確,這題就穩了。

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

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

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

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

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

  6. 排成由小到大(照抄 3.12、忘了把三個 > 改成 <):範例 2 印 2 7 9、範例 3 印 1 1 4 8。

  7. 交換時沒有暫存變數:寫成 a = b; b = a; 兩行,第一行就把 a 原本的值蓋掉了,兩個變數最後都是 b 的值。三段交換都這樣寫的話,範例 3(4 1 8)會印成 3 8;範例 2 碰巧是對的。