42. Train Swapping (CPE22811, UVA299) - CPE一顆星解答與說明
CPE一顆星49題解答 - pdf 電子檔,售價 199 元,
購買電子檔可將筆記與完整解答帶著走,
坐車、上課時皆可隨時複習,
不受網路或廣告影響,
若有需要請來信購買 greens2314@gmail.com
題目
- 計算出車廂在排序過程中最小的交換次數
輸入說明
- 第一行資料筆數 n
- 每筆測資包含
- 火車長度
- 車廂編號
- 由小至大排序
輸出說明
- 根據每筆測試資料印出排序所需的最小次數
解題技巧
- 氣泡排序法
- 又稱交換排序法,顧名思故就是與相鄰的資料兩兩比較,如果數字較大者在前面,則需交換位置到後面,這樣一來可確保,數字最大者會排在最後面
- 假設目前有 5 個數字,排列情況由大到小為:9, 8, 7, 6, 5 以氣泡排序將排列改為由小到大
- 需經過 4 次掃描
解題過程
取得輸入
- 取得資料筆數
- 根據資料筆數使用 for 迴圈取得相關資料
- 取得火車長度
- 宣告長度與火車長度相同的陣列,用來儲存車廂編號
- 使用 for 迴圈逐一取得車廂編號,並存入陣列中
實作氣泡排序法
- 使用兩層 for 迴圈產生兩兩交換的索引位置
- 第一層 for 迴圈紀錄目前已完成排序的數量
- 初始值為 0,建議將最大值設為小於火車長度 – 1
- 例如:火車長度為 3 時,當最後 2 個車廂排序好,其實就已經完成排序,減 1 可省略多餘的比對
- 第二層 for 迴圈將車廂編號進行兩兩比對
- 減 1:因為目前車廂會跟下一個車廂比對,要事先減 1 ,如果沒有減 1,存取到最後一個車廂時,又找下一個車廂比對時,會遇到超出索引的錯誤
- 建議減目前已經完成排序的數量:不需要進行多餘的比對
留言
張貼留言