82. 衣服工廠生產三種尺寸(S,M,L)與三種顏色(R,G,B)的
T-shirt，T-shirt 以尺寸與顏色分辨，例如 M-B 代表
尺寸為 M 顏色為 B 的 T-shirt。若衣架上有 9 件 Tshirt，由左至右依序為 MB, LB, LR, SG, SB, SR,
MG, LG, MR。機器人負責將 T-shirt 重新排序成 SR,
MR, LR, SG, MG, LG, SB, MB, LB。機器人每一回合
都會挑出兩件 T-shirt 並交換位置。請問機器人最少
要執行幾回合動作才能將 T-shirt 排序完成？
(A) 4 次
(B) 5 次
(C) 6 次
(D) 8 次

答案：登入後查看
統計： A(17), B(12), C(8), D(5), E(0) #3466915

詳解 (共 3 筆)

#7245272
這是一個經典的排列置換（Permutat...
(共 2614 字，隱藏中）
前往觀看
2
0
#6516706
順序 SR MR LR...
(共 317 字，隱藏中）
前往觀看
2
1
#7380889

老師好！這題在資訊科技教甄（特別是高中職教甄、或是運算思維專題）中，屬於「演算法與離散數學（置換群與循環分解）」的經典題目。

閱卷老師在改這類「最少交換次數」的題目時，最標準且能拿滿分的解法是利用「獨立循環分解（Disjoint Cycles）」。只要推導出循環數量，就能直接套用公式秒殺，同時也能寫出無懈可擊的嚴謹步驟。

以下為您整理出最符合閱卷標準的詳細解題步驟與範例說明：

核心解題觀念：置換群與循環分解（Cycle Decomposition）

在一個陣列中，若只能透過「兩兩交換（Swap）」來排序，要達到最少交換次數，其底層邏輯是將所有元素拆解成數個「獨立循環（Cycles）」。

  • 公式：$\text{最少交換次數} = N - C$

    • $N$：總元素個數。

    • $C$：獨立循環的總個數。

  • 個別循環性質：對於一個長度為 $L$ 的循環（即有 $L$ 個元素放錯位置且形成互推關係），將其導正回正確位置所需的最少交換次數為 $L - 1$ 次。如果元素本來就在正確位置上，其循環長度為 $1$，所需交換次數為 $1 - 1 = 0$ 次。

詳細解題步驟

步驟一：位置對齊與目標分析

首先，我們將「初始狀態」與「目標狀態」依位置（編號 1 到 9）對齊，找出每個元素目前在哪裡以及應該去哪裡。

位置編號 1 2 3 4 5 6 7 8 9
初始狀態 MB LB LR SG SB SR MG LG MR
目標狀態 SR MR LR SG MG LG SB MB LB

步驟二：找出所有獨立循環（Cycles）

我們從第 1 個位置開始追蹤，順著「目前元素」應該要去的「目標位置」一路連下去，直到連回起點形成一個封閉迴路：

  1. 循環一：

    • 位置 1 的 MB：目標位置在 8。

    • 位置 8 的 LG：目標位置在 6。

    • 位置 6 的 SR：目標位置在 1（回到起點）。

    • 形成循環：(位置 1 $\rightarrow$ 8 $\rightarrow$ 6 $\rightarrow$ 1)，長度 $L_1 = 3$。

  2. 循環二：

    • 找下一個未處理的位置 2，位置 2 的 LB：目標位置在 9。

    • 位置 9 的 MR：目標位置在 2（回到起點）。

    • 形成循環：(位置 2 $\rightarrow$ 9 $\rightarrow$ 2)，長度 $L_2 = 2$。

  3. 循環三：

    • 位置 3 的 LR：目標位置就在 3（已在正確位置）。

    • 形成循環：(位置 3)，長度 $L_3 = 1$。

  4. 循環四：

    • 位置 4 的 SG：目標位置就在 4（已在正確位置）。

    • 形成循環：(位置 4)，長度 $L_4 = 1$。

  5. 循環五：

    • 位置 5 的 SB：目標位置在 7。

    • 位置 7 的 MG：目標位置在 5（回到起點）。

    • 形成循環：(位置 5 $\rightarrow$ 7 $\rightarrow$ 5)，長度 $L_5 = 2$。

步驟三：計算最少回合數

  • 總元素個數 $N = 9$

  • 獨立循環總數 $C = 5$（分別為上述的 5 個循環）

套用公式：

$$\text{最少交換次數} = N - C = 9 - 5 = 4 \text{ 回合}$$

或者以各循環長度分別計算：

  • 循環一：$3 - 1 = 2$ 次

  • 循環二：$2 - 1 = 1$ 次

  • 循環三：$1 - 1 = 0$ 次

  • 循環四：$1 - 1 = 0$ 次

  • 循環五：$2 - 1 = 1$ 次

  • $\text{總計} = 2 + 1 + 0 + 0 + 1 = 4 \text{ 回合}$。

機器人操作範例說明（4 回合模擬過程）

為了向閱卷老師證明 4 回合確實可行，以下列出每一回合具體的交換代碼與狀態變化（粗體字代表該回合被交換的兩件 T-shirt）：

  • 初始狀態： [MB, LB, LR, SG, SB, SR, MG, LG, MR]

  • 第 1 回合：處理循環一，交換位置 1 的 MB 與位置 6 的 SR。

    • 狀態變為：[SR, LB, LR, SG, SB, MB, MG, LG, MR] （SR 已歸位）

  • 第 2 回合：繼續處理循環一，交換位置 6 的 MB 與位置 8 的 LG。

    • 狀態變為：[SR, LB, LR, SG, SB, LG, MG, MB, MR] （LG 與 MB 均歸位，循環一處理完畢）

  • 第 3 回合：處理循環二，交換位置 2 的 LB 與位置 9 的 MR。

    • 狀態變為：[SR, MR, LR, SG, SB, LG, MG, MB, LB] （MR 與 LB 均歸位，循環二處理完畢）

  • 第 4 回合：處理循環五，交換位置 5 的 SB 與位置 7 的 MG。

    • 狀態變為：[SR, MR, LR, SG, MG, LG, SB, MB, LB] （MG 與 SB 均歸位，全數排序完成）

答題結論

機器人最少要執行 4 回合 動作才能將 T-shirt 排序完成。

0
0