0

这段代码没有通过所有的测试用例，有人可以帮忙吗？我只通过了直截了当的测试，然后它就失去了精度。

import math
import unittest


class IntegerMultiplier:

    def multiply(self, x, y):
        if x < 10 or y < 10:
            return x * y

        x = str(x)
        y = str(y)

        m_max = min(len(x), len(y))
        x = x.rjust(m_max, '0')
        y = y.rjust(m_max, '0')

        m = math.floor(m_max / 2)

        x_high = int(x[:m])
        x_low = int(x[m:])

        y_high = int(y[:m])
        y_low = int(y[m:])

        z1 = self.multiply(x_high, y_high)
        z2 = self.multiply(x_low, y_low)
        z3 = self.multiply((x_low + x_high), (y_low + y_high))
        z4 = z3 - z1 - z2

        return z1 * (10 ** m_max) + z4 * (10 ** m) + z2


class TestIntegerMultiplier(unittest.TestCase):

    def test_easy_cases(self):
        integerMultiplier = IntegerMultiplier()

        case2 = integerMultiplier.multiply(2, 2)
        self.assertEqual(case2, 4)

        case3 = integerMultiplier.multiply(2, 20000)
        self.assertEqual(case3, 40000)

        case4 = integerMultiplier.multiply(2000, 2000)
        self.assertEqual(case4, 4000000)

    def test_normal_cases(self):
        intergerMultiplier = IntegerMultiplier()

        case1 = intergerMultiplier.multiply(1234, 5678)
        self.assertEqual(case1, 7006652)

if __name__ == '__main__':
    unittest.main()

对于第一个测试用例，'test_easy_cases' 都通过了其他两种情况，我得到错误，例如AssertionError: 6592652 != 7006652

4

1 回答 1

1

在选择时，您为以下所有分解和组合m选择一个基础。我推荐一个具有关于因子长度平均值的长度表示法。 我“不”知道为什么一次又一次地尝试使用十进制数字运算来实现 Karatsuba 乘法 - 您需要重新检查两个地方：

  • 将因子 f 拆分为高和低时，低需要为 f mod m，高 f // m
  • 在作文（ 中的最后一个表达式IntegerMultiplier.multiply()）中，您需要坚持使用m(and 2×m) -m_max每次使用都是错误m_max的不是偶数。
于 2019-07-21T10:25:41.760 回答