约瑟夫环问题（数组法）C语言实现

问题描述

有 $n$ 个人围成一圈，第 $m$ 个人开始报数，报到 $m$ 的人出圈，然后从出圈的下一个人开始继续报数，直到圈中只剩下一人。求出该人的编号。

解法思路

采用数组法解决约瑟夫环问题，主要的思路是：构建一个大小为 $n$ 的数组，来表示 $n$ 个人在约瑟夫环中的位置，将这些位置依次删除，直到只有一个人为止。

具体的步骤如下：

1. 定义一个大小为 $n$ 的数组 a，并初始化数组元素为 $1$ 表示这些人都还在约瑟夫环中。

2. 定义一个变量 step，用来表示报数的步长。

3. 定义一个变量 count，用来表示当前数到的位置。

4. 定义一个变量 iIndex，用于记录出圈人的编号。

5. 从第 $m$ 个人开始报数，即将变量 count 的初始值设置为 $m - 1$。

6. 当数组 a 中的元素个数不为 $1$ 时，进行如下循环：

7. 将 count 的值加上 step - 1，即数到第 $m$ 个人所在的位置，再判断该位置是否为 $1$，如果是 $1$，则表示该人还在约瑟夫环中，继续往前数；如果不是 $1$，说明该人已经出圈，需要继续数，直到数到一个还在约瑟夫环中的人为止。

8. 当找到下一个还在约瑟夫环中的人时，将其所在位置的数组元素置为 $0$，表示该人已经出圈。

9. 记录该人的编号，即 iIndex 变量的值为当前所在位置 $+ 1$，因为数组下标从 $0$ 开始，编号从 $1$ 开始。

10. 将 count 变量加 $1$，表示从下一个人开始重新计数。

11. 当数组 a 中的元素个数为 $1$ 时，剩下的那个人就是最后留下的人，输出其编号即可。

代码实现

以下是用 C 语言实现约瑟夫环问题（数组法）的完整程序代码，其中包括了两个示例，分别对应了题目中的两个例子：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n = 5; // 5个人
    int m = 3; // 从第3个人开始报数
    int step = 2; // 报数步长为2

    // 初始化人员位置数组
    int* a = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        a[i] = 1;
    }

    // 初始化变量
    int count = 0;
    int iIndex = -1;

    // 开始报数
    while (1) {
        for (int i = 0; i < n; i++) {
            if (a[i] == 1) {
                count++;
                if (count == m) {
                    a[i] = 0; // 当前位置的人出圈
                    iIndex = i + 1; // 出圈人的编号
                    count = 0; // 重新开始报数
                }
            }
        }

        int iLeft = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 1) {
                iLeft++;
            }
        }

        if (iLeft == 1) {
            break; // 数组中只剩下一个人了
        }
    }

    printf("当 n = %d, m = %d, step = %d 时，最后出圈的人的编号是：%d\n", n, m, step, iIndex);
    free(a);

    n = 3; // 3个人
    m = 2; // 从第2个人开始报数
    step = 3; // 报数步长为3

    // 初始化人员位置数组
    a = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        a[i] = 1;
    }

    // 初始化变量
    count = 0;
    iIndex = -1;

    // 开始报数
    while (1) {
        for (int i = 0; i < n; i++) {
            if (a[i] == 1) {
                count++;
                if (count == m) {
                    a[i] = 0; // 当前位置的人出圈
                    iIndex = i + 1; // 出圈人的编号
                    count = 0; // 重新开始报数
                }
            }
        }

        int iLeft = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 1) {
                iLeft++;
            }
        }

        if (iLeft == 1) {
            break; // 数组中只剩下一个人了
        }
    }

    printf("当 n = %d, m = %d, step = %d 时，最后出圈的人的编号是：%d\n", n, m, step, iIndex);
    free(a);

    return 0;
}

示例说明

第一个示例中，有 $5$ 个人，从第 $3$ 个人开始报数，报数步长为 $2$，最后出圈的人的编号为 $5$。

第二个示例中，有 $3$ 个人，从第 $2$ 个人开始报数，报数步长为 $3$，最后出圈的人的编号为 $3$。