25. An Easy Problem! (CPE10413, UVA10093) - CPE一顆星解答與說明
CPE一顆星49題解答 - pdf 電子檔，售價 199 元，
購買電子檔可將筆記與完整解答帶著走，
坐車、上課時皆可隨時複習，
不受網路或廣告影響，
若有需要請來信購買 greens2314@gmail.com
題目
- 一個 N 進位的數字 R ，可以被 N-1 整除，找出最小的 N
- 例如：一個 10 進位的數字 R，判斷 R 是否可以被 9 (10-1) 整除
- N 的範圍為 2~62
- 使用 0123456789A..Za..z 符號來表示 2 ~ 62的數字
輸入說明
- 每一行含有一個整數，此數的進位介於2~62
- 根據條件找出最小的進位數(也就是介於2~62的N)
輸出說明
- 如果數字不符合題目的條件，則印出 such number is impossible!字串
- 每個輸出都要換行顯示
- 輸出的數字使用 10 進制
解題技巧
- 觀念：判斷某數字是否為9的倍數
- 一個 N 進位的數字 R ，可以被 N - 1 整除，則 R 為 N-1 的倍數
- 例子：5 進位的數字 134 是否為 4 的倍數
- 1 + 3 + 4 = 8，總和 8 可被 4 (N進位 - 1)整除，所以為 5 進位
- 一個 10 進位的數字 R，判斷 R 可否被 9 整除，則 R 為 9 的倍數
- 使用的條件與判斷某數字是否為 9 的倍數的公式一樣
- 某數字的每位數相加，總和若可被 9 整除，則為 9 的倍數
- 參考影片
- https://www.youtube.com/watch?v=P4_Zmnuar1E
- 符號 0~9 / A~Z / a~z 與數字的對應關係 10個 + 26個+ 26個 = 62個
解題過程
取得輸入
- 使用 while 迴圈與 scanner.hasNextLine()，偵測是否有測試資料
- 當測試資料輸入時
- 使用 scanner.nextLine() 取得整行句子
宣告符號字串
- 符號 0~9 / A~Z / a~z 與數字的對應關係
- 10個 + 26個+ 26個 = 62個
讀取輸入資料中的每一個字元
- 使用 for 迴圈，產生從第一個 ~ 最後一個字元的位置
- 使用 String 類別提供的 charAt() 方法來取得句子中的每一個字元
找出字元在符號字串中的位置
- 使用 String 類別提供的 indexOf() 方法，可找出特定字元在符號字串中的索引位置，此索引位置可對應數字 0 ~ 61，若索引位置 = -1，表示此字元不存在字串中
- 因測資包含 + - 正負號，這些字元不存在符號字串(0~9A~Za~z)中，所以會得到 -1 ，故不需要加總
將字元所在的索引位置當作數字處理並加總
尋找最大的數字
- 讀取輸入資料中的每一個字元，判斷字元在字串中的索引位置時，可順便判斷遇到的最大數字
- 可根據這個最大數字來推測可能的進位數
- 例如：157，裡面 7 最大，可假設此數至少是使用 8 進位
根據最大數字，尋找最小的進位數
- 宣告 n 變數，紀錄找到的 n 值
- 判斷最大數字是否小於 2
- 小於 2 ：表示加總數字為 0 或 1，很明顯就是 2 進位，故 n = 2
- 大於等於 2 ：
- 使用出現過的最大數字，作為起始除數，逐一遞增到 61
- 只有 (2-1) ~ (62-1) ，也就是 1 ~ 61 的數字有機會整除加總
- 檢查加總可否被除數整除，若可整除(餘數為 0)
- 表示測資數字為除數的倍數，n = 此除數 + 1
留言
張貼留言