29. Cheapest Base (CPE10466, UVA11005) - CPE一顆星解答與說明
CPE一顆星49題解答 - pdf 電子檔，售價 199 元，
購買電子檔可將筆記與完整解答帶著走，
坐車、上課時皆可隨時複習，
不受網路或廣告影響，
若有需要請來信購買 greens2314@gmail.com
題目
- 使用0~9A~Z來表示進制中使用的字元
- 最大進制數是 36，會用到數字 0 ~ Z(35)
- 最小進制數是 2，用數到 0~1
- 計算可表達此數的最小墨水量，與其使用的進制數
輸入說明
- 輸入筆數少於 25 筆
- 第 1 行為資料筆數
- 每一組測試資料包含：
- 前 4 行各有 9 個整數
- 共 4 * 9 = 36個數字，依序對應 09~AZ 表示的墨水量
- 查詢數量
- 一行包含一個要查詢的數字
輸出說明
- 每組資料輸出要先印 Case 加上編號 :，從 1 開始
- 每筆查詢結果要印 Cheapest base(s) for number 數字 : 最少墨水量的進制數
- 每一組資料要間隔一行
解題技巧
- 0~9A-Z 與數字的對應關係
- 進制轉換
- 10 進制轉 2~36 進制
- 10 進制轉 2 進制
- 10 進制轉 5 進制
- 短除法
- 取商數，使用 /
- 取餘數，使用 %
解題過程
取得輸入
- 取得組數使用 nextInt()
- 根據組數，使用 for 迴圈讀每一組的資料
輸出每一組資料的編號
- 宣告 count 變數，紀錄資料的編號
- 每讀取一組資料，count 變數要累加 1
讀取墨水成本
- 前 4 行各有 9 個整數
- 共 4 * 9 = 36 個數字，依序對應 09~AZ 表示的墨水量
- 宣告長度為 36 的陣列，儲存09~AZ每個字的墨水成本
- 宣告 int[] ink = new int[36]
- 0 ~ 35 的索引位置，正好也進制會使用的數字
- 可使用 0 ~ 35 的索引位置來存取對應的墨水成本
取得查詢的數量與數字
- 數量
- 使用 nextInt()
- 數字
- 使用 for 迴圈讀每一個查詢數字
- 根據題目要求印出資料
計算數字轉 2 ~ 36進制的墨水成本
- 宣告長度為 37 的成本陣列 cost
- 儲存轉 2 ~ 36 進制，印刷每個字的墨水成本
- 使用進制數 2 ~ 36 對應 陣列索引位置 0 ~ 36
- 最大的索引位置是36，則陣列長度須為 37
- 使用 for 迴圈，產生 2 ~ 36 的進制數
- 使用 while 迴圈執行短除法
- 當目標數字(被除數) 除以 進制數 取餘數後，剛好可透過餘數(陣列索引)讀取墨水成本
- 進制成本= cost[進制數2~26]，將讀取到的墨水成本累加到進制成本中
- 更新被除數 = 目標數字 除以 進制數，取商數
紀錄最小成本
- 宣告變數 min 紀錄最小成本
- 初始值為 Integer.MAX_VALUE
- 初始值為一個很大的數值，讓第一次計算的成本取代最小值
- 結束短除法後
- 判斷此進制墨水成本是否小於目前的最小成本值，若小於則更新最小值
將最小成本的進制數印出
- 使用 for 迴圈，逐一檢查 2 ~ 36進制的墨水成本
- 判斷成本是否等於最小值，若等於則印出進制數
- 最小成本的進制數可能會有多筆，使用空白隔開
處理每組資料中間的空行
- 判斷目前處理的組數索引是否等於組數的長度減1
- 等於：表示資料是最後一組，不需要再印出換行
- 不等於：表示還有資料，要印出換行，跟下一組隔開
留言
張貼留言