6个大于等于1 小于等于33的不同数字为一组，这一组的数字之和必须为120
用java代码实现输出这样的数字组合
package test;
public class Test {
public static void main(String[] args) {
//构造数组
int[] numbers = new int[33];
for (int i = 0; i < 33; i++) {
numbers[i] = i + 1;
}
//记录匹配的组合总数
int count = 0;
//6层循环，每层取一个数
for (int n1 : numbers) {
for (int n2 : numbers) {
for (int n3 : numbers) {
for (int n4 : numbers) {
for (int n5 : numbers) {
for (int n6 : numbers) {
//判断6数之和是否为120
if ((n1 + n2 + n3 + n4 + n5 + n6) == 120) {
//判断这6个数是否是升序排列
if ((n2 > n1) && (n3 > n2) && (n4 > n3)
&& (n5 > n4) && (n6 > n5)) {
//输出
System.out.println(n1 + ", " + n2
+ ", " + n3 + ", " + n4 + ", "
+ n5 + ", " + n6);
count++;
}
}
}
}
}
}
}
}
//输出匹配的排列总数
System.out.println("\n" + count);
}
}
这是用上面所说的“最土”的六层循环的实现版本，逻辑不太复杂，不知有没有Bug，最后一共输出14565条记录。如下：
...
16, 18, 20, 21, 22, 23
17, 18, 19, 20, 21, 25
17, 18, 19, 20, 22, 24
17, 18, 19, 21, 22, 23
14565
不过，即使这种方法，也还是有很多可以改进的地方，可明显提高效率。比如，判断语句提前，每层一判断；限制第一层的取值上限，等等。当然，如果哪位能够给出数学上更加合理的指导的话，对于编程会有更大的帮助。
精妙的方法不谈，
就是用最土的方法，六层for循环，也是没什么难度的吧
120/6=20,每个数平均应该是20，因为最大只能33，所以最小必须是7。
问题工作量可以减少为
6个大于等于7 小于等于33的不同数字为一组，这一组的数字之和必须为120。
啊，sorry，我考虑错了。。。
来个更一般的解法吧：
[code="java"]import java.util.*;
public class Simple {
/**
求出size个不同的数,其范围为[from,to],使得其和为sum的所有解
/
public static List> listAll(int from,int to,int size,int sum){
List> res = new LinkedList>();
if(size == 0){
res.add(new LinkedList());
}
else{
int nfrom = Math.max(from,sum-to(size-1));
int nto = Math.min(to,sum-(from+1)*(size-1));
for(int it = nfrom;it <= nto;it ++)
for(List lst :listAll(it+1,to,size-1,sum-it)){
lst.add(it);
res.add(lst);
}
}
return res;
}
public static void main(String... args){
List<List<Integer>> lst = listAll(1,33,6,120);
System.out.println("Number of solutions :"+lst.size());
for(List<Integer> res : lst) System.out.println(res);
}
}[/code]
输出：
[quote]Number of solutions :14565
[33, 32, 31, 21, 2, 1]
[33, 32, 30, 22, 2, 1]
[33, 32, 29, 23, 2, 1]
[33, 31, 30, 23, 2, 1]
[33, 32, 28, 24, 2, 1]
[33, 31, 29, 24, 2, 1]
[32, 31, 30, 24, 2, 1]
[33, 32, 27, 25, 2, 1]
[33, 31, 28, 25, 2, 1]
[33, 30, 29, 25, 2, 1]
[32, 31, 29, 25, 2, 1]
[33, 31, 27, 26, 2, 1]
[33, 30, 28, 26, 2, 1]
[32, 31, 28, 26, 2, 1]
[32, 30, 29, 26, 2, 1]
[33, 29, 28, 27, 2, 1]
[32, 30, 28, 27, 2, 1]
[31, 30, 29, 27, 2, 1]
[33, 32, 31, 20, 3, 1]
[33, 32, 30, 21, 3, 1]
[33, 32, 29, 22, 3, 1]
[33, 31, 30, 22, 3, 1]
[33, 32, 28, 23, 3, 1]
[33, 31, 29, 23, 3, 1]
[32, 31, 30, 23, 3, 1]
[33, 32, 27, 24, 3, 1]
。。。[/quote]
Scala版的[code="java"]/**
&#Simple.scala
求 x1 + x2 + .. x(size) = sum, x(i) ∈ [from,to], x(i) != x(j) (i != j)
的所有解
@author Eastsun
@version 1.0 2008/10/19
*/
object Simple extends Application {
def listAll(from :Int,to :Int,size :Int,sum :Int):List[List[Int]] = {
if(size == 0) return List(Nil)
val sz = size - 1
val st = from max (sum-to*sz)
val en = to min (sum-(from+1)*sz)
for{ it <- List.range(st,en+1)
rs <-listAll(it+1,to,sz,sum-it)
} yield it::rs
}
val ls = listAll(1,33,6,120)
println(ls.size)
}[/code]