C語言實現區間內無重複數字篩選：完整解法與優化技巧

題目重述

輸入 a, b, n (1 ≤ a ≤ b ≤ 2000, 1 ≤ n ≤ 9)，輸出區間 [a, b] 內所有滿足：

1. 每位數字均來自 {1, 2, ..., n}。
2. 各位數字 **互不相同** 的整數。

每行 5 個，Tab 分隔；無符合輸出提示訊息。

核心判斷邏輯

// 檢查 num 是否只含 1..n 且無重複
int is_valid(int num, int n) {
    int used[10] = {0};          // 索引 1..9 對應數字
    while (num > 0) {
        int digit = num % 10;
        if (digit == 0 || digit > n) return 0;  // 含 0 或超出 n
        if (used[digit]) return 0;              // 重複
        used[digit] = 1;
        num /= 10;
    }
    return 1;
}

完整主程式

#include <stdio.h>

int is_valid(int num, int n);

int main() {
    int a, b, n;
    printf("Please input three integers (a b n): ");
    if (scanf("%d %d %d", &a, &b, &n) != 3) return 1;

    int count = 0, found = 0;
    for (int i = a; i <= b; i++) {
        if (is_valid(i, n)) {
            found = 1;
            printf("%d\t", i);
            if (++count % 5 == 0) putchar('\n');
        }
    }
    if (!found) {
        printf("There is no proper number in the interval.\n");
    } else if (count % 5 != 0) {
        putchar('\n');   // 確保最後換行
    }
    return 0;
}

樣例驗證

Input: 200 500 4
Output:
213	214	231	234	241
243	312	314	321	324
341	342	412	413	421
423	431	432

Input: 1000 2000 3
Output:
There is no proper number in the interval.

優化思路（大數據量擴展）

• DFS 生成合法數：直接從 {1..n} 全排列生成候選數，避免遍歷整個區間。複雜度 O(P(n, k)) 遠小於 O(b-a)。
• 位掩碼加速：用 int mask 替代 used[10]，(mask >> d) & 1 判重，極快。
• 預計算表：對固定 n，預生成所有合法數排序存儲，查詢時二分定位區間。

常見錯誤提醒

1. 忘記處理 num=0（題目為正整數，無影響）。
2. 輸出格式：最後一行不足 5 個也要換行，Tab 用 \t 非空格。
3. 變數名衝突：n 既作上限又作迴圈變數，建議改名 max_digit。