我目前正在閱讀一本名為 Algorithms Illuminated Part 1: Basics 的書，遇到了一些關于 Karatsuba 乘法的討論。該示例說“具有偶數 n 個數字的數字 x 可以用兩個 n/2 位數字表示，它的前半部分 a 和后半部分 b：
x = 10^(n/2) * a b。y = 10^(n/2) * c d。
x y = (10^(n/2) * a b) * (10^(n/2) * c d) = 10^n * (a * c) 10 ^(n/2) (a d b c) b*d。"
該示例使用數字 5678 * 1234，其中 56 = a、78 = b、12 = c 和 34 = d
我無法理解這 10^n/2 * a b 的來源，它們是如何從 n/2 - 數字變成這種表示形式的？還有為什么 this 和 n/2 被認為是遞回函式？它不需要呼叫自己被認為是遞回的嗎？為什么 n 與偶數或奇數有相關性？
我嘗試用偶數和奇數 N 繪制方程。我還查閱了遞回函式的定義，他們說它是一個呼叫自身的函式。我試圖理解為什么 n/2 被認為是遞回演算法。我錯過了作者如何設法達到這個等式的背景。
uj5u.com熱心網友回復：
考慮遞回演算法的一種方法是，它們將問題分解為相同型別的更小/更簡單的子問題，然后可以通過相同的演算法來解決。
Karatsuba 乘法的遞回部分在您的示例中沒有明確顯示，但考慮到您有一些函式“karatsuba(x,y)”將兩個數字 x 和 y 相乘。
通過你的公式 x y = 10^n * (a * c) 10 ^(n/2) (ad bc) b d
如您所見，此公式要求您計算其他幾個產品（ac、ad、bc、bd）。a,b,c,d 和更小（x 和 y 位數的一半。所以你可以將 karatsuba(x,y) 表示為
唐葉(x,y) = 10^n * 唐葉(a,c) 10^(n/2) * (唐葉(a,d) 唐葉(b,c)) 唐葉(b,d)
我希望“遞回性”現在更清楚了。
注意：您需要一些機制來處理演算法的基本情況（例如當 x 或 y 是單個/幾個數字時）
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/522073.html
標籤：算法递归唐叶