【C++代码】解决约瑟夫环问题 |21xrx.com

【C++代码】解决约瑟夫环问题

2023-07-04 18:22:11 深夜i -- --

C++ 约瑟夫环递归循环数据结构

约瑟夫环问题是一个经典的问题，它涉及到环形链表的操作，也可以用递归或数学公式来解决。在C++中，我们可以使用链表或数组来实现，下面是使用数组的方法。

先看问题的具体描述：有n个人（编号从0到n-1），他们围成一个圆圈，从第一号开始报数，数到m的人出圈，直到圆圈中只剩下一个人（即最后一人），求这个人的编号。

我们可以使用一个数组来模拟这个圆圈，假设数组长度为n，我们设计一个循环变量i表示当前报数的人的下标，每次报到m时，我们将当前位置的人标记为出圈，即将其对应的数组元素赋为-1（-1表示出圈），然后将i+1，再从下一个人开始报数，如此循环直到只剩下一个人。

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


#include<iostream>
using namespace std;
int main()
{
  int n, m;
  cin >> n >> m;
  int circle[1005]; // 定义一个数组存储圆圈中的人
  for (int i = 0; i < n; i++) {
    circle[i] = i; // 初始化，第i个人的编号为i
  }
  int count = 0; // 记录已出圈的人数
  int i = 0; // 当前报数的人的下标
  while (count < n - 1) { // 循环直到只剩一个人
    int k = 0; // 报数计数器
    while (k < m) { // 报数直到m
      if (circle[i] != -1) { // 如果当前位置的人还未出圈
        k++; // 计数器加1
      }
      if (k == m) { // 报数到m，将当前位置的人出圈
        circle[i] = -1;
        count++; // 出圈人数加1
      }
      i++; // 下一个人开始报数
      if (i == n) // 循环
        i = 0;
      
    }
  }
  for (int i = 0; i < n; i++) { // 输出存活的人的编号
    if (circle[i] != -1) {
      cout << circle[i] << endl;
    }
  }
  return 0;
}

我们先读入n和m，然后定义一个长度为n的数组circle，对其中的元素进行初始化。接着进入循环，每次循环中定义一个计数器k来进行报数，直到报到m，将当前位置的人标记为出圈，出圈人数加1，然后循环，直到只剩一个人存活。

最后再输出存活的人的编号即可。

使用数组的解法相对简单，但不够优雅，因为我们需要不断循环，使用链表或递归解法可以更加优雅和高效。无论使用哪种方法，我们都要理解和掌握约瑟夫环问题的基本思想。

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

下一篇: C++三维建模技术

评论区

()

相似文章