資料結構 204 最後報告的幸運兒(易)

may

資料結構 204 最後報告的幸運兒
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 公民課報告時，王老師想出了一個方法來決定學生上台報告的順序：假設班上共有 N 位學生（1 ≤ N ≤ 60），座號為 1 ~ N，老師請班長隨機抽出一張撲克牌（A,2,...,10,J,Q,K），並以 X 表示抽中撲克牌的號碼（1 ~ 13）。接著讓所有學生依照座號「由小到大」順時鐘排成一個圓圈，然後從座號 1 號學生順時鐘依序開始報數（1 ~ X），數到 X 的同學就成為第一個報告者並離開圓圈；接著從下一位學生依照相同方式繼續由 1 開始報數，決定出下一個報告者，持續上述過程直到決定出所有學生的報告順序。

(2) 請你寫出一支程式來找出：哪個座號是最後報告的幸運兒？

舉例：假設班上有 12 位學生（N = 12），班長隨機挑中的撲克牌數字是 5（X = 5）。接著，從 1 號開始順時針報數（1 ~ 5），第一位被挑中的學生是 5 號同學；再從 6 號同學繼續報數（1 ~ 5），第二位被選的是 10 號同學；再從 11 號同學繼續報數，第三位被選的是 3 號同學...以此類推，然後繼續以上相同程序。

提示：可使用類似佇列（Queue）的資料結構來紀錄相關資料。

3. 輸入輸出：
輸入說明
第 1 列：班級人數 N（1 ≤ N ≤ 60）。
第 2 列：抽中的撲克牌號碼 X（1 ≤ X ≤ 13）。

輸出說明
最後一位報告的學生座號。

範例輸入1
12
5
範例輸出1
1
範例輸入2
10
5
範例輸出2
3

may

1. //#include <iostream>
   
2. //#include <queue>
   
3. #include <bits/stdc++.h>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     int N, X;
   
8.     cin >> N >> X; // 讀取 N 和 X
   
9. 
   
10.     queue<int> q;
    
11.     for (int i = 1; i <= N; i++) {
    
12.         q.push(i); // 初始化佇列，將 1~N 依序加入
    
13.     }
    
14. 
    
15.     while (q.size() > 1) { // 當佇列內學生數量大於 1 時繼續執行
    
16.         for (int i = 1; i < X; i++) { // 報數 1 到 X-1
    
17.             q.push(q.front()); // 把前端學生放到佇列尾端
    
18.             q.pop(); // 移除舊的前端
    
19.         }
    
20.         q.pop(); // 報數到 X 的學生出列
    
21.     }
    
22. 
    
23.     cout << q.front() << endl; // 剩下最後一名學生，輸出他的座號
    
24.     return 0;
    
25. }

複製代碼

回復 1# may
-----------------------------------------------
解釋程式碼
讀取輸入
cin >> N >> X; 讀取班級人數 N 和抽中的撲克牌數字 X。

初始化佇列
使用 queue<int> q; 來建立一個**先進先出（FIFO）**的佇列，然後將 1 ~ N 依序放入佇列。

模擬報數過程

報數 X-1 次：

q.push(q.front());：將前端學生移動到隊尾，相當於他繼續留在圈內。

q.pop();：移除原本的前端，因為他已經移到隊尾。

數到 X 的學生出局：

q.pop();：數到 X 的學生直接移除，不再加入佇列。

重複上述過程，直到只剩下一名學生。

輸出最後一位學生的座號 cout << q.front() << endl; 這時候佇列內只剩最後一位學生，他就是最後報告的幸運兒。

時間複雜度分析
由於每一輪都會淘汰一位學生，因此總共執行 N-1 次報數，而每次報數最多 X-1 次，時間複雜度約為 O(NX)，在題目限制下（N ≤ 60, X ≤ 13）能夠順利執行。
---------------------------------------------
測資:
測資 00
輸入
6
2
預期輸出
5
解釋
(X=2) 移除 2

(X=2) 移除 4

(X=2) 移除 6

(X=2) 移除 3

(X=2) 移除 1

剩下 5

測資 01
輸入
8
3
預期輸出
7
解釋
(X=3) 移除 3

(X=3) 移除 6

(X=3) 移除 1

(X=3) 移除 5

(X=3) 移除 2

(X=3) 移除 8

(X=3) 移除 4

剩下 7

測資 02
輸入
10
4
預期輸出
5
解釋
(X=4) 移除 4

(X=4) 移除 8

(X=4) 移除 2

(X=4) 移除 7

(X=4) 移除 3

(X=4) 移除 9

(X=4) 移除 1

(X=4) 移除 6

(X=4) 移除 10

剩下 5

測資 03
輸入
12
6
預期輸出
7
解釋
(X=6) 移除 6

(X=6) 移除 12

(X=6) 移除 7

(X=6) 移除 2

(X=6) 移除 9

(X=6) 移除 4

(X=6) 移除 11

(X=6) 移除 5

(X=6) 移除 1

(X=6) 移除 3

(X=6) 移除 8

剩下 7

測資 04
輸入
15
5
預期輸出
13
解釋
(X=5) 移除 5

(X=5) 移除 10

(X=5) 移除 15

(X=5) 移除 6

(X=5) 移除 12

(X=5) 移除 3

(X=5) 移除 9

(X=5) 移除 14

(X=5) 移除 8

(X=5) 移除 2

(X=5) 移除 11

(X=5) 移除 4

(X=5) 移除 7

(X=5) 移除 1

剩下 13

這 5 筆測資涵蓋了不同的學生數與抽牌數字，可以幫助你測試程式的正確性！