ArrayIndexOutOfBoundsException: 0 в реализации Карацубы - PullRequest
Новая
       71

ArrayIndexOutOfBoundsException: 0 в реализации Карацубы

0 голосов
/ 16 декабря 2018

Я реализую алгоритм Карацубы и столкнулся с этим исключением.

Некоторый соответствующий код (я могу опубликовать больше, если необходимо):

Из основного: 

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 [] для возврата к основному. Вот пример ввода , который используется для загрузки 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, который не инициализирован должным образом?Или есть еще одна проблема, которую я не понимаю?

Вот полный список ошибок

1 Ответ

0 голосов
/ 16 декабря 2018

Ваш код склонен к выполнению доступа за пределы массива.В частности, рассмотрим этот упрощенный вариант: 

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 на единицу больше, чем degree / 2, поэтому вы пересекаете границы массива на последней итерации.В частности, если degree == 1, то существует только одна итерация, с i == 0, а A_hi имеет нулевую длину.Это создаст именно то исключение, которое вы наблюдаете.

...