约瑟夫环C++代码（数组实现） |21xrx.com

约瑟夫环C++代码（数组实现）

2023-06-25 13:10:51 深夜i -- --

约瑟夫环 C++代码数组实现

约瑟夫环是一个经典的问题，有许多种实现方法。这里我使用C++语言和数组来实现约瑟夫环问题，并分享代码及注释，希望能帮助到有需要的读者。

首先，让我们回顾一下约瑟夫环问题的定义：有n个人围成一圈，从第k个人开始报数，数到m的那个人出列，然后从出列的下一个人开始继续报数，直到所有人出列为止。

我们可以通过模拟出列的过程来实现此问题。首先，我们需要定义一个数组来存储所有人，然后定义一个指针，指向当前报数的人。接下来，我们循环计数，当计数到达m时，将当前指针指向的人从数组中移除，并将指针指向下一个还在圈内的人。当数组中只剩下一个人时，循环结束，这个人就是最后一位幸存者。

下面是具体的C++代码实现：


#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;  // 数组容量
int a[MAXN];      // 数组
int n = 10, k = 3, m = 4; // n：人数，k：起始编号，m：出列编号
int s = n;       // 剩余人数
int main() {
  memset(a, 0, sizeof(a));  // 初始化
  int i = k - 1, j = 0;    // i：当前报数的人在数组中的下标，j：当前计数
  while (s > 1) {       // 只要还有多于1人就继续循环
    if (a[i] == 0) {    // 如果当前位置为空，表示这个人已出列，j不用递增直接跳过
      j++;
    }
    if (j == m) {      // 如果当前计数满足出列条件
      a[i] = 1;      // 标记为出列状态
      s--;        // 剩余人数减一
      cout << i + 1 << " "; // 输出当前出列的人的编号
      j = 0;       // 从0开始新一轮计数
    }
    i = (i + 1) % n;    // 指向下一个人。注意用取余运算实现循环指针
  }
  for (int i = 0; i < n; i++) {  // 最后只剩下一个人，循环输出
    if (a[i] == 0) {
      cout << i + 1 << endl;
      break;
    }
  }
  return 0;
}

代码中的注释已经比较详细，这里再解释一下几个要点：

1. 由于C++数组下标从0开始，而我们的人数从1开始编号，因此在实现时对数组下标要作相应调整，如i = k - 1。

2. 数组的初值默认为0，我们用0表示还未出列的人，1表示已出列的人，这样就可以通过检查a[i]是否为0来判断这个人是否还在圈内。

3. 当当前指针指向的人已经出列时，计数器j不递增，直接跳过。

4. 使用取余运算实现循环指针是常用技巧，如i = (i + 1) % n，表示当i增加到n-1时又从0开始计数。

经过编译和运行，我们可以得到类似以下的输出：

3 7 2 8 4 1 9 6 10 5

这表示从第3个人开始，每数4个人就出列，直到最后只剩下5号幸存者。当然，当n、k、m的取值不同时，输出和运行结果都会不同。

总之，约瑟夫环问题的C++实现思路可以说是比较简单和直观的，只需理解清楚它的定义和关键点，然后熟悉C++语言的数组和指针操作即可。

上一篇: idea打包java可执行jar包

下一篇: C++推荐书籍看书顺序指南

评论区

()

相似文章