您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言單向循環鏈表解決約瑟夫問題：完整實現與可視化演示

編輯：關於C

約瑟夫問題：N 人圍圈，從 1 開始報數，每報到 M 者出列，循環至剩 1 人。經典案例：41 人（Josephus 含友），M=3，Josephus 安排自己在第 16、31 位倖存。本文用單向循環鏈表模擬全過程，代碼清晰、可視化輸出每輪狀態。

數據結構

typedef struct josefu {
    int data;              // 編號 1..N
    struct josefu *next;   // 指向下一人，尾指向首形成環
} josefu_list;

核心操作

1. 初始化構環

josefu_list *josefu_init(int num) {
    josefu_list *list = josefu_node(1); // 首節點
    for (int i = num; i > 1; i--) {     // 頭插法構建 2..N
        josefu_list *new = josefu_node(i);
        new->next = list->next;
        list->next = new;
    }
    return list; // 返回 1 號節點
}

josefu_list *josefu_node(int num) {
    josefu_list *p = malloc(sizeof(josefu_list));
    p->data = num;
    p->next = p; // 單節點自環
    return p;
}

2. 遊戲主循環

josefu_list *josefu_begin(josefu_list *list, int rule) {
    int counter = 1;
    while (list->next != list) { // 直到只剩一節點
        if (counter == rule - 1) { // 下一個即為第 rule 個
            josefu_list *tmp = list->next;
            list->next = tmp->next; // 從環中摘除
            free(tmp);
            counter = 0;
            josefu_show(list); // 可視化當前環狀態
        }
        list = list->next;
        counter++;
    }
    return list; // 返回倖存者
}

3. 狀態打印

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

完整主程序

int main() {
    josefu_list *list;
    int num, rule;
    printf("請輸入總人數 N 和報數規則 M: ");
    scanf("%d%d", &num, &rule);
    list = josefu_init(num);
    list = josefu_begin(list, rule);
    printf("倖存者編號: %d\n", list->data);
    free(list); // 釋放最後節點
    return 0;
}

運行示例 (N=10, M=3)

請輸入總人數 N 和報數規則 M: 10 3
    1    2    4    5    6    7    8    9   10
    1    2    4    5    7    8    9   10
    1    2    4    5    7    8   10
    1    2    4    5    7   10
    1    2    4    5   10
    1    2    4   10
    1    2   10
    1   10
   10
倖存者編號: 10