C語言四位反序數問題：暴力枚舉與數學建模求解

問題描述

給定整數n (2≤n≤9)，找到四位數N，使得N * n = reverse(N)。例如：n=9時，1089 * 9 = 9801。

解法一：暴力枚舉 (最直觀)

#include 

int reverse_num(int x) {
    int rev = 0;
    while (x > 0) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    return rev;
}

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 1000; i < 10000; i++) {
        if (i * n == reverse_num(i)) {
            printf("%d\n", i);
            return 0;
        }
    }
    printf("No solution\n");
    return 0;
}

解法二：數學建模優化 (減少搜索空間)

設N = 1000a + 100b + 10c + d，其中a∈[1,9], b,c,d∈[0,9]。
反序數M = 1000d + 100c + 10b + a。
方程：(1000a+100b+10c+d) * n = 1000d+100c+10b+a。

整理得：(1000n-1)a + (100n-10)b + (10n-100)c + (n-1000)d = 0。

由於n≤9，1000n-1 > 0，n-1000 < 0。可推導約束關係縮小搜索範圍。

優化枚舉代碼

int main() {
    int n;
    scanf("%d", &n);
    
    // a 是最高位，d 是最低位
    for (int a = 1; a <= 9; a++) {
        for (int d = 1; d <= 9; d++) {  // d≠0 否則反序非四位數
            // 根據個位數特性快速過濾
            if ((a * n) % 10 != d) continue;
            
            for (int b = 0; b <= 9; b++) {
                for (int c = 0; c <= 9; c++) {
                    int N = 1000*a + 100*b + 10*c + d;
                    int M = 1000*d + 100*c + 10*b + a;
                    if (N * n == M) {
                        printf("%d\n", N);
                        return 0;
                    }
                }
            }
        }
    }
    return 0;
}

已知解對照表

注：經驗證，n=2,3,5,6,7,8在四位數範圍內無解。題目保證輸入有解。

進階：通用反序數查找器

#include 
#include 

int reverse_int(int x) {
    int rev = 0;
    while (x) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    return rev;
}

void find_reverse_multiples(int digits, int max_n) {
    int start = 1;
    for (int i = 1; i < digits; i++) start *= 10;
    int end = start * 10;
    
    for (int n = 2; n <= max_n; n++) {
        for (int i = start; i < end; i++) {
            if (i * n == reverse_int(i)) {
                printf("n=%d: %d × %d = %d\n", n, i, n, i*n);
            }
        }
    }
}

int main() {
    find_reverse_multiples(4, 9);  // 四位數，n≤9
    return 0;
}

複雜度分析

• 暴力枚舉：O(9000) ≈ 9000次迭代，極快
• 數學優化：O(9×9×10×10) = 8100，略優但代碼複雜
• 大數擴展：若位數增至10位，需大整數庫或字符串處理

考試/面試技巧

1. 優先寫暴力枚舉：代碼簡短、邏輯清晰、不易出錯
2. 封裝reverse()函數提高可讀性
3. 注意d≠0約束 (反序數必須也是四位數)
4. 測試樣例：n=9 → 1089，n=4 → 2178

此類數字遊戲題，暴力枚舉通常是最佳工程實踐：現代CPU執行9000次簡單運算只需微秒級。過度優化反而增加bug風險。