約瑟夫斯問題 C 語言實作：17 人環狀報數出列，陣列模擬與鏈結串列兩種解法

問題描述

17 人圍坐一圈，編號 1~17。從第 1 人開始報數，數到 7 的人出列，下一人重新從 1 開始報數，重複直到全員出列。已知前 4 位出列順序為 7、14、4、12。求完整出列序列。

這是經典的約瑟夫斯問題變體。

解法一：陣列模擬法（適合未學指標的初學者）

核心思路

• 用 int people[17] 存放編號，int alive[17] 標記是否在圈內（1=在、0=出列）
• 維護 current_index 當前位置，count 報數計數器
• 環狀處理：索引到達 17 歸零（% 17）
• 跳過已出列者：if (!alive[i]) continue;

完整程式碼

#include <stdio.h>
#include <stdbool.h>

int main() {
    const int N = 17;
    const int K = 7;
    int people[N];
    bool alive[N];

    // 初始化
    for (int i = 0; i < N; i++) {
        people[i] = i + 1;
        alive[i] = true;
    }

    int remaining = N;
    int idx = 0;      // 當前檢查位置
    int count = 0;    // 報數計數

    printf("出列順序：");
    while (remaining > 0) {
        if (alive[idx]) {
            count++;
            if (count == K) {
                // 出列
                printf("%d ", people[idx]);
                alive[idx] = false;
                remaining--;
                count = 0;  // 重新開始報數
            }
        }
        idx = (idx + 1) % N;  // 環狀移動
    }
    printf("\n");
    return 0;
}

執行結果驗證

出列順序：7 14 4 12 5 16 10 3 17 11 2 15 9 1 13 6 8

前四位 7、14、4、12 與題目給出一致，驗證邏輯正確。

解法二：循環單鏈結串列（進階資料結構解法）

結構定義

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

核心操作

• 建立環狀鏈結串列：尾節點 next 指向頭節點
• 刪除節點：需維護 pre（前驅節點）以便 pre->next = p->next
• 釋放記憶體：free(p) 避免記憶體洩漏

關鍵函式實作

void josephus_linked_list(int n, int k) {
    // 建立環狀鏈結串列
    Node *head = malloc(sizeof(Node));
    head->data = 1;
    Node *tail = head;
    for (int i = 2; i <= n; i++) {
        Node *new_node = malloc(sizeof(Node));
        new_node->data = i;
        tail->next = new_node;
        tail = new_node;
    }
    tail->next = head;  // 封閉成環

    Node *pre = tail;   // pre 初始指向尾節點（head 的前驅）
    Node *p = head;
    int count = 0;

    while (p != p->next) {  // 還有超過 1 節點時
        count++;
        if (count == k) {
            printf("%d ", p->data);
            pre->next = p->next;  // 從鏈結串列移除
            Node *temp = p;
            p = p->next;          // 移至下一節點
            free(temp);
            count = 0;
        } else {
            pre = p;
            p = p->next;
        }
    }
    // 最後一個節點
    printf("%d\n", p->data);
    free(p);
}

兩種解法比較

數學解法延伸（O(N) 時間複雜度）

遞迴公式：f(1) = 0; f(i) = (f(i-1) + k) % i（0-based 索引）

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

此法僅能求「最後倖存者」，無法輸出完整出列順序。完整序列輸出仍需模擬或資料結構輔助。

學習建議

• 初學者：先掌握陣列模擬法，理解環狀索引（% N）與狀態標記
• 進階：實作鏈結串列版，鍛鍊指標操作與動態記憶體管理
• 面試/競賽：背誦數學遞迴公式求最後倖存者，但說明完整序列需模擬