java - 在数组中添加连续整数对的分治算法时遇到问题
问题描述
因此,我试图在一个方法中了解分而治之原则和多次递归调用。一切正常,但我正在编写的方法的输出有问题。
该方法的目的是返回数组中所有连续数字对的总和。我有 95% 在那里,但没有得到我期望的输出,并且多年来一直把我的头撞在桌子上试图找出原因。
数组是:
int[] array = { 11, 6, 87, 32, 15, 5, 9, 21 };
方法是:
public int consecutivePairsSum_DivideAndConquer(int start, int end, int[] array) {
int leftSum;
int rightSum;
int middle = (start + end) / 2;
if (start == middle) {
return array[middle];
} else {
leftSum = array[start] + array[start + 1];
leftSum += consecutivePairsSum_DivideAndConquer(start, middle, array);
}
if (middle == end) {
return array[end];
} else {
rightSum = array[middle] + array[middle+1];
rightSum += consecutivePairsSum_DivideAndConquer(middle+1, end, array);
}
return leftSum + rightSum;
}
这是我的方法调用:
System.out.println(rF.consecutivePairsSum_DivideAndConquer(0, array.length-1, array));
我认为这一定与我拆分数组的方式有关,但没有多少实验能给我正确的输出。
预期输出:340
实际输出:330
欢迎任何建议,这让我发疯!:p
ps任何有用的链接到哪里我可以找到关于递归的可靠在线教程/好书也很棒(如果这在SO的范围内,看看它对编程问题没有直接帮助)
解决方案
下面是算法的概要:
基本情况:如果您的数组的元素少于两个,则结果为0
(因为没有对)。
否则:将数组分成两半,计算左右两半的结果,然后整个数组的结果将是<result of left half> + <result of right half> + <last element of left half> + <first element of right half>
(因为这里唯一缺少的对是分割位置的对)。
在java中,它会是这样的:
int consPairSum(int[] array, int left, int right) {
if(right <= left + 1) return 0;
int mid = (left + right) / 2;
int leftPairSum = consPairSum(array, left, mid);
int rightPairSum = consPairSum(array, mid, right);
return leftPairSum + rightPairSum + array[mid - 1] + array[mid];
}
它应该被称为
consPairSum(array, 0, array.length);
推荐阅读
- python - ImportError:无法导入名称'text_summary'
- c# - Outlook COM 加载项 - 在 Outlook 撰写窗口中显示任务窗格
- php - 类如何被路由器实例化?
- javascript - Javascript数组reduce将数组转换为具有整数键的对象
- android - IllegalStateException:片段 xx 未附加到 Activity
- c++ - OpenGL,渲染纹理上的异常伪影,渲染坐标?
- xcode - 用正则表达式替换不能正确使用制表符和换行符模式
- javascript - 如何在我的服务器中创建一个 discord.js bot dm 所有成员
- sql - 为什么这个获取朋友的查询没有返回任何结果?
- javascript - Jdbc.getCloudSqlConnection 的正确实现