如何找出6个小于33大于0的整数，加起来正好是150

问题：如何找出6个小于33大于0的整数，加起来正好是150

结果：

找出6个小于33大于0的整数，加起来正好是150，可以重复
获取数据组合个数：1515921 耗时：3.986

 

代码： 不重复组合的

	/**
	 * 如何找出6个小于33大于0的整数，加起来正好是150，可以重复，比如[25，25，25，25，25，25]，但是不需要考虑顺序
	 * 也就是说[26，24，25，25，25，25]和[24，26，25，25，25，25]是同一个组合
	 */
	public static void main(String[] args) throws IOException {
		long end, start = System.currentTimeMillis();
		List<int[]> ret = find(150, 6);
		TreeSet<int[]> result = new TreeSet<int[]>(new Comparator<int[]>() {//<---去掉重复的数据
			@Override
			public int compare(int[] o1, int[] o2) {
				int len = o1.length > o2.length ? o2.length : o1.length;
				for (int i = 0; i < len; i++) if (o1[i] != o2[i]) return o1[i] - o2[i];
				return o1.length - o2.length;
			}
		});
		for (int[] tmp : ret) {
			Arrays.sort(tmp);//<--组合按照小-->大排列
			result.add(tmp);
		}
		end = System.currentTimeMillis();
		
		File f = new File("/home/skzrorg/number.txt");
		f.createNewFile();
		BufferedWriter writer = new BufferedWriter(new FileWriter(f));
		writer.write("找出6个小于33大于0的整数，加起来正好是150，可以重复\n");
		writer.write("获取数据组合个数：" + result.size() + " 耗时：" + (end - start)/1000.0 + "s\n");
		StringBuffer buf = new StringBuffer();
		for (int[] tmp : result) {
			buf.setLength(0);
			int s = 0;
			for (int i = 0; i < tmp.length; i++) {
				s += tmp[i];
				buf.append(tmp[i]).append(',');
			}
			buf.deleteCharAt(buf.length() - 1).append('\n');
			if (tmp.length != 6 || s != 150) {
				writer.write("一个错误的数据：\n\t");
			}
			writer.write(buf.toString());
		}
		writer.close();
	}
	/**
	 * 找出size个小于33大于0的整数，他们之和为sum，可以重复
	 * @param sum 和数
	 * @param size 整数个数
	 * @return 结果int[]
	 * @author skzr.org(E-mail:[e-mail])
	 */
	private static List<int[]> find(int sum, int size) {
		List<int[]> ret = new ArrayList<int[]>();
		if (size == 1) {
			for (int i = 1; i <= 33; i++) if (sum == i) ret.add(new int[]{i});
		} else {
			for (int i = 1; i <= 33; i++) {//找到一个数据
				if (i < sum) {
					List<int[]> others = find(sum - i, size - 1);//寻找其他数据 
					if (!others.isEmpty()) {//找到其他数据
						for (int[] other : others) {
							int[] tmp = Arrays.copyOf(other, other.length + 1);
							tmp[other.length] = i;
							ret.add(tmp);
						}
					}
				}
			}
		}
		return ret;
	}

 所有的组合的

	/**
	 * 如何找出6个小于33大于0的整数，加起来正好是150，可以重复，比如[25，25，25，25，25，25]，但是不需要考虑顺序
 *也就是说[26，24，25，25，25，25]和[24，26，25，25，25，25]是同一个组合
	 * @throws IOException 
	 */
	public static void main(String[] args) throws IOException {
		long end, start = System.currentTimeMillis();
		List<int[]> ret = find(150, 6);
//		ret.add(new int[]{1,23,32,30,32,32});//<---取消注释用于测试 检测重复是否正常工作
//		ret.add(new int[]{25,25,25,25,25,25});
		Collections.sort(ret, new Comparator<int[]>() {//<---排序和检测重复
			@Override
			public int compare(int[] o1, int[] o2) {
				int len = o1.length > o2.length ? o2.length : o1.length;
				for (int i = 0; i < len; i++) if (o1[i] != o2[i]) return o1[i] - o2[i];
				int ret = o1.length - o2.length;
				if (ret == 0) {
					StringBuffer buf = new StringBuffer();
					for (int i = 0; i < o1.length; i++) {
						buf.append(o1[i]).append(',');
					}
					System.out.println("存在相同的数据:" + buf);
				}
				return ret;
			}
		});
		end = System.currentTimeMillis();
		
		File f = new File("/home/skzrorg/number.txt");
		f.createNewFile();
		BufferedWriter writer = new BufferedWriter(new FileWriter(f));
		writer.write("找出6个小于33大于0的整数，加起来正好是150，可以重复\n");
		writer.write("获取数据组合个数：" + ret.size() + " 耗时：" + (end - start)/1000.0 + "s\n");
		StringBuffer buf = new StringBuffer();
		for (int[] tmp : ret) {
			buf.setLength(0);
			int s = 0;
			for (int i = 0; i < tmp.length; i++) {
				s += tmp[i];
				buf.append(tmp[i]).append(',');
			}
			buf.deleteCharAt(buf.length() - 1).append('\n');
			if (tmp.length != 6 || s != 150) {
				writer.write("一个错误的数据：\n\t");
			}
			writer.write(buf.toString());
		}
		writer.close();
	}
	/**
	 * 找出size个小于33大于0的整数，他们之和为sum，可以重复
	 * @param sum 和数
	 * @param size 整数个数
	 * @return 结果int[]
	 * @author skzr.org(E-mail:[e-mail])
	 */
	private static List<int[]> find(int sum, int size) {
		List<int[]> ret = new ArrayList<int[]>();
		if (size == 1) {
			for (int i = 1; i < 33; i++) if (sum == i) ret.add(new int[]{i});
		} else {
			for (int i = 1; i < 33; i++) {//找到一个数据
				if (i < sum) {
					List<int[]> others = find(sum - i, size - 1);//寻找其他数据 
					if (!others.isEmpty()) {//找到其他数据
						for (int[] other : others) {
							int[] tmp = Arrays.copyOf(other, other.length + 1);
							tmp[other.length] = i;
							ret.add(tmp);
						}
					}
				}
			}
		}
		return ret;
	}

评论

1 楼 skzr.org 2009-11-26  

忘记说了，生成的txt文件大小有25.8MB，小心编辑器崩溃^ ^