您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

枚舉與剪枝實戰：解「觀察算式」謎題的極致優化之路

編輯：C++ 入門

問題描述

觀察算式：△△△ × △△ = △△△△
某三位數乘以二位數得四位數。要求 9 個 △ 恰好填入 1~9 每個數字一次。找出所有滿足條件的算式。

從暴力到極致剪枝的演進

版本 1：純暴力（46 ms）

三層迴圈枚舉三位數、二位數，計算積，用 HashSet 檢查 9 個數字是否互不重複且無 0。

版本 2：基礎剪枝（32 ms）

提前檢查被乘數、乘數是否含 0 或重複數字，跳過無效組合。
積必須是 4 位數（1023~9999）。

版本 3：標準答案優化（6 ms）

改用陣列而非 Set，減少物件建立開銷。
將乘數放在外層迴圈（10~99），被乘數內層（100~999）。
逐位比對，發現重複立即 continue 到外層標籤（L1），避免後續無效計算。
積的分解用迴圈，逐位檢查是否與前方數字衝突或含 0。

// 核心邏輯片段
for (int x = 10; x < 100; x++) {
    int a = x/10, b = x%10;
    if (a==0 || b==0 || a==b) continue;
    L1: for (int y = 100; y < 1000; y++) {
        int c = y/100, d = y%100/10, e = y%10;
        if (c*d*e==0) continue;
        if (c==a||c==b||d==a||d==b||e==a||e==b||e==c||e==d) continue;
        int z = x * y;
        if (z < 1000 || z >= 10000) continue;
        int r[4]; for (int i=0;i<4;i++) { r[i]=z%10; z/=10; }
        // 檢查 r 與 a,b,c,d,e 是否衝突、含0、自重複...
    }
}

版本 4：極致優化（3 ms，比標準答案更快）

縮小搜尋範圍：三位數 102~987，二位數 10~98，積 1023~9876。
**關鍵觀察**：積的個位數（a9）必為偶數（因乘數個位 a5 × 被乘數個位 a3 的積模 10 等於 a9，若 a9 為奇數則兩數皆奇，但 1~9 中奇數僅 5 個，約束極強），直接 if (a9%2!=0) continue;。
將所有重複檢查**前置**且**展開**，避免函數呼叫與迴圈開銷。
使用 System.nanoTime() 精確計時。

// 核心剪枝邏輯
for (int i = 102; i <= 987; i++) {
    a1=i/100; a2=i/10%10; a3=i%10;
    if (a1*a2*a3==0) continue;
    if (a1==a2 || a2==a3 || a1==a3) continue;
    L2: for (int j = 10; j <= 98; j++) {
        int k = i * j;
        if (k >= 1023 && k <= 9876) {
            a4=j/10; a5=j%10;
            if (a4*a5==0) continue L2;
            if (a4==a5 || a4==a1 || a4==a2 || a4==a3 || a5==a1 || a5==a2 || a5==a3) continue L2;
            a6=k/1000; a7=k/100%10; a8=k/10%10; a9=k%10;
            if (a9%2!=0) continue L2;  // 關鍵：積個位必為偶數
            if (a6*a7*a8*a9==0) continue L2;
            // 展開所有兩兩不等判斷...
            System.out.println(i + "*" + j + "=" + k);
        }
    }
}