0

我正在尝试使用 karatsuba 乘法将两个数字相乘。我的 java 代码不工作。我使用字符串作为参数和参数，以便我们可以将两个 n 位数字相乘（n 是偶数）。另外，我不想使用 long 或 BigInteger。请帮我找出我的代码错误。

class karat{

public static String karatsuba(String first, String second){

    if(first.length() <= 1 || second.length() <= 1)
        return String.valueOf(Long.parseLong(first)*Long.parseLong(second));

    String a = karatsuba(first.substring(0, first.length()/2), second.substring(0, second.length()/2));

    String b = karatsuba(first.substring(first.length() - first.length()/2, first.length()), second.substring(second.length() - second.length()/2, second.length()));

    String c = karatsuba(String.valueOf(Long.parseLong(first.substring(0, first.length()/2)) + Long.parseLong(first.substring(first.length() - first.length()/2, first.length()))), String.valueOf(Long.parseLong(second.substring(0, second.length()/2)) + Long.parseLong(second.substring(second.length() - second.length()/2, second.length()))));

    String d = String.valueOf(Long.parseLong(c) - Long.parseLong(b) - Long.parseLong(a));

    return String.valueOf(((int)Math.pow(10, first.length()))*(Long.parseLong(a)) + (((int)Math.pow(10, first.length()/2))*Long.parseLong(d)) + (Long.parseLong(c)));
}

public static void main(String[] args){
        String result = karatsuba("1234", "5678");
        System.out.println(result); }
}

您能否也请完善我的代码。

乘法传递的数字 - 1234 和 5678

输出为 - 6655870（不正确）

输出应该是 - 7006652（正确）

谢谢

4

2 回答 2

1

首先，我尝试查看您的代码，它让程序员迷失了方向，在我们进入解决方案之前几乎没有什么东西。

一般建议。像你一样将字符串转换为值并来回转换不是一个好习惯，它不是这样工作的。我也尝试调试您的代码，这只是魔鬼圈。

所以我会从检查值长度和最大值开始。

如果其中一个值小于 2 的长度，则意味着每件小于 10 的事物都进行乘法运算，否则进行 karatsuba 递归算法。

这是解决方案：

public static long karatsuba(long num1, long num2) {

    int m = Math.max(
            String.valueOf(num1).length(),
            String.valueOf(num2).length()
    );

    if (m < 2)
        return num1 * num2;

    m = (m / 2) + (m % 2);

    long b = num1 >> m;
    long a = num1 - (b << m);
    long d = num2 >> m;
    long c = num2 - (d << m);

    long ac = karatsuba(a, c);
    long bd = karatsuba(b, d);
    long abcd = karatsuba(a + b, c + d);

    return ac + (abcd - ac - bd << m) + (bd << 2 * m);
}

一些测试；

public static void main(String[] args) {
    System.out.println(karatsuba(1, 9));
    System.out.println(karatsuba(1234, 5678));
    System.out.println(karatsuba(12345, 6789));
}

输出将是

9
7006652
83810205

它比你的 Stringish 代码更痛苦。顺便说一句，该解决方案的灵感来自 wiki 中的pesudo和 this class。

于 2017-08-20T18:04:59.213 回答
0

有趣的算法。一个错误在于

return String.valueOf(((int)Math.pow(10, first.length()))*(Long.parseLong(a)) + (((int)Math.pow(10, first.length()/2))*Long.parseLong(d)) + (Long.parseLong(c)));

最后，它应该Long.parseLong(b)代替Long.parseLong(c).

在中间计算中，可能会发生两个字符串的长度不同的情况。这也不能正常工作。

请允许一些评论以改进实施。使用字符串的想法似乎允许大数字，但随后您引入了Long.parseLong()or之类的东西(int)Math.pow(10, first.length())，将您限制在longorint范围内。

如果您真的想做大数，请编写您自己的基于字符串的加法和 10 次方乘法（通过附加一些零，这很简单）。

并且，尽量避免使用 a、b、c 或 d 之类的名称 - 很容易忘记它们的含义，就像您最初的错误一样。例如，来自Wikipedia的名称稍微好一点（使用 z0、z1 和 z2），但仍然不完美......

于 2017-08-20T15:49:57.940 回答