0

我正在实现一个 Karatsuba 算法，并且遇到了这个异常。

一些相关代码（如果需要，我可以发布更多）：

从主要：

int degree = (input.nextInt() + 1);
int A[] = new int[degree];
int B[] = new int[degree];

for(int i = 0; i < degree; i++)
    A[i] = input.nextInt();
for(int i = 0; i < degree; i++)
    B[i] = input.nextInt();
product = karatsuba(A, B, degree); // LINE 22

来自唐叶：

static int[] karatsuba(int[] A, int[] B, int degree) {

    int[] A_hi = new int[degree / 2];
    int[] A_lo = new int[degree / 2];
    int[] B_hi = new int[degree / 2];
    int[] B_lo = new int[degree / 2];

    int[] m1 = new int[degree / 2];
    int[] m2 = new int[degree / 2];

    for(int i = (degree / 2); i < degree; i++) {
        A_hi[i - degree / 2] = A[I]; // LINE 50
        B_hi[i - degree / 2] = B[i];
        System.out.println(A_hi[i - degree / 2] + " " + A[i] + "   " + B_hi[i - degree / 2] + " " + B[i]);
    }

    for(int i = 0; i < (degree / 2); i++) {
        A_lo[i] = A[i];
        B_lo[i] = B[i];
        m1[i] = A_lo[i] + A_hi[i];
        m2[i] = B_lo[i] + B_hi[i];
    }  

    int[] r = new int[(degree * 2) - 1];
    int[] r_m = karatsuba(m1, m2, (degree / 2)); // LINE 63
    int[] r_lo = karatsuba(A_lo, B_lo, (degree / 2));
    int[] r_hi = karatsuba(A_hi, B_hi, (degree / 2));

从那里我将 r_ 数组加载到 r[] 以返回到 main。 这是用于加载 A[] 和 B[]的示例输入。我正在使用数组进行多项式乘法，这些值是系数。

我对这个异常不是很熟悉，但据我了解，ArrayIndexOutOfBoundsException: 0意味着当数组边界中不存在该索引时，我正在尝试使用索引 0 访问数组。

我的困惑是，对于 A[] 和 B[]，我验证了输入得到了正确的数字，所以它被初始化并且具有最高程度的值。对于 A_hi 和 B_hi，我初始化了数组，并一一加载值。我用这一行检查了哪些值被加载到 A_hi[] 和 B_hi[] 中：

System.out.println(A_hi[i - degree / 2] + " " + A[i] + "   " + B_hi[i - degree / 2] + " " + B[i]);

这导致了这个输出——所以这些值是按照我的意图加载的。

那么我使用未正确初始化的 0 访问哪个数组？或者还有其他我不理解的问题？

这是完整的错误列表

4

1 回答 1

2

您的代码很容易执行越界数组访问。具体来说，考虑这个简化的变体：

int[] A_hi = new int[degree / 2];

for(int i = (degree / 2); i < degree; i++) {
    A_hi[i - degree / 2] = 1;
}

数组A_hi有degree / 2元素，你设置degree - degree / 2元素。但是，如果 的值为degree奇数，则degree - degree / 2大于 1 degree / 2，因此您在最后一次迭代中超出了数组边界。特别是，如果degree == 1then 只有一次迭代，i == 0和A_hi的长度为零。这将产生您观察到的异常。

于 2018-12-15T22:15:17.207 回答