Алгоритм разделения и покоя для суммы целочисленного массива

Question

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

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

Ниже приведен код, который я написал для sumArray, который компилирует, но не возвращает правильный результат.

int sumArray(int anArray[], int size) 
{ 
    int total = 0; 
    //base case 
    if (size == 0) 
    { 
     return 0; 
    } 
    else if (size == 1) 
    { 
     return anArray[0]; 
    } 

    //divide and conquer 
    int mid = size/2; 
    int lsum = anArray [mid] + sumArray(anArray, --mid); 
    int rsize = size - mid; 
    int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize); 
    return lsum + rsum; 
} 

Я идентифицировал проблему как функцию, которая включает в себя значение lsum при вычислении rsum. Я знаю, что проблема заключается в моем рекурсивном вызове sumArray с использованием rsize (переменная, которая равна размеру исходного массива, минус средняя точка). По какой-то причине, однако, я не могу найти определения.

Я чувствую себя глупо, спрашиваю, поскольку я знаю, что ответ смотрит мне прямо в лицо, но как мне восстановить свою функцию, чтобы она вернула точный результат?

ОБНОВЛЕНИЕ: Благодаря всем полезным ответам, я исправил свой код и так, что он компилируется и работает красиво. Я оставлю свой оригинальный код здесь, если другие борются с делением и победой и могут совершать подобные ошибки. Для функции, которая правильно решает проблему, см. Ответ @Laura M. Ответ @haris также дает хорошее объяснение того, где мой код подвергался ошибкам.

Answer 1

int sumArray(int anArray[], int size) 
{ 
    //base case 
    if (size == 0) 
    { 
     return 0; 
    } 
    else if (size == 1) 
    { 
     return anArray[0]; 
    } 

    //divide and conquer 
    int mid = size/2; 
    int rsize = size - mid; 
    int lsum = sumArray(anArray, mid); 
    int rsum = sumArray(anArray + mid, rsize); 
    return lsum + rsum; 
} 

Answer 2

int sumArray(int anArray[],int start,int end){ 
    if(start==end) 
     return anArray[start]; 
    if(start<end){ 
     int mid=(start+end)/2; 
     int lsum=sumArray(anArray,start,mid-1); 
     int rsum=sumArray(anArray,mid+1,end); 
     return lsum+rsum+anArray[mid]; 

    } 
    return 0; 

} 

Answer 3

В коде

int mid = size/2; 
int lsum = anArray [mid] + sumArray(anArray, --mid); 
int rsize = size - mid; 
int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize); 

позволяет брать пример в шоу, где это делает ошибку ..

Давайте предположим, что массив { 2, 3, 4, 5, 6, 9} так size = 6

теперь, когда йо до mid = size/2, а затем

int lsum = anArray [mid] + sumArray(anArray, --mid); 
int rsize = size - mid; 
int rsum = anArray[size - mid] + sumArray(anArray + mid, --rsize); 

уведомление, так как mid == (size - mid) число 5 добавляется дважды (один раз в lsum, а затем в rsum).

Далее призыв к sumArray() в rsum должны иметь параметры sumArray(anArray + (mid + 1), --rsize), как элемент mid уже был добавлен в lsum

На другой ноте, вы можете пойти на гораздо более простой код для рекурсии, что-то вроде ..

int add(int low,int high,int *a) 
{ 
    int mid; 
    if(high==low) 
     return a[low]; 
    mid=(low+high)/2; 
    return add(low,mid,a)+add(mid+1,high,a); 
} 

Answer 4

Как Харис сказал в своем коде вы добавить тот же номер как правой суммы и оставшейся суммы; однако с вашим кодом возникает гораздо большая проблема.

Вы всегда передаете один и тот же массив своим рекурсивным вызовам для lsum и rsum. Сначала я подумал, что это всего лишь часть вашей реализации, и о ней позаботится параметр размера.Однако параметр размера не работает, поскольку вы, возможно, намеревались его работать. Весь ваш алгоритм уменьшает параметр размера до тех пор, пока он не достигнет 1. Затем запускается базовый случай, и в результате возвращается первый элемент в исходном массиве. Зачем? Вы никогда не разбиваете массив в своем коде, и поэтому один и тот же массив сохраняется во всех рекурсивных вызовах (даже в базовом случае).

Чтобы устранить эту проблему, все sumarray() следует сделать, это разделить массив на левую половину и правую половину на основе среднего вычисления и рекурсивно передать этот новый массив до тех пор, пока размер массива не будет равен 1 (базовый регистр), и вы возвращаете элемент в массиве. Это эффективно разбивает массив на отдельные элементы, и вся функция должна делать в этот момент, это добавить lsum и rsum.

псевдокод:

sumArray(array[]){ 
    if size(array) is 1 
      return array[0] 

    mid = size(array)/2 
    leftArray = splitArrayUpto(mid, array) 
    rightArray = splitArrayAfter(mid+1, array) 

    leftArraySum = sumArray(leftArray) 
    rightArraySum = sumArray(rightArray) 

    return leftArraySum + rightArraySum 
}