標題:
資料結構 204 最後報告的幸運兒(易)
[打印本頁]
作者:
may
時間:
2025-3-25 12:25
標題:
資料結構 204 最後報告的幸運兒(易)
資料結構 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
時間:
2025-3-25 12:30
//#include <iostream>
//#include <queue>
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, X;
cin >> N >> X; // 讀取 N 和 X
queue<int> q;
for (int i = 1; i <= N; i++) {
q.push(i); // 初始化佇列，將 1~N 依序加入
}
while (q.size() > 1) { // 當佇列內學生數量大於 1 時繼續執行
for (int i = 1; i < X; i++) { // 報數 1 到 X-1
q.push(q.front()); // 把前端學生放到佇列尾端
q.pop(); // 移除舊的前端
}
q.pop(); // 報數到 X 的學生出列
}
cout << q.front() << endl; // 剩下最後一名學生，輸出他的座號
return 0;
}
複製代碼
回復
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 筆測資涵蓋了不同的學生數與抽牌數字，可以幫助你測試程式的正確性！
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)
Powered by Discuz! 7.2
