#21896: 我的思考過程,和最後的演算法


aecho1028@gmail.com (鮪魚)

學校 : 不指定學校
編號 : 124759
來源 : [114.34.229.103]
最後登入時間 :
2020-07-30 14:45:00
c830. 第一題:小數加法 -- 2018資訊學科能力競賽高職組高雄市 | From: [114.34.229.103] | 發表日期 : 2020-07-29 17:32

 

從範例,可以觀察到一個現象,

 

以10進位來看 ~

123 + 45 = 168

 

從最後面,遞迴地處理7進位到最前面的位數,

 

168 => 171 //< 個位數的 8,進位成 11

171 => 201 //< 十位數的 7,進位成 10

 

然後就可以輸出結果了…。

 

------------------- 分隔線 ------------------

依照上面的思路,可以用Greedy algorithm,從低位數開始,處理到最高位數。

 

但是,上面的思考方式,遇到這一組測資,就會出錯。

 

6 + 6 = 12

 

依照7進位的算法, 6 + 6 = 15。

15才是正確答案。

 

所以,不能先把2個數字加總之後,再處理。而是分別把2個數字,從低位數,處理到最高位數,依順累加起來,然後檢查7進位的結果。

 

接著就是照上面的步驟下去實做。

 

但是計算過程中,會遇到 float的精確度的問題。也就是原本以為的 0.1,其實是類似0.99999999981237 這樣的數值。

因為浮點數在記憶體裡的儲存方式,它存的是一個近似值。所以會有些微失真的情形。

 

而這個失真的情形,也造成了幾個test case,我沒處理好,fail掉的情形…。

 

 

 

 

 

 

 

 
ZeroJudge Forum