我做了一個程式來將兩個字串相乘，我期望1000*10 = 10000，但我得到了100000。我不知道我的邏輯哪里錯了。我也嘗試在運算式中 替換m2with但沒有任何效果，當我嘗試乘法時，我得到.m1((val3 val4) * 10**(m2))120 * 10300
def Multiply_Recursive(a, b):
if len(a) == 1 or len(b) == 1:
return str(int(a)*int(b))
else:
m = max(len(a),len(b))
m2 = m // 2
m1 = len(b) // 2
A = int(a[0:m2])
B = int(a[m2:len(a)])
C = int(b[0:m1])
D = int(b[m1:len(b)])
val1 = int(Multiply_Recursive(str(A),str(C)))
val2 = int(Multiply_Recursive(str(B),str(D)))
val3 = int(Multiply_Recursive(str(A),str(D)))
val4 = int(Multiply_Recursive(str(B),str(C)))
return str(val1 * 10**(2*m2) ((val3 val4) * 10**(m2)) val2)
num = Multiply_Recursive("1000","10")
print(num)
uj5u.com熱心網友回復：
在最后的公式中，您假設m2數字出現在拆分點的右側，并且兩個拆分的數字數量相同。通常兩者都不是真的。
此外，由于 的定義m取決于較大的輸入，m2當a遠小于時，它可能導致由 表示的b位數超出范圍。
你可以像這樣解決這個問題：
像這樣定義
m2：m2 = len(a) // 2以這樣的方式拆分輸入，
m1并且是拆分點之后m2的位數，而不是之前的位數。所以拆分如下：A = int(a[:-m2]) B = int(a[-m2:]) C = int(b[:-m1]) D = int(b[-m1:])考慮到這一點，更改最終公式，
m1并且m2可能會有所不同。因此，例如不應該有2*m2, 但是m1 m2, ...等：return str(val1 * 10**(m1 m2) val3 * 10**m2 val4 * 10**m1 val2)
真正的 Karatsuba 演算法會確保選擇m1，m2所以它們是相同的，除非確定字串的大小是有限的，否則它不會將字串轉換為整數。它還需要一個更少的遞回呼叫。
uj5u.com熱心網友回復：
命名沒有幫助 - 只使用 ah、al、bh、bl：
def multiply_recursive(a, b):
""" Return the product of a and b.
All numbers are passed as their decimal string representations.
"""
if not a or not b:
return "0"
if len(a) == 1 or len(b) == 1:
return str(int(a)*int(b))
#
m = max(len(a), len(b))
m2 = m // 2
# different split points not suitable for common scaling of "mixed products" below
# m1 = len(b) // 2
# low parts are remainders: split from least significant end!
ah, al = a[0:-m2], a[-m2:].lstrip("0")
bh, bl = b[0:-m2], b[-m2:].lstrip("0")
# print(ah, al, bh, bl, sep=',')
ahbh = int(multiply_recursive(ah, bh))
albl = int(multiply_recursive(al, bl))
ahbl = int(multiply_recursive(ah, bl))
albh = int(multiply_recursive(al, bh))
product = str(ahbh * 100**m2 (ahbl albh) * 10**m2 albl)
# print(product)
return product
num = multiply_recursive("1000","10")
print(num)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/510105.html
標籤：Python算法递归乘法