2037 约瑟夫问题

N个人围成一圈，从第一个人开始报数，数到M的人出圈；再由下一个人开始报数，数到M的人出圈；…输出依次出圈的人的编号。

【输入】输入N和M。

【输出】输出一行，依次出圈的人的编号。

分析

• 将这N个人的状态保存到一维数组中，并设定初始状态为1，表示没有出圈

• 循环判断当前人是否是第m个人，如果是，这个人出圈（置为0）

• 如果出圈人数和总人数相等，表示所有人都出圈了，跳出循环

参考程序

#include <iostream>
using namespace std;
int main()
{
 int n,m,a[1100],k=1,s=0;
 cin >> n >> m;
 //把n个的初始状态置为1，表示都没有出圈
 for(int i=1;i<=n;i++) a[i] = 1;
 while(1){
  for(int i=1;i<=n;i++){
   if(a[i]!=0){
    //判断当前的人是否是第m个人
     if(k%m==0){
      cout << i << " ";
      a[i] = 0; //表示找到这个人，出圈
     s++;
     }
     k++;
     if(k>m) k = 1;
   }
  }
  //如果出圈的人与总人数相等，那么跳出循环
  if(s==n) break; 
 } 
 return 0;
}