首页 > 代码库 > 输出和相等的两堆数据
输出和相等的两堆数据
import java.util.*; /** * 给定一个数据集合,把这些数据分成和相等的两堆,输出所有可能的结果。 */ public class FindTwoSetsWithSameSum { // 当前Stack中所有数据的和 private int sumInStack = 0; private Stack<Integer> stack = new Stack<Integer>(); //数据降序排列(java内置升序) private static void sortByDes(int[] data) { Arrays.sort(data); int length = data.length; for (int i = 0; i < length / 2; i++) { int temp = data[i]; data[i] = data[length - i - 1]; data[length - i - 1] = temp; } } private List<String> uniqueResult = new ArrayList<String>(); int count = 0; public void populate(int[] data) { //计算数据集的和,如果不是偶数,那么直接输出“结果不存在”。 int sum = sum(data); if (sum % 2 != 0) { System.out.println("结果不存在!"); return; } /** * 如果数据集的和为偶数,计算出平均数,为了减少递归的次数, * 将数据从大到小排列。 */ int average = sum / 2; sortByDes(data); System.out.println("源数据分成和相等的两堆数据,有如下几种情况:");; populateTargetSets(average, data, 0, data.length); } private void populateTargetSets(int sum, int[] sourceData, int begin, int end) { // 判断Stack中的数据和是否等于目标值,如果是则输出当前Stack中的数据 if (sumInStack == sum) { if (!isDuplicatedResult(stack, sourceData)) { print(stack, sourceData); } } for (int currentIndex = begin; currentIndex < end; currentIndex++) { /* * 如果当前Stack中的和加上当前index的数据小于等于目标值, 那么将当前的index的数据添加到Stack中去, * 同时,将当前Stack中所有数据的和加上新添加到Stack中的数值 */ if (sumInStack + sourceData[currentIndex] <= sum) { stack.push(sourceData[currentIndex]); sumInStack += sourceData[currentIndex]; // 当前index加上1,递归调用本身 populateTargetSets(sum, sourceData, currentIndex + 1, end); sumInStack -= (Integer) stack.pop(); } } } private boolean isDuplicatedResult(Stack<Integer> stack, int[] sourceData) { return uniqueResult.contains(stack.toString()); } private void print(Stack<Integer> stack, int[] sourceData) { System.out.print("第"+(++count)+"种结果==> "); System.out.print(""+stack.toString()); printRemainingData(stack, sourceData); } private void printRemainingData(Stack<Integer> stack, int[] sourceData) { List<Integer> list = new ArrayList<Integer>(); for (int element : sourceData) { list.add(element); } for (int element : stack) { list.remove(new Integer(element)); } System.out.println(" "+list.toString()); uniqueResult.add(stack.toString()); uniqueResult.add(list.toString()); } //数据求和。 private int sum(int[] data) { int sum = 0; for (int element : data) { sum += element; } return sum; } public static void main(String[] args) { int[] sourceData = { 1, 3, 4, 5, 6, 2, 7, 8}; FindTwoSetsWithSameSum finder = new FindTwoSetsWithSameSum(); finder.populate(sourceData); } }
运行结果:
本文出自 “闲庭信步、” 博客,请务必保留此出处http://macxiao.blog.51cto.com/9606147/1588966
输出和相等的两堆数据
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。