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

全部评论

相关推荐

昨天 22:34
已编辑
重庆邮电大学 Java
快手 客户端开发 (n+5)k*16 公积金12
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务