`
oboaix
  • 浏览: 273894 次
社区版块
存档分类
最新评论

数组(排列组合)累加求和限制值

    博客分类:
  • JAVA
阅读更多

  今日得闲,想起过往一朋友问到的一个排列组合问题,在数组中{1,5,8,9}找出任意组合,所有数字之和累加值小于或等于14。  (即:不需要考虑顺序先后),列举所有的情况,并显示最终个数。现在提出一种思路,编码如下,抛砖引玉,探讨以资更好的方法。

 

 

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * 在数组中{1,5,8,9}找出任意组合,所有数字之和累加值小于或等于14。 (即:不需要考虑顺序先后),列举所有的情况,并显示最终个数。
 * 简单思路: 排列组合,快速排序(归并排序)
 * @author Dennis Zhao
 * @createdTime:2012-5-24 JDK 1.6.0_17
 */
public class AccumulateArith {

	private volatile String temp = "";

	private int[] arr = { 1, 5, 8, 9 };

	private volatile static int sum = 0;

	private volatile static List<String> list = new ArrayList<String>(64);//4 * 4 * 4 * 4

	public static void main(String[] args) {
		for (int i = 0; i < 4; i++) {
			new AccumulateArith().generateData(i + 1, new AccumulateArith());
		}
		filterCombination(list);
		System.out.println("符合条件的个数:" + sum);
//		System.out.println(list.size());
	}

	/**
	 * 产生所有可能数据的排列组合 generateData
	 * 
	 * @param int count
	 * @param AccumulateArith
	 *            acc
	 * @return the void
	 */
	private void generateData(int count, AccumulateArith acc) {
		for (int i = 0, len = arr.length; i < len; i++) {
			this.temp = acc.temp + arr[i];
			if (count == 1) {
				// System.out.println(this.temp);
				// sum++;
				// 去掉重复的
				filterDuplicate(this.temp);
			} else if (count > 1) {
				new AccumulateArith().generateData(count - 1, this);
			} else {
				continue;
			}
		}
	}

	/**
	 * 去掉重复字符的 filterDuplicate
	 * 
	 * @param String
	 *            str
	 * @return the void
	 */
	private void filterDuplicate(String str) {
		if (null != str && !"".equals(str.trim())) {
			Set<String> set = new HashSet<String>(0);
			String[] arr = new String[str.length()];
			for (int i = 0, len = str.length(); i < len; i++) {
				arr[i] = (str.charAt(i) + "");
				set.add(arr[i]);
			}
			if (set.size() > 0 && set.size() == str.length()) {
				list.add(str);
				// System.out.println(str);
				// sum++;
			}
		}
	}

	/**
	 * 符合组合规则,无顺序 filterCombination
	 * @param List
	 * <String> sList
	 * @return the void
	 */
	private static void filterCombination(List<String> sList) {
		if (null != sList && sList.size() > 0) {
			Map<String, String> map = new HashMap<String, String>(0);
			for (String str : sList) {
				char[] ch = str.toCharArray();
//				quickSort(ch,0, ch.length -1);//faster sort 
				mergeSort(ch,0, ch.length -1);//merge sort
				map.put(String.valueOf(ch), str);
			}
			Iterator<String> it = map.keySet().iterator();
			for (; it.hasNext();) {
				String str = it.next();
				int accSum = 0;
				for (int i = 0; i < str.length(); i++) {
					accSum += Integer.parseInt(str.charAt(i) + "");
				}
				if (accSum <= 14) {
					System.out.println(str);
					sum++;
				}
			}
		}
	}
	
	/**
	 * O(nlogn)
	 * @param a
	 * @param low
	 * @param high
	 */
	private static void quickSort(char[] a, int low, int high) {
		if (low < high) { // 如果不加这个判断递归会无法退出导致堆栈溢出异常
			int middle = getMiddle(a, low, high);
			quickSort(a, 0, middle - 1);
			quickSort(a, middle + 1, high);
		}
	}

	private static int getMiddle(char[] a, int low, int high) {
		char temp = a[low];// 基准元素
		while (low < high) {
			// 找到比基准元素小的元素位置
			while (low < high && a[high] >= temp) {
				high--;
			}
			a[low] = a[high];
			while (low < high && a[low] <= temp) {
				low++;
			}
			a[high] = a[low];
		}
		a[low] = temp;
		return low;
	}
	
	/**
	 * O(NlogN)
	 * @param a
	 * @param left
	 * @param right
	 */
	private static void mergeSort(char[] a, int left, int right) {
	      if(left<right){
	          int middle = (left+right)/2;
	          //对左边进行递归
	          mergeSort(a, left, middle);
	          //对右边进行递归
	          mergeSort(a, middle+1, right);
	          //合并
	          merge(a,left,middle,right);
	      }
	  }

	  private static void merge(char[] a, int left, int middle, int right) {
	      char[] tmpArr = new char[a.length];
	      int mid = middle+1; //右边的起始位置
	      int tmp = left;
	      int third = left;
	      while(left<=middle && mid<=right){
	          //从两个数组中选取较小的数放入中间数组
	          if(a[left]<=a[mid]){
	              tmpArr[third++] = a[left++];
	          }else{
	              tmpArr[third++] = a[mid++];
	          }
	      }
	      //将剩余的部分放入中间数组
	      while(left<=middle){
	          tmpArr[third++] = a[left++];
	      }
	      while(mid<=right){
	          tmpArr[third++] = a[mid++];
	      }
	      //将中间数组复制回原数组
	      while(tmp<=right){
	          a[tmp] = tmpArr[tmp++];
	      }
	  }
}
/**
 * 测试效果如下: 59 58 19 18 15 158 1 5 9 8 符合条件的个数:10
 */

 

2015-09-24

分享到:
评论

相关推荐

    数组求和,素数,排序算法

    - 在函数`sum()`中,通过遍历数组`a`的每个元素并累加到`sum1`,计算数组所有元素的和。 - 在`max()`函数中,通过比较数组中的每个元素与当前最大值`max`,找出数组的最大值。 - `paixu()`函数实现了冒泡排序,...

    labview-sum.rar_SUM_数组_数组labview_数组循环

    在数组循环中,一般会有一个累加器变量,初始值为0,每次循环时累加数组的一个元素。当遍历完整个数组后,累加器的值就是数组所有元素的和。这种操作在数据分析、信号处理等领域非常常见。 LabVIEW中的数组操作还...

    C语言数组二

    其次,杨辉三角是组合数学中的一个重要概念,它展示了二项式系数的排列。在C语言中,我们可以用二维数组来表示杨辉三角。首先,数组的每一行的开头和结尾都填充1,然后通过一个嵌套循环计算中间的元素,这些元素等于...

    4-14_lv一维数组中所有元素之和_

    2. 使用For Loop或For Each Loop遍历数组,每次迭代将当前元素的值与累加器(初始值为0)相加。 3. 最后,累加器的值将作为输出返回,表示所有元素的和。 五、LV的优势 LV以其图形化编程界面著称,使得程序逻辑清晰...

    《VisualBasic Net程序设计》教学课件:第5章 数组2.ppt

    通过多轮比较,最终将整个数组排列成有序序列。例如,【例5-10】展示了如何使用选择法对6个数字进行升序排序。这个过程包括了多次查找和交换操作,直至所有元素都在正确的位置上。 然后,我们进入了二维数组的领域...

    湖南省计算机考试C语言机考试题.pdf

    - 循环结构在处理数组或序列时很常见,如遍历数组元素,累加求和。 - 数组存储数字,便于进行多步计算和条件判断。 6. 数学公式与精度控制: - 求解数学公式可能涉及到浮点数的计算,需要注意精度问题,如题目...

    很好的啊 C语言数组PPT课件.pptx

    在上述的平均分计算例子中,我们使用了数组`s`来保存所有学生的成绩,然后通过循环累加求和,再除以元素个数得到平均分。同时,我们还可以通过循环遍历数组,输出所有学生的成绩,如`for(j=0; j; j++) printf("%d,",...

    蓝点被必做的算法经典题java.c/c++

    - 使用循环结构计算每个分数,并累加其值。 - 循环20次,每次迭代更新分子和分母的值。 #### 程序17: 阶乘序列求和 - **目标**: 计算1! + 2! + 3! + ... + 20! 的和。 - **程序分析**: - 此程序将传统的累加操作...

    js数组方法reduce经典用法代码分享

    reduce()方法主要用于将数组元素组合成单一的输出值。这个方法在处理数组时非常有用,尤其是在需要进行累加、累乘或其他类型的累积计算时。 ### Reduce方法的概念和用法 Reduce方法的核心概念是累加器...

    C大学教程数组与C标准库类模板实用PPT学习教案.pptx

    - **数组元素求和**:通过循环累加数组中的所有元素实现求和操作。 - **统计骰子各面出现次数**:利用数组来统计不同数字出现的频率,适用于需要跟踪多个分类计数的情况。 ### 多维数组 - 多维数组是数组元素也是...

    04java数组.txt

    - **求和**:可以通过循环遍历数组并累加每个元素的值来计算数组元素的总和。 - **排序**:可以使用Java内置的`Arrays.sort()`方法对数组进行排序,例如: ```java Arrays.sort(scores); ``` 通过以上介绍,我们...

    数组排序和计算练习.zip_trickyua_数组排序和计算练习

    在C#中,你可以遍历数组,使用`foreach`循环,累加每个元素的值以求和,通过比较找到最大值。平均值是总和除以元素个数。Python中同样可以使用`for`循环进行计算,或者利用内置函数如`sum()`和`max()`。 4. **...

    c语言 - 副本.pdf

    33. 累加和:do-while循环用于累加求和。 34. 奇数平方和:筛选奇数并求平方和。 35. 因子积:遍历1到给定数,检查是否为因子并参与乘积计算。 36. 偶数之积:遍历1到100,计算偶数的乘积。 37. 编写函数:根据需求...

    2019年C语言期末考试题及答案.pdf

    3. 求最大值和最小值的积:需要找到数组的最大值和最小值,理解数组操作。 4. 保留小数位:涉及到浮点数处理和四舍五入规则。 5. 实数x对应的函数值:根据不同的x值应用不同的函数,需理解条件语句。 6. 找最大元素...

    C语言编程技术实践2020版 实验数组教学单元设计.doc

    - 求和:遍历数组,累加所有元素,如`int sum = 0; for(int i=0; i; i++) sum += numbers[i];`。 - 排序:学习经典的冒泡排序算法,通过比较和交换元素来实现升序或降序排列。 ### 重点与难点 - **重点** - 一维...

    培训数组应用技巧与方法PPT教案学习.pptx

    - 排序:数组的一个常见任务是排序,即将数组元素按照特定规则(如升序或降序)排列。排序有助于数据管理和后续处理。 - 插入、删除和查找:这些操作涉及到数组元素的动态管理,如在数组中添加新元素、移除元素或...

    全国计算机等级考试二级C语言上机考试题库及答案.pdf

    - 平均值计算:通过对数组元素的累加求和再除以元素个数,可以得到平均值。 - 字符串逆序输出:不改变原字符串,而是遍历字符串并逐个输出字符,从后往前遍历即可。 - 字符串长度比较:通过逐个遍历字符串直到...

    C语言程序设计练习题-程序填空.doc

    2. 遍历数组,累加元素到变量s中。 3. 返回变量s的值。 在给定的练习题中,通过填充空白处实现数组求和。空白处的答案为: 1. a 2. s 3. &sco[i] 或 sco+i 4. sco 或 &sco[0] 三、选择法排序 选择法排序是另一种...

    c++编程练习题1(适合广大新手学习)

    7. 累加求和:使用循环累加,注意边界条件。 8. 非连续累加:理解循环累加,同时需要处理非连续序列。 9. 排序:了解排序算法,如冒泡排序或选择排序。 10. 模运算和条件判断:使用模运算检查余数,结合循环。 11. ...

    C语言编程题老师提供

    2. 求奇数和:需要理解循环、条件判断和累加求和。 3. 求偶数和:与求奇数和类似,但需修改条件判断。 4. 打印四位数的每一位:涉及数组、循环和格式化输出。 5. 倒序输出:需要理解取模运算和整数除法。 6. 打印...

Global site tag (gtag.js) - Google Analytics