C 語言經典練習：從 1、2、3、4 組成不重複三位數的兩種算法實現

題目描述

給定數字 1、2、3、4，組成所有互不相同且無重複數字的三位數。輸出所有符合條件的數字並統計總數。

算法一：三重循環暴力枚舉

最直觀思路：百位、十位、個位各自循環 1~4，通過條件判斷去重。

#include <stdio.h>

int main() {
    int count = 0;
    int i, j, k;
    
    printf("所有符合條件的三位數：\n");
    for (i = 1; i <= 4; i++) {        // 百位
        for (j = 1; j <= 4; j++) {    // 十位
            for (k = 1; k <= 4; k++) { // 個位
                if (i != j && i != k && j != k) {
                    printf("%d%d%d ", i, j, k);
                    count++;
                }
            }
        }
    }
    printf("\n總計: %d 個\n", count);
    return 0;
}

輸出：

123 124 132 134 142 143 
213 214 231 234 241 243 
312 314 321 324 341 342 
412 413 421 423 431 432 
總計: 24 個

算法二：排列生成（遞歸/回溯）

將問題視為從 4 個元素中選 3 個的排列（A(4,3)=24）。通過遞歸構建排列，自帶去重特性。

#include <stdio.h>

#define N 4
#define M 3

int digits[N] = {1, 2, 3, 4};
int perm[M];
int used[N] = {0};
int count = 0;

void generate(int pos) {
    if (pos == M) {
        for (int i = 0; i < M; i++) printf("%d", perm[i]);
        printf(" ");
        count++;
        return;
    }
    for (int i = 0; i < N; i++) {
        if (!used[i]) {
            used[i] = 1;
            perm[pos] = digits[i];
            generate(pos + 1);
            used[i] = 0;  // 回溯
        }
    }
}

int main() {
    printf("遞歸生成結果：\n");
    generate(0);
    printf("\n總計: %d 個\n", count);
    return 0;
}

數學驗證

從 n 個不同元素中取 m 個有序排列：A(n,m) = n! / (n-m)!
本題 n=4, m=3：A(4,3) = 4×3×2 = 24，與程序結果一致。

擴展：任意 n、m 的通用解法

void permutation(int n, int m) {
    int *digits = malloc(n * sizeof(int));
    int *perm = malloc(m * sizeof(int));
    int *used = calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) digits[i] = i + 1;
    
    void dfs(int pos) {
        if (pos == m) {
            for (int i = 0; i < m; i++) printf("%d", perm[i]);
            putchar(' ');
            return;
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                used[i] = 1;
                perm[pos] = digits[i];
                dfs(pos + 1);
                used[i] = 0;
            }
        }
    }
    
    dfs(0);
    free(digits); free(perm); free(used);
}

複雜度對比

進階變體

• 允許重複：去掉 used 檢查，總數 n^m
• 組合（無序）：for 循環從 start 開始，避免順序重複
• 含 0 的情況：百位不能為 0，生成時首位跳過 0
• 輸出為整數：num = num*10 + digit 累積計算