【題目鏈接】

ybt 2037：【例5.4】約瑟夫問題
ybt 1334：【例2-3】圍圈報數
洛谷 P1996 約瑟夫問題

【題目考點】

1. 循環遍歷數組

假設數組下標為1~n，循環控制變量i從1遍歷到n后，再重新賦值為1，再遍歷到n，重復此過程，直到滿足某一條件，跳出循環。

int i = 1; while(某種循環條件) {//...i++; //或將這一段寫為：i = i + 1 == n ? 1 : i + 1;if(i == n)i = 1; }

如果數組下標為0~n-1，可以寫為：

for(int i = 0; 某種循環條件; i = (i + 1)%n) {//... }

2. 隊列

3. 鏈表

考察：單鏈表、環形鏈表、stl list

【解題思路】

解法1：循環遍歷數組

設布爾數組，表示某號人是否已經出列。循環遍歷數組，如果遇到不在列的人，就跳過，從當前位置開始找到m-1個在列的人，再找下一個在列的人，就是要出列的人。將該人編號輸出，出列。重復上述過程n次，每次讓一個人出列。

解法2：使用隊列

假設這n個人排成一隊，在隊頭數人數，每數一個人，就讓這個人出隊，然后在隊尾入隊。數到第m個人時，輸出這個人的編號，讓該人出隊，不再入隊。重復上述過程n次。

解法3：環形隊列

模擬，每個人作為一個結點，依次指向下一個結點，形成單鏈表，最后一個結點的下一個結點設為第一個結點，形成環狀鏈表。模擬題中過程，設一個指針指向第一個結點，指針向后移動m-1次，指向第m結點，將此時指向的結點的值輸出，而后刪除該結點，并指向下一個結點，如此循環n次。

【題解代碼】

解法1：循環遍歷數組

#include <bits/stdc++.h> using namespace std; int main() {bool isOut[1005] = {};//isOut[i]:第i人是否出列，初值為false，都沒有出列。使用下標：0~n-1 int n, m, p = 0;//p:當前位置cin >> n >> m;for(int i = 1; i <= n; ++i)//一共輸出n次{for(int j = 0; j < m-1; ++j)//找m-1個在列的人{while(isOut[p] == true)p = (p+1)%n;p = (p+1)%n;}//此時p指向第m-1個數的下一個位置 while(isOut[p] == true)//再找下一個人，就是第m個在列的人p = (p+1)%n;isOut[p] = true;//此時p指向第m個人 讓該人出列 cout << p+1 << ' ';//下標從0開始，人編號從1開始，從下標轉為人編號，需要加1 }return 0; }

解法2：使用隊列

#include <bits/stdc++.h> using namespace std; int main() {queue<int> que;int n, m;cin >> n >> m;for(int i = 1; i <= n; ++i)que.push(i);for(int i = 1; i <= n; ++i){for(int i = 1; i <= m - 1; ++i){//將隊頭的人出隊后，再入隊到隊尾que.push(que.front()); que.pop();}cout << que.front() << ' ';//此時隊頭是要出列的人 que.pop();}return 0; }

解法2：環狀鏈表

• 寫法1：環狀單鏈表

#include <bits/stdc++.h> using namespace std; struct Node {int val;int next; }; Node node[1005];//結點池 int p = 1; int main() {int n, m;cin >> n >> m;int first, tail, np;//first：指向第一個結點 tail：尾指針 np：新結點地址 np = p++;//第一個結點的位置node[np].val = 1;first = tail = np;for(int i = 2; i <= n; ++i){//尾插法構建單鏈表np = p++;node[np].val = i;node[tail].next = np;tail = np;}node[tail].next = first;//最后一個結點的next指向第一個結點，形成環狀鏈表 int sel = tail, del;//判斷是否要刪掉sel的下一個結點，最初sel的next就是第1結點， del：待刪除的結點for(int i = 1; i <= n; ++i){for(int j = 1; j <= m-1; ++j)//最初sel的next是第1結點。向后移動m-1次后，sel的next就是第m個結點。 sel = node[sel].next;del = node[sel].next;//sel的下一個結點del就是應該刪除的結點node[sel].next = node[del].next;//刪除結點del，刪除后，sel的下一個結點，就是下面要看的m個結點中的第一個 cout << node[del].val << ' ';//輸出被刪除結點的值，也就是出列的人的編號 }return 0; }

• 寫法2：使用stl list，實際是雙向鏈表

#include<bits/stdc++.h> using namespace std; int main() {list<int> li;int n, m, ct = 0;//ct：計數，看數了幾次 cin >> n >> m;for(int i = 1; i <= n; ++i)//將1~n用尾插法插入鏈表 li.push_back(i);list<int>::iterator it = li.begin(), ie;//it：迭代器，指向第一個結點，ie：指向要被刪除的結點 while(li.empty() == false)//只要鏈表不空，就不斷讓人出列（刪除結點） {ct++;//數人數 if(ct == m)//如果數到第m人 {ie = it;//準備刪除此時it指向的結點 cout << *ie << ' ';//輸出結點值，也就是人的編號 it--;//it指向ie前一個結點 li.erase(ie);//刪除ie結點 ct = 0;//重新計數 }it++;//it指向下一個結點 if(it == li.end())//如果it已經遍歷到鏈表末尾，那么重新指向鏈表第一個結點，模擬對環形鏈表的遍歷方式 it = li.begin();}return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 2037：【例5.4】约瑟夫问题 | 1334：【例2-3】围圈报数 | 洛谷 P1996 约瑟夫问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。