USTC机试—约瑟夫环的问题
唯一注解:此处不用推导出的公式。而是利用队列的方法,直接将报号为指定数字前的数据压入到队列结尾,如此往复循环,则可以输出正确结果
//约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
#include<stdio.h>//队列方法一直将数据用队列循环即可
#include<queue>
using namespace std;
int main(){
queue<int> q;
int n,m;//n记录人数,m记录要报的号
while(scanf("%d%d",&n,&m)!=EOF){
for(int i=1;i<=n;i++){//先将编号压入栈中
q.push(i);
}
while(!q.empty()){
for(int i=1;i<m;i++){
q.push(q.front());//从头开始将m之前的数据写入队列尾
q.pop();
}
printf("%d ",q.front());//输出当前报号为m的编号
q.pop();//弹出此数据
}
printf("\n");
}
return 0;
}