报数

题目描述

有n个小朋友做游戏，他们的编号分别是1,2,3…n。他们按照编号从小到大依次围成一个圆圈，从第一个小朋友开始从1报数，依次按照顺时针方向报数（加一），报m的人会离开队伍，然后下一个小朋友会继续从1开始报数，直到只剩一个小朋友为止。

输入格式

第一行输入两个整数，n，m。（1≤n，m≤1000）

输出格式

输出最后一个小朋友的编号，占一行。

 样例输入

10 5

样例输出

3

解法

一道较为经典的队列题。

首先要明白这题为什么可以用队列来做，“围成一个圆圈”其实就可以想象成一个类似的队列。需要一个while循环，每次循环先把队首小朋友报的数字保存下来，再把队首的小朋友踢出去，然后检查小朋友报的数字和m是否相同。如果相同，那么就把小朋友再请回来；反之，踢出去就踢出去好了。那为什么要先踢出去呢？因为小朋友们围成的是一个圆圈，而队列只是一个受限制的线性结构。从队首踢出，再回到队尾，就模拟了一个圆圈。

 1 #include <iostream>
 2 #include <queue>
 3 using namespace std;
 4 int main ()
 5 {
 6     queue<int> q;
 7     int n,m;
 8     cin>>n>>m;
 9     for(int i=1;i<=n;i++)
10     {
11         q.push(i);
12     }
13     int t=1;
14     while(q.size()>1)
15     {
16         int now=q.front();
17         q.pop();
18         if(t!=m)
19         {
20             q.push(now);
21         }
22         else
23         {
24             t=0;
25         }
26         t++;
27     }
28     cout<<q.front()<<endl;
29     return 0;
30 }

第13行的t是用来存储小朋友要报的数字，而且每当有小朋友报数=m时，t就要从1重新开始。那你可能会发现，第24行给t赋的值是0，这是因为在这个if判断之后，26行有一个t++的操作~

第16行的now是用来存储队首小朋友报的数字的，因为如果把队首小朋友踢出去了，再想获取他报的数字就很困难，所以我们就先用变量now将报的数字保存下来。

 

版权声明：本文为DYXM原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/DYXM/p/13285513.html