分治求和算法

Question

我正在寻找一些 D&C 算法并创建了这个算法

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;
}

但每次运行没有基本情况的代码都是 returns 段错误。我想弄清楚为什么这个基本案例如此重要，以至于即使运行 n>1 它仍然返回那个错误，有人会在这里伸出援手吗？

Answer 1

因为函数sumArray递归调用自身，

    int lsum = sumArray(anArray, mid);
    int rsum = sumArray(anArray + mid, rsize);

无论数组大小如何，都需要基本情况。否则Fnction永远无法退出调用自身的循环！请记住，基于 mid 和 rsize 中的一个可能是奇数，甚至是 size == 0 和 size == 1 的基本情况：

    if (size == 0)
    {
        return 0;
    }
    else if (size == 1)
    {
        return anArray[0];
    }

需要

分治求和算法

Divide and conquer sum algorithm

c++

sorting

array-algorithms