經典 C 語言程式練習九則：水仙花數、完數、楊輝三角、約瑟夫環等

譚浩強《C 程式設計》習題精選，涵蓋數學計算、數字特徵、遞迴、陣列操作、字串處理等核心考點。本文提供現代化、可編譯的標準 C 實作，修正原書圖片代碼的潛在問題，並補充複雜度分析與變體思考。

1. 疊加數列求和：Sn = a + aa + aaa + …

題目：a 為單一數字（1~9），n 為項數，鍵盤輸入 a、n，計算總和。

#include <stdio.h>

long long sum_series(int a, int n) {
    long long term = 0, sum = 0;
    for (int i = 0; i < n; i++) {
        term = term * 10 + a;  // 遞推：a, aa, aaa...
        sum += term;
    }
    return sum;
}

int main() {
    int a, n;
    printf("輸入 a (1-9) 和 n: ");
    scanf("%d %d", &a, &n);
    printf("Sn = %lld\n", sum_series(a, n));
    return 0;
}

注意：n 較大時會溢位，可改用字串大數相加或 __int128。

2. 水仙花數（三位數自戀數）

定義：三位數 abc，滿足 a³ + b³ + c³ = abc。

void print_narcissistic() {
    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);
    }
    putchar('\n');
}
// 輸出: 153 370 371 407

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

定義：如 6 = 1+2+3，28 = 1+2+4+7+14。1000 內僅 6, 28, 496。

void print_perfect(int limit) {
    for (int n = 2; n <= limit; n++) {
        int sum = 1;  // 1 是所有數的因子
        for (int d = 2; d * d <= n; d++) {
            if (n % d == 0) {
                sum += d;
                if (d * d != n) sum += n / d;  // 避免平方數重複
            }
        }
        if (sum == n) printf("%d ", n);
    }
    putchar('\n');
}

優化：只需枚舉到 √n，成對累加因子。

4. 楊輝三角（帕斯卡三角）

利用組合數遞推：C(n,k) = C(n,k-1) * (n-k+1) / k

void print_pascal(int rows) {
    for (int n = 0; n < rows; n++) {
        // 置中空格
        for (int s = 0; s < rows - n - 1; s++) printf("  ");
        long val = 1;
        for (int k = 0; k <= n; k++) {
            printf("%4ld", val);
            val = val * (n - k) / (k + 1);
        }
        putchar('\n');
    }
}

5. 遞迴整數轉字串

輸入 483 → 輸出 "483"。遞迴拆解：先處理高位，再處理個位。

void int_to_str_recursive(int n) {
    if (n < 0) { putchar('-'); n = -n; }
    if (n / 10) int_to_str_recursive(n / 10);
    putchar('0' + n % 10);
}

關鍵：遞迴基準情況隱含在 n/10 == 0 時不再遞迴。

6. 陣列循環右移 m 位

原地反轉法（三步反轉法），O(n) 時間、O(1) 空間：

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 rotate_right(int a[], int n, int m) {
    m %= n; if (m < 0) m += n;
    reverse(a, 0, n-1);
    reverse(a, 0, m-1);
    reverse(a, m, n-1);
}

7. 約瑟夫環：n 人圍圈，報數 3 出列

經典遞推解：f(1)=0, f(i)=(f(i-1)+3)%i，最後加 1 轉 1-based 編號。

int josephus(int n, int k) {  // k=3
    int pos = 0;  // 0-based
    for (int i = 2; i <= n; i++)
        pos = (pos + k) % i;
    return pos + 1;  // 轉 1-based
}
// 也可用循環鏈表模擬，適合教學演示

8. 手寫 strcmp

逐字元比較，遇不同或結束即返回差值。

int my_strcmp(const char *s1, const char *s2) {
    while (*s1 && *s1 == *s2) { s1++; s2++; }
    return (unsigned char)*s1 - (unsigned char)*s2;
}

關鍵：轉 unsigned char 避免有號字元比較錯誤。

9. 手寫記憶體分配器 alloc(n)

簡易版：靜態大緩衝區 + 指標位移（不支援釋放、對齊）。

#define POOL_SIZE 65536
static char pool[POOL_SIZE];
static char *pool_ptr = pool;

void* my_alloc(size_t n) {
    // 簡易對齊到 8 位元組
    n = (n + 7) & ~7;
    if (pool_ptr + n > pool + POOL_SIZE) return NULL;
    void *p = pool_ptr;
    pool_ptr += n;
    return p;
}

實務：真實分配器需管理空閒鏈表、分塊合併、執行緒鎖、對齊保證（malloc 用 16/32 位元組對齊）。

總結與延伸

這九道題串聯起 C 語言基礎功力的完整鏈條：算術、迴圈、遞迴、陣列、指標、字串、記憶體。反覆推敲、優化、擴展，方能內化為直覺。