小编Kha*_*han的帖子

我一直在尝试在java中实现Karatsuba算法而不使用BigInteger.仅当整数相同且位数相同时,我的代码才适用.我没有得到正确的答案,但我得到的答案非常接近正确答案.例如,当12*12时,我得到149.我无法弄清楚我的代码有什么问题,因为我相信我做的一切都是正确的(通过本书).这是我的代码.

public static void main(String[] args) {
    long ans=karatsuba(12,12);
    System.out.println(ans);
}

private static long karatsuba(long i, long j) {
    if (i<10 || j<10){
        return i*j;
    }
    int n=getCount(i);
    long a=(long) (i/Math.pow(10, n/2));
    long b=(long) (i%Math.pow(10, n/2));
    long c=(long) (j/Math.pow(10, n/2));
    long d=(long) (j%Math.pow(10, n/2));

    long first=karatsuba(a,c);
    long second=karatsuba(b,d);
    long third=karatsuba(a+b,c+d);

    return ((long) ((first*Math.pow(10, n))+((third-first-second)*Math.pow(10,n/2))+third));
}

private static int getCount(long i) {
    String totalN=Long.toString(i);
    return totalN.length();
}

编辑:

感谢Ziyao Wei,问题是用"第二"取代"第三".但是我现在有另一个问题是:

如果叫karatsuba(1234,5678),我会得到正确答案,但是当我打电话给karatsuba(5678,1234)时,我得不到正确答案.任何人都可能知道原因吗？我的更新代码是:

public static void main(String[] args) {
    //wrong answer
    long ans=karatsuba(5678,1234); …

我目前正致力于使用mergesort计算反演练习.我面临的问题是当我有小型或中型数组时,结果非常好,但是如果我使用一个非常大的测试用例(一个100,000个整数的数组),它就不会给我正确的反转次数.我不知道为什么会发生这种情况.这是我的代码:

static int [] helper;
static long count=0;
static Integer [] arr3;

private static void mergeSortMethod(Integer[] arr3) {
    int head=0;
    int tail=arr3.length-1;
    int mid=tail+((head-tail)/2);

    sort(arr3,head,tail);
}


private static void sort(Integer[] arr3, int low, int high) {

    if (high<=low){
        return;
    }
    int mid=low+ ((high-low)/2);

    sort(arr3,low,mid);
    sort(arr3,mid+1,high);

    merge3CountInvs(arr3,low,mid,high);

}

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) {
    int i=low;
    int j=mid+1;
    int k=low;
    //to get size of first half of array
    int nArr1Elems=(mid-low)+1;

    for (int m=low;m<=high;m++){
        helper[m]=arr3[m];

    } …