约瑟夫环问题 C语言实现 - 按退出顺序输出每个人的序号

约瑟夫环问题 C语言实现 - 按退出顺序输出每个人的序号

约瑟夫环问题是一个经典的数学问题，描述了 N 个人围成一个圈，从第 1 个人开始报数，报到第 P 个人出圈，然后从下一个继续报数，直到只剩下一个人为止。该问题要求输出每个出圈人的原序号，按出圈顺序排列。

问题描述

N 个人围成一圈顺序编号，从 1 号开始按 1、2、3......顺序报数，报 P 者退出圈外，其余的人再从 1、2、3 开始报数，报 P 的人再退出圈外，以此类推。请按退出顺序输出每个退出人的原序号。

输入格式

输入只有一行，包括一个整数 N(1<=N<=3000)及一个整数 p(1<=p<=5000)。

输出格式

按退出顺序输出每个退出人的原序号，数据间以一个空格分隔，但行尾无空格。

输入样例

7 3

输出样例

3 6 2 7 5 1 4

C语言实现

#include <stdio.h>

void josephus(int N, int p) {
    int arr[3000];
    int i, j;
    int count = 0;
    int num = N;

    // 初始化数组
    for (i = 0; i < N; i++) {
        arr[i] = i + 1;
    }

    // 循环报数并输出退出的人的原序号
    while (num > 0) {
        for (i = 0; i < N; i++) {
            if (arr[i] != 0) {
                count++;
                if (count == p) {
                    printf('%d ', arr[i]);
                    arr[i] = 0; // 标记退出的人
                    count = 0;
                    num--;
                }
            }
        }
    }
}

int main() {
    int N, p;

    // 读取输入
    scanf('%d %d', &N, &p);

    // 输出退出的人的原序号
    josephus(N, p);

    return 0;
}

代码解释

1. 使用一个数组 arr 来存储每个人的原序号，初始值为 1 到 N。
2. 使用变量 count 来记录当前报数的次数，使用变量 num 来记录剩余的人数。
3. 循环遍历数组，当 count 等于 P 时，输出当前人的序号，并将该位置的数组元素设置为 0，表示该人已经退出。
4. 重置 count 和 num，继续循环报数，直到所有的人都退出为止。

希望对您有所帮助！请注意，以上代码仅供参考，可能需要根据具体情况进行修改或优化。