本文共 1726 字，大约阅读时间需要 5 分钟。

算法分析:

设n为正整数，试把整数3n分解为9个互不相同的正整数a,b,c,d,e,f,g,h,i,然后把这9个正整数分成(a,b,c)、(d,e,f)与(g,h,i)三个三元组(约定a<b<c.d<e<f,g<h<i,a<d<g),若这三个三元组具有以下两个合积相等特性：

a + b + c = d + e + f = g + h + i = n

a * b * c = d * e * f = g * h * i

那么(a,b,c)、(d,e,f)、(g,h,i)就为一个基于n的合积相等特性。

例如: n = 45

4 + 20 + 21 = 5 + 12 + 28 = 7+ 8 + 30 = 45

4 * 20 * 21 = 5 * 12 * 28 = 7 * 8 * 30 = 1680

因9个不同正整数之和至少为45，由此可知正整数n > 14。

1) 设置枚举循环

由于 a + b + c = n，且a < b < c，因而a、b循环取值如下:

a: 1~(n - 3)/3，因b比a至少大1，c比a至少大2，即a至多为(n - 3)/3。

b: a + 1~(n - a - 1)/2。因c比b至少大1，即b至多为(n - a - 1)/2。

c = n - a - b,以确保a < b < c且a + b + c = n

设置d、e循环与g、h循环基本同上，只是由于d > a，因而d起点为 a + 1；g > d,因而g起点为d + 1。

2) 检验和积相等

在设置的枚举循环中，确保了三个三元组和相等，若abc = def = ghi，则表示积相等,用count统计组数。

3) 省略相同整数的检验

若两个和相等的3元组中，若等号两边有部分数相同，部分数不同，不可能有积相等。

代码实现:

/** * 和积三组 */public static void groupBy(){	Scanner input = new Scanner(System.in);	System.out.println("请输入正整数n:");	int n = input.nextInt();	//定义和积三组的所有数字	int a,b,c,d,e,f,g,h,i = 0;	//统计个数	int count = 0;	//循环求解	for (a = 1; a <= (n - 3)/3; a++) {		for (b = a + 1; a <= (n - a - 1)/2; b++) {			for (d = a + 1; d <= (n - 3)/3; d++) {				for (e = d + 1; e <= (n - d - 1)/2; e++) {					for (g = d + 1; g <= (n - 3)/3; g++) {						for (h = g + 1; h <= (n - d - 1)/2; h++) {							System.out.println(1);							//确保和相等							c = n - a - b;							f = n - d - e;							i = n - g - h;							//乘积							int temp = a * b * c;							//在这里排除积不相等							if (d * e * f == temp && g * h * i == temp) {								count++;								System.out.print("  "+count+": " + a + " "+b+" " + c + "、");								System.out.print(" "+ d + " "+e+" " + f + ";");								System.out.println(" " + g + " "+ h +" " + i + ";"										+ "(" + temp +")");															}						}					}				}			}		}	}	input.close();}

转载地址：http://mdslf.baihongyu.com/