在方案球拍中乘以Big-int

我在方案中實現了一個「big-int」作爲列表，所以第一個元素是數字的符號（+或 - ），以下是數字本身，首先的操作，然後幾十等在方案球拍中乘以Big-int

例如：(+ 0 0 1)爲100，(- 9 2 3 1)是-1329等

我現在需要的是落實對大整數加法，減法和乘法以這種方式實施。我已經做了加法和減法，有人可以用乘法幫助我嗎？

2011-12-01 DanielY

如果您已經完成了添加，那麼乘法非常簡單（只需按照正常程序在紙上手動乘法即可）。 –

我也這麼認爲。但是，與b相乘實際上是給自己增加一個b次，但是你不能將bigint轉換爲它的數字值，所以你不能告訴運行多少次add – DanielY

我不是在說重複的加法，我是談論[長乘法]（http://en.wikipedia.org/wiki/Multiplication_algorithm#Long_multiplication）。 –

將問題分解成小塊。首先，編寫一個將Big-int乘以一個數字的函數。然後，將這個擴展（使用Greg Hewgill的提示，你可能知道如何在紙上做到這一點）到一個將Big-int乘以數字列表的函數。最後，將其封裝在一個函數中，該函數接受兩個Big-ints，剝離符號，然後調用您以前的函數。

我強烈建議你在開發它們之前編寫這些函數的測試用例。

來源

2011-12-01 18:39:41

我明白我需要做什麼。但是因爲整數被保存爲列表，所以它使事情變得更加困難 – DanielY

更具體。你能寫一個函數來把一個Big-int乘以一個數字嗎？如果沒有，你會堅持[設計配方]（http://www.htdp.org/）的哪一步？ –

我寫了一個函數，它將一個大的整數乘以一個數字。其餘的是problamatic。更何況我寫的加法函數，在某些情況下不起作用 - 比如當你有進位到下一個數字時......我在這些情況下需要幫助 – DanielY

這裏是一個衆所周知的分而治之的方法，以大INT乘法：

http://ozark.hendrix.edu/~burch/csbsju/cs/160/notes/31/1.html

這種方法切斷兩個數字成兩半，並處理它們遞歸。它非常快速，而且很容易實現，儘管可能看起來很長。我強烈推薦它。它採用其他語言的所有約10行代碼，在計劃中可能更少:)。

來源

2011-12-03 16:22:33 djhaskin987

感謝您的算法！考慮一下我在實現時遇到的幾點：在這種情況下，大整數是一個數字列表。你如何將列表分成兩半？當存在n = 1的情況時，即使像a * b這樣簡單的計算在這種情況下可能會變得複雜，因爲a * b可能是2位結果，然後需要對列表進行修改。再次感謝算法，儘管這裏有一些需要考慮的事情。有什麼建議麼？ – DanielY

在方案球拍中乘以Big-int

回答

相關問題