Алгоритм «разделяй и властвуй» для суммы целочисленных массивов
У меня возникли небольшие проблемы с алгоритмами «разделяй и властвуй», и я искал помощи. Я пытаюсь написать функцию 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 также дает хорошее объяснение того, где мой код подвергался ошибкам.
Решение
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;
}
Другие решения
В вашем коде:
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);
число 5 добавляется дважды (один раз в lsum а затем в rsum) так как mid == (size - mid),
Кроме того, призыв к 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);
}
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;
}
Как сказал Харис, в своем коде вы добавляете одинаковое число к правой и левой сумме; тем не менее, существует гораздо большая проблема с вашим кодом.
Вы всегда передаете один и тот же массив рекурсивным вызовам lsum и rsum. Сначала я подумал, что это всего лишь часть вашей реализации и что об этом позаботится параметр size. Тем не менее, параметр размера не работает, как вы, возможно, предполагали, что он будет работать.
Все, что делает ваш алгоритм — это уменьшает параметр размера, пока он не достигнет 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
}
#include<iostream>
using namespace std;
int sum(int a[], int l, int r)
{
if(l==r) return a[l];
int mid = (l+r)/2;
int lsum = sum(a,l,mid);
int rsum = sum(a,mid+1,r);
return lsum+rsum;
}
int main() {
int b[] = {9,7,2,6,5,3};
int fsum = sum(b,0,5);
cout<<fsum;
return 0;
}