Небольшая проблема в программе рекурсивного массива

У меня проблемы с рекурсивной функцией. Я передаю в него массив, содержащий целые числа, а затем функция либо складывает, либо вычитает их все вместе. Я правильно реализовал функцию сложения, но мне трудно получить правильный бит вычитания.

Вот что я заметил: размер в настоящее время установлен на 5. Чтобы проверить это, я изменяю строку if(i == size) в части вычитания функции на if(i == (size - 3)), и кажется, что второй элемент правильно вычитается из первого элемента (4 - 2). Но если я позволю ему снова запуститься, я получу 9 вместо (4-2) - 7 = -5, которые я должен получить. Возможно, это добавление -7?

Кроме того, я очень благодарен за все указатели, но я также признаю, что это может быть не самая эффективная программа для выполнения того, что я пытаюсь сделать. Я начинающий программист, и мне больше всего помогло бы увидеть, где я ошибся в моей текущей программе, а не в том, как я должен был сделать свой алгоритм вместо этого.

#include<iostream>

using namespace std;


int reduceArray(int array[], int size, char op, int i = 0)
{
    if(op == '+')
    {
        if(size == 0)
        return 0;

        if(i == size)
        return 0;

        else
        { 
            return array[i++] + reduceArray(array, size, '-', i + 1);   
        }
    }

    else if(op == '-')
    {
        if(size == 0)
        return 0;

        if(i == (size - 2)) //changing this to "size - n" changes how many numbers are subtracted
        return 0;

        else
        { 
            return array[i++] - reduceArray(array, size, '-', i + 1);   
        }
    }
}

int main()
{
    int array[] = {4, 2, 7, 1, 9};

    //cout << reduceArray(array, 5, '+') << endl; this bit works fine works fine
    cout << reduceArray(array, 5, '-') << endl;
    system("pause");
    return 0;
}

EDIT: На самом деле то же самое происходит и с программой разделения. Для третьего элемента массива (7) он выполняет ОБРАТНУЮ операцию — когда он должен вычитать, он складывает, когда он должен делить, он умножает — не может понять, почему это происходит.


c++ arrays recursion subtraction
person user2302335    schedule 28.04.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Вы изменяете i сразу после вызова функции. После возврата функции i увеличивается на единицу. Когда вы извлекаете значение из array[i], вы извлекаете неправильный элемент, по сути, вы делаете array[i + 1] =. Вы также получаете доступ к элементу за пределами конца массива.

Этот код для операторов выполняет вычисления справа налево, а не слева направо, как вы ожидаете. Вы всегда вызываете reduceArray перед выполнением вычисления, поэтому он проходит весь путь до конца массива, затем начинает откат (возврат) и выполняет вычисления после каждого возврата. Чтобы исправить это, вам нужно выполнить вычисления перед вызовом reduceArray, а затем выполнить еще один расчет возвращаемого результата.

if(i < (size - 3)) // This MUST be -1 in order to go to the end of the array!
{
    // We're operating on the current array entry and the next entry.
    // this is why (size - 1) is necessary to prevent accessing beyond
    // the end of the array.
    int result = array[i] - array[i + 1];
    i += 2;
    return result - reduceArray(array, size, '-', i);
}
return array[i];

Это возвращает -5 в качестве результата, которого вы ожидаете.

person Captain Obvlious    schedule 28.04.2013
comment
Имеет смысл. Я соответствующим образом отредактировал свой код, но на самом деле я все еще получаю те же результаты. Он начинается правильно: сначала я получаю 4, затем он вычитает 2, и я получаю 2, но затем вместо вычитания 7 (следующий элемент в массиве) кажется, что он добавляет его, потому что вместо этого я получаю 9 из -7. - person user2302335; 28.04.2013
comment
Когда reduceArray возвращает отрицательное число, вы вычитаете его из числа в массиве. `1 - -5 = 6', так что выглядит так, будто вы добавляете число. - person Captain Obvlious; 28.04.2013
comment
Как я могу исправить это? abs() возможно? - person user2302335; 28.04.2013
comment
Нет. У меня уже есть решение. Я обновляю свой ответ сейчас. Вычисления выполняются в обратном порядке к исходной рекурсивной функции. Я не учитывал это раньше. - person Captain Obvlious; 28.04.2013
comment
Я вижу, как вы изменили его, но если вы увеличите его на 2, что произойдет, если будет передан массив всего на одно целое больше? Кажется ближе, но код все еще не совсем правильный. Код должен возвращать -15 после просмотра всего массива. - person user2302335; 28.04.2013
comment
Так же, как в комментарии говорится, что (size - 1) не позволяет вам пройти за конец массива. Мы знаем, что мы находимся как минимум в 2 элементах от конца массива, поэтому, когда индекс увеличивается на 2, проблем не возникает. Читайте комментарии и источник вслух. - person Captain Obvlious; 28.04.2013
comment
Возможно, я не совсем понимаю. У меня есть: else if(op == '-') { if(size == 0) return 0; if(i ‹ (size - 1)) { int result = array[i] - array[i + 1]; я += 2; вернуть результат - уменьшить массив (массив, размер, '-', i); } вернуть массив[i]; } Итак, как вы говорите, это (размер - 1). Я так понимаю, это для того, чтобы мы не переполняли массив. Однако это не возвращает -15. - person user2302335; 29.04.2013