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

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

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

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

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

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


java karatsuba
person DanBan    schedule 15.12.2018    source источник
comment
Можете ли вы опубликовать более полный код, который показывает ошибку?   -  person Makoto    schedule 16.12.2018
comment
@Makoto Конечно, я сейчас отредактирую. Я не решаюсь публиковать слишком много кода из-за проблем с плагиатом, так как я студент, поэтому дайте мне знать, если вам понадобится что-то еще после моего редактирования!   -  person DanBan    schedule 16.12.2018
comment
Предположим, степень == 1. Тогда ваш массив имеет нулевой размер, и первый оператор в цикле дает сбой.   -  person FredK    schedule 16.12.2018
comment
@FredK Значит, только на самом последнем шаге рекурсии она достигает степени == 1? Должен ли я вместо этого использовать цикл while, чтобы убедиться, что степень ›= 2, или есть лучший способ сделать это?   -  person DanBan    schedule 16.12.2018

Ответы (1)


arrow_upward
2
arrow_downward

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

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 имеет нулевую длину. Это создаст именно то исключение, которое вы наблюдаете.

person John Bollinger    schedule 15.12.2018
comment
Таким образом, проблема нечетной степени не является проблемой, потому что степень всегда будет четной (это часть задания). Что касается другой проблемы, где степень == 1, я не знаю, как обойти эту проблему. Я играю с добавлением оператора if, который возвращает вызов рекурсии, если степень ‹ 2, но, похоже, это не помогает. Есть идеи как упростить? - person DanBan; 16.12.2018
comment
@DanBan, проблема степени 1 - это всего лишь частный случай проблемы нечетной степени, а не отдельная проблема. И хотя самый верхний рекурсивный вызов всегда может указывать четную степень, если только степень не всегда является степенью двойки, вы иногда будете сталкиваться с проблемой нечетной степени для степеней, отличных от 1. - person John Bollinger; 16.12.2018
comment
Извините, это то, что я имел в виду. Ввод всегда будет на 1 меньше степени 2. И так, как я построил свою программу, я добавляю единицу к степени, чтобы учесть переменные степени 0, поэтому это всегда будет степень 2 @John Bollinger - person DanBan; 16.12.2018
comment
Хорошо, тогда вы должны сделать базовым случаем вашей рекурсии тот, в котором массивы имеют длину 1. Уловите это с помощью соответствующего условного оператора и выполните соответствующее поведение. Мне неясно, какое реальное поведение, требуемое для этого случая, будет в вашей конкретной реализации, но это является академическим упражнением, так что.... - person John Bollinger; 16.12.2018
comment
Я ценю всю помощь. Как вы сказали, это упражнение, мне нужно руководство, а не ответ :) Спасибо! - person DanBan; 16.12.2018