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;
}