查询所有 5 个正整数凑成 100 的搭配

java 代码

/**
 * 查询所有 5 个正整数凑成 100 的搭配。所有数字互不相同。
 *
 * @param args 参数
 */
public static void main(String[] args) {
    long start = System.currentTimeMillis();
    int counter = 0;
    int result = 0;
    for (int i = 1; i < 50; i++) {
        for (int j = i + 1; i + j <= 100; j++) {
            for (int k = j + 1; i + j + k <= 100; k++) {
                for (int l = k + 1; i + j + k + l + l + 1 <= 100; l++) {
                    int m = 100 - i - j - k - l;
                    System.out.println(i + " " + j + " " + k + " " + l + " " + m);
                    counter++;
                }
            }
        }
    }
    long end = System.currentTimeMillis();
    System.out.println("得到" + counter + "个结果; 花费时间:" + (end - start) + "毫秒; 循环次数:" + counter);
}

输出：

1 2 3 4 90
1 2 3 5 89
1 2 3 6 88
1 2 3 7 87
......
17 18 20 21 24
17 18 20 22 23
17 19 20 21 23
18 19 20 21 22
得到25337个结果; 花费时间:656毫秒; 循环次数:25337

评论

1 楼 borland 2007-09-05  

package com.perki;

public class Plus {

	/**
	 * @param args
	 */

	private int count;

	private int sum;

	private int total;

	private int[] arrValue;

	// 0 repeat disable,1: repeat enable
	private int digitalRepeat = 0;

	private static RWFile writer = new RWFile("c:/plus_result.txt",
			RWFile.WRITE);

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int sum = 200;
		int count = 13;
		new Plus(count, sum).calc();
		// writer.flush();
		// writer.close();
	}

	public Plus(int count, int sum) {
		super();
		// TODO Auto-generated constructor stub
		this.count = count;
		this.sum = sum;
		arrValue = new int[count + 1];
	}

	public void calc() {
		long t = System.currentTimeMillis();
		calc(0, sum);
		writer.flush();
		System.out.println("total:" + total + ",cost "
				+ (System.currentTimeMillis() - t) + " ms");
	}

	// public void calc(int start, int leftSum) {
	// int base = 1, max;
	// if (start > 0)
	// base = arrValue[start - 1];
	// max = leftSum / (count - start);
	// if (base > max)
	// return;
	// if (start == count - 1) {
	// arrValue[start] = leftSum;
	// total++;
	// pResult();
	// return;
	// }
	// for (int i = base + (digitalRepeat == 1 ? 0 : 1); i <= max; i++) {
	// arrValue[start] = i;
	// calc(start + 1, leftSum - i);
	// }
	// }
	public void calc(int start, int leftSum) {

		int base = 0, max;
		if (start > 0)
			base = arrValue[start - 1];
		max = leftSum / (count - start);
		if (base >= max + digitalRepeat)
			return;
		if (start == count - 1) {
			//if (leftSum > 150)
			//	return;
			arrValue[start] = leftSum;
			total++;
			pResult();
			return;
		}
		for (int i = base + (digitalRepeat == 1 ? 0 : 1); i <= max; i++) {
			arrValue[start] = i;
			calc(start + 1, leftSum - i);
		}
	}

	public void pResult() {
		String result = "";
		for (int i = 0; i < count; i++) {
			if (i == count - 1)
				result += arrValue[i] + "=";
			else
				result += arrValue[i] + "+";
		}
		result += sum;
		write(result);
	}

	public static void write(String s) {
		//writer.write(s);
		// System.out.println(s);
	}

}