首页 > 代码库 > 圆环游戏
圆环游戏
【题目描述】
现有n个人按照编号1~n的顺序顺时针围成一圈,从1号开始顺时针报数,报到t的人退出圈子,然后从他的下一位开始接着报数,询问最后一个退出圈子的人在哪个位置。
【输入描述】
输入两个数n、t。
【输出描述】
输出一个数,表示答案。
【输入样例】
3 2
【输出样例】
3
【数据范围及提示】
对于30%的数据,n <= 100;
对于100%的数据,n <= 100000,1 <= t <= 100。
猴子选大王
有M个猴子围成一圈,每个有一个编号,编号从1到M。打算从中选出一个大王。经过协商,决定选大王的规则如下:从第一个开始,每隔N个,数到的猴子出圈,最后剩下来的就是大王。 输出大王的编号。
【题目分析】
约瑟夫环问题
#include <iostream>#include <cstdio>#include <cstring>using namespace std;int n,t,num=0,ans=1;struct node{ int front; int next;}a[100010];int main(){ scanf("%d%d",&n,&t); a[1].front=n;a[1].next=2; a[n].front=n-1;a[n].next=1; for(int i=2;i<n;i++) a[i].front=i-1, a[i].next=i+1; while(a[ans].front!=ans&&a[ans].next!=ans)// { num++; if(num==t) { num=0; a[a[ans].next].front=a[ans].front; a[a[ans].front].next=a[ans].next; } ans=a[ans].next; } printf("%d",ans); return 0;}
圆环游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。