經典 C 語言算法題精選：水仙花數、完數、楊輝三角、遞迴字串轉換與約瑟夫環

前言

本文整理自譚浩強《C 程序設計》經典習題，涵蓋數字規律探索、數論基礎、組合數學、遞迴思維、陣列旋轉、循環鏈表模擬、字串比較、記憶體分配器八大核心主題。每題附帶完整邏輯解析與可執行代碼框架，適合夯實算法基本功。

1. 累加序列：Sn = a + aa + aaa + ... (n 項)

數學規律

第 k 項：`T_k = a * (10^{k-1} + 10^{k-2} + ... + 1) = a * (10^k - 1) / 9`

遞推關係：`T_1 = a`，`T_{k} = T_{k-1} * 10 + a`

代碼框架

long long calcSum(int a, int n) {
    long long sum = 0, term = 0;
    for (int i = 1; i <= n; i++) {
        term = term * 10 + a; // 遞推生成項
        sum += term;
    }
    return sum;
}

**注意**：`long long` 防溢位，`n` 較大時需高精度或取模。

2. 水仙花數：三位數立方和等於自身

定義

`abc = a³ + b³ + c³`，其中 `a∈[1,9], b,c∈[0,9]`

窮舉解法

for (int i = 100; i < 1000; i++) {
    int a = i / 100, b = i / 10 % 10, c = i % 10;
    if (a*a*a + b*b*b + c*c*c == i) printf("%d ", i);
}
// 輸出：153 370 371 407

**擴展**：n 位自戀數（Narcissistic Number），預計算 0-9 的 n 次方表加速。

3. 完數（完全數）：因子和等於自身

定義

真因子（不含自身）之和等於自身。如 `6 = 1+2+3`，`28 = 1+2+4+7+14`

優化查找：只遍歷到 √n

int isPerfect(int n) {
    if (n <= 1) return 0;
    int sum = 1; // 1 是所有 n>1 的因子
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            sum += i;
            if (i != n / i) sum += n / i; // 避免平方數重複
        }
    }
    return sum == n;
}

1000 內完數：`6, 28, 496`。下一個 8128 > 1000。

4. 楊輝三角：二項式係數視覺化

性質

• 第 n 行（從 0 開始）有 n+1 個數
• 首尾為 1，中間 `C(n,k) = C(n-1,k-1) + C(n-1,k)`

滾動陣列 O(n) 空間

void printPascal(int rows) {
    int *cur = calloc(rows, sizeof(int));
    for (int i = 0; i < rows; i++) {
        cur[i] = 1; // 行尾為 1
        for (int j = i - 1; j > 0; j--) // 逆序更新，避免覆蓋前值
            cur[j] += cur[j-1];
        for (int j = 0; j <= i; j++)
            printf("%d ", cur[j]);
        printf("\n");
    }
    free(cur);
}

5. 遞迴整數轉字串：itoa 核心邏輯

遞推關係

`n = 483` → `print(48) + '3'` → `print(4) + '8' + '3'` → `'4' + '8' + '3'`

代碼

void intToStr(int n, char *buf, int *pos) {
    if (n < 0) { buf[(*pos)++] = '-'; n = -n; }
    if (n / 10) intToStr(n / 10, buf, pos);
    buf[(*pos)++] = '0' + n % 10;
}
// 呼叫：int pos=0; intToStr(483, buf, &pos); buf[pos]='\0';

**關鍵**：先遞迴處理高位，再寫入低位，自然形成正序。

6. 陣列循環右移 m 位：三次反轉法

算法

原陣列：`[A][B]`，其中 A 前 n-m 個，B 後 m 個。
目標：`[B][A]`
步驟：`reverse(A)` → `reverse(B)` → `reverse(整體)`

代碼

void reverse(int *a, int l, int r) {
    while (l < r) { int t=a[l]; a[l]=a[r]; a[r]=t; l++; r--; }
}
void rotateRight(int *a, int n, int m) {
    m %= n; if (m < 0) m += n;
    reverse(a, 0, n-m-1);
    reverse(a, n-m, n-1);
    reverse(a, 0, n-1);
}

時間 O(n)，空間 O(1)，無需額外陣列。

7. 約瑟夫環：n 人報數 3 出列，求倖存者

數學解（遞推公式）

`f(1) = 0`（0-based）
`f(i) = (f(i-1) + 3) % i`

代碼

int josephus(int n, int k) { // k=3
    int survivor = 0; // 0-based
    for (int i = 2; i <= n; i++)
        survivor = (survivor + k) % i;
    return survivor + 1; // 轉 1-based 編號
}

**模擬法**（教學用）：循環鏈表或陣列標記，時間 O(nk)，空間 O(n)。

8. 手寫 strcmp：字串字典序比較

int myStrcmp(const char *s1, const char *s2) {
    while (*s1 && *s1 == *s2) { s1++; s2++; }
    return (unsigned char)*s1 - (unsigned char)*s2; // 強制無號減法
}

**細節**：轉 `unsigned char` 避免負字元導致比較錯誤（如 ISO-8859-1 擴展字元）。

9. 簡易記憶體分配器 alloc(n)：從靜態池切割

設計

• 靜態大陣列 `char pool[POOL_SIZE]`
• 指標 `char *free_ptr = pool` 指向可用區起始
• `alloc(n)`：檢查剩餘空間 → 記錄當前 `free_ptr` → `free_ptr += n` → 回傳舊指標

代碼

#define POOL_SIZE 10000
static char pool[POOL_SIZE];
static char *free_ptr = pool;

void *alloc(int n) {
    if (free_ptr + n > pool + POOL_SIZE) return NULL; // 耗盡
    void *p = free_ptr;
    free_ptr += n;
    return p;
}

**缺失**：無 `free`、無對齊、無碎片整理。真實分配器需維護空閒鏈表/紅黑樹。

總結與練習建議

建議：先獨立實作每題，**再對比標準庫實現**（`qsort`、`bsearch`、`strlen`、`memmove` 等），體會工業級代碼的邊界處理與效能優化。