21xrx.com
2024-05-21 01:26:19 Tuesday
登录
文章检索 我的文章 写文章
C++数组实现约瑟夫问题的代码
2023-07-14 08:35:08 深夜i     --     --
C++ 数组 实现 约瑟夫 代码

约瑟夫问题是一个经典的数学问题,它涉及到人们的生存问题。问题的背景是:N个人围成一圈,从第一个人开始报数,报到M的人出圈,剩下的人继续从1开始报数,直到所有人都出圈。求出出圈人的顺序。

在C++中,可以使用数组来实现约瑟夫问题的求解。下面是一个简单的代码实现:


#include <iostream>

using namespace std;

int josephus(int n, int m) {

  int a[1000];

  for (int i = 0; i < n; i++) {

    a[i] = i + 1;

  }

  int i = -1, count = 0, sum = n;

  while (sum > 0) {

    i++;

    if (i >= n)

      i = 0;

    

    if (a[i] != 0) {

      count++;

    }

    if (count == m) {

      cout << a[i] << " ";

      count = 0;

      a[i] = 0;

      sum--;

    }

  }

  return 0;

}

int main() {

  int n, m;

  cout << "请输入N和M:";

  cin >> n >> m;

  josephus(n, m);

  return 0;

}

在这段代码中,我们创建了一个大小为1000的数组a来代表N个人,用i来表示当前的人的编号,用count来计数,用sum来表示还有多少人没有出圈。当count等于M时,表示当前的人应该出圈,将其对应的数组元素a[i]置为0,并将sum减1,然后打印出当前人的编号。最终,数组中剩下的元素都为0,程序结束。

总之,使用C++数组实现约瑟夫问题是一种简单有效的方法。我们可以依托C++自身的语言特性快速实现算法,大大提高程序效率及运行速度。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复