C 語言單向循環鏈表解決約瑟夫問題

約瑟夫問題背景

經典約瑟夫問題：N 人圍成一圈，從第 1 人開始報數，每報到 M 者出局，下一人繼續報 1，直到剩最後一人。歷史典故源自猶太歷史學家弗拉維奧·約瑟夫斯，亦見於法國數學家加斯帕《數目遊戲問題》。

循環鏈表模型

• 每個節點包含 data（編號）與 next 指標。
• 建立時將尾節點 next 指向頭節點，形成環。
• 刪除節點時，前驅節點 next 指向被刪節點的 next，再 free 被刪節點。

核心演算法

1. 建立 1..N 的循環鏈表。
2. 從頭節點開始，計數器 counter 從 1 遞增。
3. 當 counter == rule-1 時，下一個節點為第 rule 人，執行刪除：
   tmp = list->next; list->next = tmp->next; free(tmp);
4. 重置 counter=0，list 移至下一節點繼續。
5. 當 list->next == list 時，剩最後一人，結束。

完整程式碼

/*************************************************************************
> File Name: josefu.c
> Author: Baniel Gao
> Mail: createchance@163.com
> Blog: blog.csdn.net/createchance
> Created Time: Thu 19 Dec 2013 03:08:21 PM CST
***********************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct josefu {
    int data;
    struct josefu *next;
} josefu_list;

josefu_list *josefu_init(int num);
josefu_list *josefu_begin(josefu_list *list, int rule);
josefu_list *josefu_node(int num);
int josefu_free(josefu_list *list);
int josefu_show(josefu_list *list);

int main(void) {
    josefu_list *list;
    int num, rule;
    puts("Please input number and rules: ");
    scanf("%d%d", &num, &rule);
    list = josefu_init(num);
    list = josefu_begin(list, rule);
    josefu_free(list);
    return 0;
}

josefu_list *josefu_init(int num) {
    int i;
    josefu_list *new_node;
    josefu_list *list = josefu_node(1);
    for (i = num; i > 1; i--) {
        new_node = josefu_node(i);
        new_node->next = list->next;
        list->next = new_node;
    }
    return list;
}

josefu_list *josefu_node(int num) {
    josefu_list *p = (josefu_list *)malloc(sizeof(josefu_list));
    p->data = num;
    p->next = p;
    return p;
}

josefu_list *josefu_begin(josefu_list *list, int rule) {
    int counter;
    josefu_list *tmp = NULL;
    for (counter = 1; list->next != list; counter++) {
        if (counter == rule - 1) {
            tmp = list->next;
            list->next = tmp->next;
            free(tmp);
            counter = 0;
            josefu_show(list);
        }
        list = list->next;
    }
    return list;
}

int josefu_show(josefu_list *list) {
    josefu_list *p = list;
    if (list == NULL) return 0;
    do {
        printf("%5d", p->data);
        p = p->next;
    } while (list != p);
    putchar('\n');
    return 0;
}

int josefu_free(josefu_list *list) {
    free(list);
    return 0;
}

執行範例

輸入 41 3（41 人，報 3 出局），程式會逐步印出每輪倖存者序列，最終剩下第 31 號（約瑟夫斯與朋友所站位置）。

常見變體與優化

• 遞迴數學解：f(1)=0; f(n)=(f(n-1)+k)%n，O(N) 時間、O(1) 空間，適合大規模 N。
• 雙向循環鏈表：支援雙向刪除，適合需頻繁前後遍歷的擴展題。
• 陣列模擬：用 next[] 陣列模擬鏈表，避免 malloc 開銷，速度更快。

教學重點

1. 循環鏈表建立與刪除節點的指標操作。
2. 計數器重置邏輯（counter = rule-1 觸發刪除）。
3. 終止條件 list->next == list 判斷單節點環。
4. 記憶體釋放：free(tmp) 避免洩漏，結束時 free(list) 釋放最後節點。