C 語言約瑟夫環：10 人報數 3 出列完整程序

問題重述

10 人圍圈，編號 1-10，從 1 起報數，報 3 出列，循環至剩 1 人，輸出倖存者編號。

數組模擬法 (經典教學實現)

#include 
#include 

int main() {
    const int N = 10;
    const int K = 3;
    int a[N];               // 0: 在圈內, 1: 已出列
    for (int i = 0; i < N; i++) a[i] = 0;

    int left = N;           // 剩餘人數
    int idx = -1;           // 當前位置 (從 -1 開始，第一次 ++ 到 0)
    int count = 0;          // 報數計數

    while (left > 1) {
        idx = (idx + 1) % N;      // 移動到下一位置
        if (a[idx] == 1) continue; // 已出列跳過
        count++;
        if (count == K) {
            a[idx] = 1;           // 標記出列
            left--;
            count = 0;
            printf("出列: %d\n", idx + 1);
        }
    }

    // 找倖存者
    for (int i = 0; i < N; i++) {
        if (a[i] == 0) {
            printf("最後剩下: %d\n", i + 1);
            break;
        }
    }
    return 0;
}

鏈表模擬法 (動態刪除節點)

#include 
#include 

typedef struct Node {
    int id;
    struct Node *next;
} Node;

Node* createCircle(int n) {
    Node *head = malloc(sizeof(Node));
    head->id = 1;
    Node *p = head;
    for (int i = 2; i <= n; i++) {
        p->next = malloc(sizeof(Node));
        p = p->next;
        p->id = i;
    }
    p->next = head; // 首尾相連
    return head;
}

int josephus(Node *head, int k) {
    Node *p = head, *prev = NULL;
    // 找尾節點作為 prev
    for (prev = head; prev->next != head; prev = prev->next);
    
    while (p->next != p) {
        for (int i = 1; i < k; i++) {
            prev = p;
            p = p->next;
        }
        printf("出列: %d\n", p->id);
        prev->next = p->next;
        free(p);
        p = prev->next;
    }
    int survivor = p->id;
    free(p);
    return survivor;
}

int main() {
    Node *circle = createCircle(10);
    int survivor = josephus(circle, 3);
    printf("倖存者: %d\n", survivor);
    return 0;
}

數學遞推法 O(n) 時間 O(1) 空間

int josephusMath(int n, int k) {
    int res = 0; // f(1) = 0 (0-based)
    for (int i = 2; i <= n; i++)
        res = (res + k) % i;
    return res + 1; // 1-based
}

int main() {
    printf("倖存者: %d\n", josephusMath(10, 3)); // 4
    return 0;
}

三種方法對比

驗證輸出

出列: 3
出列: 6
出列: 9
出列: 2
出列: 7
出列: 1
出列: 8
出列: 5
出列: 10
最後剩下: 4

總結

初學掌握**數組模擬**理解過程，進階掌握**遞推公式** f(i) = (f(i-1) + k) % i 應對大規模與面試。C 語言注意數組下標 0-based 與編號 1-based 轉換。