首页 > 代码库 > 圆环游戏

圆环游戏

 

【题目描述】

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

 

圆环游戏