《算法競賽入門經典》5.3 排序與檢索：四位數卡普雷卡常數問題解析

《算法競賽入門經典》5.3 排序與檢索：四位數卡普雷卡常數問題解析

在《算法競賽入門經典》第 5.3 節中，有一個經典的排序與檢索問題：給定一個各位數字互不相同的四位數，將其數字從大到小排序得到 a，從小到大排序得到 b，然後用 a - b 替換原數，重複此操作。以 1234 為例：

4321 - 1234 = 3087
8730 - 0378 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174  (進入循環)

這個過程最終會陷入 6174 這個「卡普雷卡常數」的循環中。題目要求輸入一個 n 位數，輸出操作序列，直到出現循環（即新得到的數曾經出現過），輸入保證循環前最多產生 1000 個整數。

核心思路

解決這個問題分為兩個關鍵步驟：

1. 編寫 get_next 函數計算下一個數：將整數轉為字串，對字元進行排序（可用冒泡排序），得到升序數 b；反轉字串得到降序數 a；回傳 a - b。
2. 生成序列並檢測循環：用陣列記錄已出現的數。每生成一個新數，掃描陣列判斷是否重複；若重複則輸出並結束，否則存入陣列繼續。

關鍵代碼實現 (C 語言)

#include <stdio.h>
#include <string.h>

int num[2000], count;

int get_next(int x) {
    int a, b, n;
    char s[10];
    sprintf(s, "%d", x);          // 整數轉字串
    n = strlen(s);
    // 冒泡排序：升序
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (s[i] > s[j]) {
                char t = s[i]; s[i] = s[j]; s[j] = t;
            }
    sscanf(s, "%d", &b);          // 升序數 b
    // 反轉字串得到降序
    for (int i = 0; i < n / 2; i++) {
        char t = s[i]; s[i] = s[n - 1 - i]; s[n - 1 - i] = t;
    }
    sscanf(s, "%d", &a);          // 降序數 a
    return a - b;
}

int main() {
    scanf("%d", &num[0]);
    printf("%d", num[0]);
    count = 1;
    for (;;) {
        num[count] = get_next(num[count - 1]);
        printf(" -> %d", num[count]);
        // 檢查是否重複
        int found = 0;
        for (int i = 0; i < count; i++)
            if (num[i] == num[count]) { found = 1; break; }
        if (found) break;
        count++;
    }
    printf("\n");
    return 0;
}

注意事項

• 輸入數字可能包含前導零（如 3087 排序後為 0378），sprintf/sscanf 配合字串長度可正確處理。
• 題目保證循環前不超過 1000 個數，陣列大小 2000 足夠安全。
• C99 標準允許在 for 迴圈中宣告變數（for(int i=...)），若編譯器報錯請改用 .cpp 副檔名或移至迴圈外宣告。

這道題目優雅地展示了「排序 + 模擬 + 循環檢測」的組合技巧，是算法入門的經典練習。