c – 对整数数组求和的除法和征服算法
发布时间:2020-12-16 10:35:06 所属栏目:百科 来源:网络整理
导读:我在分治算法方面遇到了一些麻烦,并且正在寻求一些帮助.我正在尝试编写一个名为sumArray的函数来计算整数数组的总和. 此函数必须通过将数组分成两半并在每一半上执行递归调用来完成.我尝试使用类似的概念来编写递归求和算法时使用的概念,以及用于识别数组中
我在分治算法方面遇到了一些麻烦,并且正在寻求一些帮助.我正在尝试编写一个名为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; } 我已经将问题确定为函数在计算rsum时包含lsum的值.我知道问题在于我使用rsize对sumArray的递归调用(一个等于原始数组大小的变量,减去中点).但是,出于某种原因,我似乎无法确定修复方法. 我觉得很傻,因为我知道答案是正确地盯着我,但是我如何修复我的功能以便它返回准确的结果呢? 更新:感谢所有有用的响应,我已修复我的代码,以便它编译和运行良好.我会留下我原来的代码,以防其他人在分裂和征服中挣扎,并可能犯同样的错误.有关正确解决问题的函数,请参阅@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; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |