-3

以下是我尝试实现递归 Karatsuba 算法的 python 代码。我没有得到输入 1234、5678 的正确值。加上值 55,15 我收到错误消息。我为此绊倒了几个小时，请您帮忙。谢谢

x = input("Enter a number: ")
y = input("Enter another number: ")



def ksml (p,q):
    p = str(p)
    q = str (q)
    n = len(p)
    # mid is to be made int because when used to strip num, range has to be in num not float
    mid = int(n/2)
    if n == 1:
        p = int(p)
        q = int(q)
        product = p * q
        return product
    else:
        a = int(p[0:mid])
        b = int(p[mid:])
        c = int(q[0:mid])
        d = int(q[mid:])
        # parts of the prodcut
        k = ksml(a,c)
        l = ksml (b,d)
        m = ksml (a+b,c+d) - k - l
        product = (10 ** n * k) + (10 ** mid * m) + l
        return product

print(ksml(x,y))

我得到的错误是

Enter a number: 55
Enter another number: 15
Traceback (most recent call last):
  File "test1.py", line 27, in <module>
    print(ksml(x,y))
  File "test1.py", line 23, in ksml
    m = ksml (a+b,c+d) - k - l
  File "test1.py", line 19, in ksml
    d = int(q[mid:])
ValueError: invalid literal for int() with base 10: ''
4

1 回答 1

0

您的问题在这里：mid = int(n/2)因为您正在转换为int，所以结果可能为零。您可能应该四舍五入，但我对算法的了解不够确定。

考虑一下单位数字会发生什么p。n=len(p)现在是 0.5，mid=int(n/2)现在是零，p[0:mid]此时实际上只是一个空字符串。尝试将空字符串放入 anint会导致错误。

如果我是正确的，你应该四舍五入（这样你至少会得到 1 的值）你应该使用math.ceil：

import math
mid = math.ceil(n) # will be 1 if n was 0.5
于 2019-09-15T06:03:28.690 回答