C語言練習實例69：約瑟夫環問題（3出局）

經典約瑟夫環問題：n 人圍圈，從 1 開始報數，報到 3 的人出列，求最後剩下的人的原始編號。

程序分析

• 數組 num[50] 存儲每人編號（1~n），0 表示已出列。
• 指針 p 指向數組首地址，下標 i 模擬當前位置。
• 變量 k 計數報數（1,2,3），m 記錄出列人數。
• 循環條件 m < n-1 確保至少剩 1 人。
• 若 *(p+i) != 0 則報數 k++；k==3 時將該位置置 0，m++，k=0。
• i++ 移動下標，i==n 時歸 0 實現環狀。

源代碼

// Created by www.runoob.com on 15/11/9.
// Copyright © 2015年 菜鳥教程. All rights reserved.
//
#include <stdio.h>

void main() {
    int num[50], n, *p, j, loop, i, m, k;
    printf("請輸入這一圈人的數量:\n");
    scanf("%d", &n);
    p = num;
    for (j = 0; j < n; j++)
        *(p + j) = j + 1;

    i = 0; m = 0; k = 0;
    while (m < n - 1) {
        if (*(p + i) != 0) k++;
        if (k == 3) {
            k = 0;
            *(p + i) = 0;
            m++;
        }
        i++;
        if (i == n) i = 0;
    }

    printf("現在剩下的人是:");
    for (loop = 0; loop < n; loop++)
        if (num[loop] != 0)
            printf("%2d號\n", num[loop]);
}

運行示例

請輸入這一圈人的數量:
8
現在剩下的人是:  7號

數學解法

遞推公式：f(1)=0; f(i)=(f(i-1)+3)%i，最終答案 f(n)+1。時間複雜度 O(n)，空間 O(1)。