2037 約瑟夫問題

N個(gè)人圍成一圈，從第一個(gè)人開始報(bào)數(shù)，數(shù)到M的人出圈；再由下一個(gè)人開始報(bào)數(shù)，數(shù)到M的人出圈；…輸出依次出圈的人的編號(hào)。

【輸入】輸入N和M。

【輸出】輸出一行，依次出圈的人的編號(hào)。

分析

• 將這N個(gè)人的狀態(tài)保存到一維數(shù)組中，并設(shè)定初始狀態(tài)為1，表示沒有出圈
• 循環(huán)判斷當(dāng)前人是否是第m個(gè)人，如果是，這個(gè)人出圈（置為0）
• 如果出圈人數(shù)和總?cè)藬?shù)相等，表示所有人都出圈了，跳出循環(huán)

參考程序

#include <iostream>
using namespace std;
int main()
{
    int n,m,a[1100],k=1,s=0;
    cin >> n >> m;
    //把n個(gè)的初始狀態(tài)置為1，表示都沒有出圈
    for(int i=1;i<=n;i++) a[i] = 1;
    while(1){
        for(int i=1;i<=n;i++){
            if(a[i]!=0){
                //判斷當(dāng)前的人是否是第m個(gè)人
                 if(k%m==0){
                    cout << i << " ";
                    a[i] = 0; //表示找到這個(gè)人，出圈
                    s++;
                 }
                 k++;
                 if(k>m) k = 1;
            }
        }
        //如果出圈的人與總?cè)藬?shù)相等，那么跳出循環(huán)
        if(s==n) break; 
    } 
    return 0;
}