C 语言第88题：模拟约瑟夫环：n 人报数 m 出列

题目

模拟约瑟夫环：n 人报数 m 出列

思路

本题模拟约瑟夫环：n 人围圈报数 m，第 m 个出列，直到剩一人或输出出列顺序。

可用数组标记存活或链表模拟；从当前位置数 m 个活人，出局后继续从下一位报数，直到满足题面停止条件。

解题分析

约瑟夫环模拟：数组标记是否出局，从当前位置报数到 m 的出局，下一位继续，直到剩 0 人。n、m 不大时 O(n²) 模拟足够；n 很大时有递推公式 O(n)，但理解成本高，练手先用模拟。

完整程序

#include <stdio.h>

int main(void)
{
    int n, m;
    if (scanf("%d %d", &n, &m) != 2 || n < 1 || m < 1) {
        return 1;
    }
    int alive[1000];
    for (int i = 0; i < n; i++) {
        alive[i] = 1;
    }
    int left = n, i = 0, cnt = 0;
    while (left) {
        if (alive[i]) {
            cnt++;
            if (cnt == m) {
                printf("%d ", i + 1);
                alive[i] = 0;
                left--;
                cnt = 0;
            }
        }
        i = (i + 1) % n;
    }
    putchar('\n');
    return 0;
}

运行示例

输入：

5 2

输出：

2 4 1 5 3 

其它写法

下面每种写法都是完整程序，输入输出格式与正文一致，便于对照。

数组标记模拟（与正文同类）

正文已是数组模拟，此处保留完整程序便于与链表思路对照。

程序：

#include <stdio.h>

int main(void)
{
    int n, m;
    if (scanf("%d %d", &n, &m) != 2 || n < 1 || m < 1) {
        return 1;
    }
    int alive[1000];
    for (int i = 0; i < n; i++) {
        alive[i] = 1;
    }
    int left = n, i = 0, cnt = 0;
    while (left) {
        if (alive[i]) {
            cnt++;
            if (cnt == m) {
                printf("%d ", i + 1);
                alive[i] = 0;
                left--;
                cnt = 0;
            }
        }
        i = (i + 1) % n;
    }
    putchar('\n');
    return 0;
}

运行示例

输入：

5 2

输出：

2 4 1 5 3