题目描述 求解约瑟夫(Joseph)问题。有n个小孩围成一圈,给他们从1开始依次编号,从编号为1的小孩开始报数,数到第m个小孩出列,然后从出列的下一个小孩重新开始报数,数到第m个小孩又出列,…,如此反复直到所有的小孩全部出列为止,求整个出列序列。 如当n=6,m=5时的出列序列是5,4,6,2,3,1。
1≤n,m≤20
输入 n m的值 输出 出列序列 样例输入 6 5 样例输出 5 4 6 2 3 1
代码如下:
#include <bits/stdc++.h>
using namespace std;
int n,m,nt[25],x;//x为坐标
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
nt[i]=i+m-1;//nt数组表示:地i个数字的下m个坐标位置
if(nt[i]>n){//越边界处理
nt[i]-=n;
}
}
x=1;
for(int j=1;j<=n;j++){
cout<<nt[x];//输出m个后
x=nt[x]+1;//坐标移动至m个后的后一个
int t=x;
//出列处理 {
for(int i=1;i<=m;i++){//把出列的前m个+1;
t--;
if(nt[t]==-1){//找到了的跳过 标记在33行
while(nt[t]>-1){
t--;
}
}
if(t<=0)//越边界处理
t+=n;
nt[t]++;//++
if(nt[t]>n){
nt[t]=1;//nt数组越边界处理
}
}
// }
nt[x]=-1;//找到了的标记一下
}
return 0;
}