報數
題目描述
有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將報的數字保存下來，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/1839.html
標籤：C++