今日得闲,想起过往一朋友问到的一个排列组合问题,在数组中{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()`函数实现了冒泡排序,...
在数组循环中,一般会有一个累加器变量,初始值为0,每次循环时累加数组的一个元素。当遍历完整个数组后,累加器的值就是数组所有元素的和。这种操作在数据分析、信号处理等领域非常常见。 LabVIEW中的数组操作还...
其次,杨辉三角是组合数学中的一个重要概念,它展示了二项式系数的排列。在C语言中,我们可以用二维数组来表示杨辉三角。首先,数组的每一行的开头和结尾都填充1,然后通过一个嵌套循环计算中间的元素,这些元素等于...
2. 使用For Loop或For Each Loop遍历数组,每次迭代将当前元素的值与累加器(初始值为0)相加。 3. 最后,累加器的值将作为输出返回,表示所有元素的和。 五、LV的优势 LV以其图形化编程界面著称,使得程序逻辑清晰...
通过多轮比较,最终将整个数组排列成有序序列。例如,【例5-10】展示了如何使用选择法对6个数字进行升序排序。这个过程包括了多次查找和交换操作,直至所有元素都在正确的位置上。 然后,我们进入了二维数组的领域...
- 循环结构在处理数组或序列时很常见,如遍历数组元素,累加求和。 - 数组存储数字,便于进行多步计算和条件判断。 6. 数学公式与精度控制: - 求解数学公式可能涉及到浮点数的计算,需要注意精度问题,如题目...
在上述的平均分计算例子中,我们使用了数组`s`来保存所有学生的成绩,然后通过循环累加求和,再除以元素个数得到平均分。同时,我们还可以通过循环遍历数组,输出所有学生的成绩,如`for(j=0; j; j++) printf("%d,",...
- 使用循环结构计算每个分数,并累加其值。 - 循环20次,每次迭代更新分子和分母的值。 #### 程序17: 阶乘序列求和 - **目标**: 计算1! + 2! + 3! + ... + 20! 的和。 - **程序分析**: - 此程序将传统的累加操作...
reduce()方法主要用于将数组元素组合成单一的输出值。这个方法在处理数组时非常有用,尤其是在需要进行累加、累乘或其他类型的累积计算时。 ### Reduce方法的概念和用法 Reduce方法的核心概念是累加器...
- **数组元素求和**:通过循环累加数组中的所有元素实现求和操作。 - **统计骰子各面出现次数**:利用数组来统计不同数字出现的频率,适用于需要跟踪多个分类计数的情况。 ### 多维数组 - 多维数组是数组元素也是...
- **求和**:可以通过循环遍历数组并累加每个元素的值来计算数组元素的总和。 - **排序**:可以使用Java内置的`Arrays.sort()`方法对数组进行排序,例如: ```java Arrays.sort(scores); ``` 通过以上介绍,我们...
在C#中,你可以遍历数组,使用`foreach`循环,累加每个元素的值以求和,通过比较找到最大值。平均值是总和除以元素个数。Python中同样可以使用`for`循环进行计算,或者利用内置函数如`sum()`和`max()`。 4. **...
33. 累加和:do-while循环用于累加求和。 34. 奇数平方和:筛选奇数并求平方和。 35. 因子积:遍历1到给定数,检查是否为因子并参与乘积计算。 36. 偶数之积:遍历1到100,计算偶数的乘积。 37. 编写函数:根据需求...
3. 求最大值和最小值的积:需要找到数组的最大值和最小值,理解数组操作。 4. 保留小数位:涉及到浮点数处理和四舍五入规则。 5. 实数x对应的函数值:根据不同的x值应用不同的函数,需理解条件语句。 6. 找最大元素...
- 求和:遍历数组,累加所有元素,如`int sum = 0; for(int i=0; i; i++) sum += numbers[i];`。 - 排序:学习经典的冒泡排序算法,通过比较和交换元素来实现升序或降序排列。 ### 重点与难点 - **重点** - 一维...
- 排序:数组的一个常见任务是排序,即将数组元素按照特定规则(如升序或降序)排列。排序有助于数据管理和后续处理。 - 插入、删除和查找:这些操作涉及到数组元素的动态管理,如在数组中添加新元素、移除元素或...
- 平均值计算:通过对数组元素的累加求和再除以元素个数,可以得到平均值。 - 字符串逆序输出:不改变原字符串,而是遍历字符串并逐个输出字符,从后往前遍历即可。 - 字符串长度比较:通过逐个遍历字符串直到...
2. 遍历数组,累加元素到变量s中。 3. 返回变量s的值。 在给定的练习题中,通过填充空白处实现数组求和。空白处的答案为: 1. a 2. s 3. &sco[i] 或 sco+i 4. sco 或 &sco[0] 三、选择法排序 选择法排序是另一种...
7. 累加求和:使用循环累加,注意边界条件。 8. 非连续累加:理解循环累加,同时需要处理非连续序列。 9. 排序:了解排序算法,如冒泡排序或选择排序。 10. 模运算和条件判断:使用模运算检查余数,结合循环。 11. ...
2. 求奇数和:需要理解循环、条件判断和累加求和。 3. 求偶数和:与求奇数和类似,但需修改条件判断。 4. 打印四位数的每一位:涉及数组、循环和格式化输出。 5. 倒序输出:需要理解取模运算和整数除法。 6. 打印...