漫畫:如何實現大整數相加?
在程式中列出的 “豎式” 究竟是什麼樣子呢?我們以 426709752318 + 95481253129 為例,來看看大整數相加的詳細步驟:
第一步 ,把整數倒序儲存,整數的個位存於陣列0下標位置,最高位存於陣列長度-1下標位置。之所以倒序儲存,更加符合我們從左到右訪問陣列的習慣。
第二步 ,建立結果陣列,結果陣列的最大長度是較大整數的位數+1,原因很明顯。
第三步 ,遍歷兩個陣列,從左到右按照對應下標把元素兩兩相加,就像小學生計算豎式一樣。
例子中,最先相加的是陣列A的第1個元素8和陣列B的第1個元素9,結果是7,進位1。把7填充到Result陣列的對應下標,進位的1填充到下一個位置:
第二組相加的是陣列A的第2個元素1和陣列B的第2個元素2,結果是3,再加上剛才的進位1,把4填充到Result陣列的對應下標:
第三組相加的是陣列A的第3個元素3和陣列B的第3個元素1,結果是4,把4填充到Result陣列的對應下標:
第四組相加的是陣列A的第4個元素2和陣列B的第4個元素3,結果是5,把5填充到Result陣列的對應下標:
以此類推......一直把陣列的所有元素都相加完畢:
第四步 ,把Result陣列的全部元素再次逆序,去掉首位的,就是最終結果:
原文釋出時間為:2018-11-19
本文作者:小灰
本文來自雲棲社群合作伙伴“ ofollow,noindex">程式設計師小灰 ”,瞭解相關資訊可以關注“ 程式設計師小灰 ”。