2037 約瑟夫問題

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

【輸入】輸入N和M。

【輸出】輸出一行，依次出圈的人的編號。

分析

• 將這N個人的狀態(tài)保存到一維數(shù)組中，并設定初始狀態(tài)為1，表示沒有出圈

• 循環(huán)判斷當前人是否是第m個人，如果是，這個人出圈（置為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個的初始狀態(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){
????//判斷當前的人是否是第m個人
?????if(k%m==0){
??????cout?<<?i?<<?"?";
??????a[i]?=?0;?//表示找到這個人，出圈
?????s++;
?????}
?????k++;
?????if(k>m)?k?=?1;
???}
??}
??//如果出圈的人與總?cè)藬?shù)相等，那么跳出循環(huán)
??if(s==n)?break;?
?}?
?return?0;
}