分而治之算法的整数数组的总和 [英] Divide and conquer algorithm for sum of integer array

问题描述

我有一个有点麻烦与分治法，并寻找一些帮助。我试图写一个称为sumArray函数，计算整数数组的总和。

此功能必须通过将一半的阵列和表演上的每个半递归调用来完成。我曾尝试使用类似的概念给那些我写的递归算法之和分而治之算法识别在一个数组的最大元素时使用的，但我奋力把两者结合起来的想法。

下面是code我有sumArray，其中编译写的，但不会返回正确的结果。

  INT sumArray（INT anArray []，int长度）
{
    INT总= 0;
    //基本情况
    如果（大小== 0）
    {
        返回0;
    }
    否则，如果（尺寸== 1）
    {
        返回anArray [0];
    }

    //分而治之
    INT中等=尺寸/ 2;
    INT lsum = anArray [MID] + sumArray（anArray，--mid）;
    INT RSIZE =大小 - 中;
    INT率R sum = anArray [大小 -  MID] + sumArray（anArray +中旬，--rsize）;
    返回lsum +率R sum;
}
 

我已确定问题作为其功能包括lsum在其计算率R sum的值。我知道在使用RSIZE到sumArray我的递归调用（一个变量等于原数组的大小，减去中点）的问题所在。出于某种原因，不过，我似乎无法识别修复。

我觉得傻问，因为我知道答案是盯着我的权利在脸上，但我怎么修理我的功能，使其返回一个准确的结果？

更新：感谢所有有用的答复，我有固定我的code等，它编译和运行得很好。我将离开这里我原来的code的情况下，其他人都在努力分而治之和可能会犯类似的错误。对于一个函数，正确地解决了这个问题，看@Laura M的答案。通过@haris的反应也让我在这里code的招致错误的很好的解释。的

解决方案

  INT sumArray（INT anArray []，int长度）
{
    //基本情况
    如果（大小== 0）
    {
        返回0;
    }
    否则，如果（尺寸== 1）
    {
        返回anArray [0];
    }

    //分而治之
    INT中等=尺寸/ 2;
    INT RSIZE =大小 - 中;
    INT lsum = sumArray（anArray，MID）;
    INT率R sum = sumArray（anArray +中旬，RSIZE）;
    返回lsum +率R sum;
}
 

I'm having a bit of trouble with divide and conquer algorithms and was looking for some help. I am attempting to write a function called sumArray that computes the sum of an array of integers.

This function must be done by dividing the array in half and performing recursive calls on each half. I have tried to use similar concepts to those I employed when writing recursive sum algorithms and a divide and conquer algorithm for identifying the maximum element in an array, but I am struggling to combine the two ideas.

Below is the code I have written for sumArray, which compiles, but does not return the correct result.

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

I have identified the problem as being that the function includes the value of lsum in its calculation of rsum. I know the issue lies within my recursive call to sumArray using rsize ( a variable that is equal to the size of the original array, minus the midpoint). For some reason, however, I cannot seem to identify a fix.

I feel silly asking, as I know the answer is staring me right in the face, but how do I repair my function so that it returns an accurate result?

UPDATE: Thanks to all the helpful responses, I have fixed my code and so that it compiles and runs nicely. I will leave my original code here in case others are struggling with divide and conquer and might be making similar mistakes. For a function that correctly solves the problem, see @Laura M's answer. The response by @haris also gives a good explanation of where my code was incurring errors.

解决方案

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

这篇关于分而治之算法的整数数组的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！