報數

題目描述

　　有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將報的數字保存下來。