请教一个问题请教一个问题，4到9之间的数字相加，数字可重复，答案为100的所有组合。求算法
比如4到9之间的数字相加，数字可重复，答案为100的所有组合。求算法--------------------编程问答-------------------- 数学语言表示一下：a * 4 + b * 5 + c * 6 + d * 7 + e * 8 + f * 9 = 100，求解集{a, b, c, d, e, f}，其中a (= [0, 25], b (= [0, 20], c (= [0, 16], d (= [0, 14], e (= [0, 12], f (= [0, 11]
暴力法：建立6个数组，预设a .. f的所有可能取值，然后一个个组合找。其中可以做一些优化，不过那都是细节 --------------------编程问答-------------------- 写6个循环 就可以了 哈哈 楼上的很对 --------------------编程问答-------------------- a * 4 + b * 5 + c * 6 + d * 7 + e * 8 + f * 9 = 100
把这些，写6个循环 就脱了 1楼很是聪明！！ --------------------编程问答-------------------- 不是吧！ 我是说比如４到９， 个数不是估计定的， 假如别人调用的时候输入３到９.那怎么改变循环次数？ --------------------编程问答-------------------- 最简单可以用递归搜索
class AddUp {
private static int start;
private static int end;
private static int target;
public static void main(String[] args) {
start = 4;
end = 9;
target = 100;
solve(0, start, new int[6]);
}
public static void solve(int currentTotal, int currentNumber, int[] answer) {
if (currentNumber > end)
return;
for (int i = 0; i <= target / currentNumber; i++) {
int nextTotal = currentTotal + currentNumber * i;
answer[currentNumber - start] = i;
if (nextTotal == 100) {
// we got one, baby!
output(answer);
return;
}
else if (nextTotal < 100)
solve(nextTotal, currentNumber + 1, answer);
else {
// it's already impossible to find another one, clear the cached array entry
answer[currentNumber - start] = 0;
return;
}
}
return;
}
public static void output(int[] answer) {
StringBuilder sb = new StringBuilder();
int total = 0;
for (int i = 0; i < answer.length; i++) {
if (answer[i] == 0)
continue;
sb.append(i + start);
if (answer[i] > 1)
sb.append(" * ").append(answer[i]);
total += (i + start) * answer[i];
if (total != target)
sb.append(" + ");
}
System.out.println(sb.toString());
}
}
--------------------编程问答--------------------
solve(0, start, new int[6]);
改成
solve(0, start, new int[end - start + 1]); --------------------编程问答--------------------
import java.util.LinkedList;
import java.util.List;
public class Hello {
public static void foo(final int start, final int end, List<Integer> elements, final int result) {
int sum = 0;
for (int i : elements) {
sum += i;
}
if (sum == result) {
System.out.println(elements);
return;
} else if (sum > result) {
return;
}
for (int i = start; i <= end; ++i) {
elements.add(i);
foo(i, end, elements, result); // i作为start是为了避免重复，例如[4, 7, 9]与[9, 7, 4], [7, 4, 9]等是重复的
elements.remove(elements.size() - 1);
}
}
public static void main(String[] args) {
List<Integer> elements = new LinkedList<Integer>();
System.out.println("Sum is 20");
foo(4, 9, elements, 20);
System.out.println("\n\nSum is 30");
foo(4, 9, elements, 30);
// System.out.println("\n\nSum is 100");
// foo(4, 9, elements, 100);
}
}
Sum is 20--------------------编程问答-------------------- 修改了一下细节
[4, 4, 4, 4, 4]
[4, 4, 4, 8]
[4, 4, 5, 7]
[4, 4, 6, 6]
[4, 5, 5, 6]
[4, 7, 9]
[4, 8, 8]
[5, 5, 5, 5]
[5, 6, 9]
[5, 7, 8]
[6, 6, 8]
[6, 7, 7]
Sum is 30
[4, 4, 4, 4, 4, 4, 6]
[4, 4, 4, 4, 4, 5, 5]
[4, 4, 4, 4, 5, 9]
[4, 4, 4, 4, 6, 8]
[4, 4, 4, 4, 7, 7]
[4, 4, 4, 5, 5, 8]
[4, 4, 4, 5, 6, 7]
[4, 4, 4, 6, 6, 6]
[4, 4, 4, 9, 9]
[4, 4, 5, 5, 5, 7]
[4, 4, 5, 5, 6, 6]
[4, 4, 5, 8, 9]
[4, 4, 6, 7, 9]
[4, 4, 6, 8, 8]
[4, 4, 7, 7, 8]
[4, 5, 5, 5, 5, 6]
[4, 5, 5, 7, 9]
[4, 5, 5, 8, 8]
[4, 5, 6, 6, 9]
[4, 5, 6, 7, 8]
[4, 5, 7, 7, 7]
[4, 6, 6, 6, 8]
[4, 6, 6, 7, 7]
[4, 8, 9, 9]
[5, 5, 5, 5, 5, 5]
[5, 5, 5, 6, 9]
[5, 5, 5, 7, 8]
[5, 5, 6, 6, 8]
[5, 5, 6, 7, 7]
[5, 6, 6, 6, 7]
[5, 7, 9, 9]
[5, 8, 8, 9]
[6, 6, 6, 6, 6]
[6, 6, 9, 9]
[6, 7, 8, 9]
[6, 8, 8, 8]
[7, 7, 7, 9]
[7, 7, 8, 8]
package com.tur.demo;--------------------编程问答-------------------- 哎呀我真是。。还是有几个地方写了100。。
import java.util.LinkedList;
import java.util.List;
public class Hello {
public static void foo(final int start, final int end, final int result, List<Integer> elements) {
if (start > end) { return; }
int sum = 0;
for (int i : elements) {
sum += i;
}
if (sum == result) {
System.out.println(elements);
return;
} else if (sum > result) {
return;
}
for (int i = start; i <= end; ++i) {
elements.add(i);
foo(i, end, result, elements); // i作为start是为了避免重复，例如[4, 7, 9]与[9, 7, 4], [7, 4, 9]等是重复的
elements.remove(elements.size() - 1);
}
}
public static void main(String[] args) {
List<Integer> elements = new LinkedList<Integer>();
System.out.println("Sum is 20");
foo(4, 9, 20, elements);
System.out.println("\n\nSum is 30");
foo(4, 9, 30, elements);
// System.out.println("\n\nSum is 100");
// foo(4, 9, 100, elements);
}
}
先更正，再跟楼上的做一下对比
class AddUp {
private static int start;
private static int end;
private static int target;
public static void main(String[] args) {
start = 4;
end = 9;
target = 100;
for (int i = 0; i < 5000; i++)
solve(0, start, new int[end - start + 1]);
long now = System.nanoTime();
for (int i = 0; i < 5000; i++)
solve(0, start, new int[end - start + 1]);
System.out.println(System.nanoTime() - now);
}
public static void solve(int currentTotal, int currentNumber, int[] answer) {
if (currentNumber > end)
return;
for (int i = 0; i <= target / currentNumber; i++) {
int nextTotal = currentTotal + currentNumber * i;
answer[currentNumber - start] = i;
if (nextTotal == target) {
// we got one, baby!
output(answer);
return;
}
else if (nextTotal < target)
solve(nextTotal, currentNumber + 1, answer);
else {
// it's already impossible to find another one, clear the cached array entry
answer[currentNumber - start] = 0;
return;
}
}
return;
}
public static void output(int[] answer) {
StringBuilder sb = new StringBuilder();
int total = 0;
for (int i = 0; i < answer.length; i++) {
if (answer[i] == 0)
continue;
sb.append(i + start);
if (answer[i] > 1)
sb.append(" * ").append(answer[i]);
total += (i + start) * answer[i];
if (total != target)
sb.append(" + ");
}
System.out.println(sb.toString());
}
}
--------------------编程问答--------------------
多谢各位！
--------------------编程问答--------------------
这里纯讨论技术，不针对个人，更没有炫耀。
首先做了一下性能对比（注释掉了System.out.print）：
//warm up
for (int i = 0; i < 5000; i++)
solve(0, start, new int[end - start + 1]);
long now = System.nanoTime();
for (int i = 0; i < 5000; i++)
solve(0, start, new int[end - start + 1]);
System.out.println(System.nanoTime() - now);
这里输出的值在3988456000附近，就是4秒左右
for (int i = 0; i < 5000; i++) {
elements.clear();
foo(4, 9, 100, elements);
}
long now = System.nanoTime();
for (int i = 0; i < 5000; i++) {
elements.clear();
count = 0;
foo(4, 9, 100, elements);
}
System.out.println(System.nanoTime() - now);这里输出18715472000左右，大概是18秒
我能一眼观察到的导致性能差异的两点：
1. foo函数有一个计算sum的操作，而solve函数则没有
2. foo函数有对ArrayList的操作，性能上不如直接操作int[]
然后再做深入调查：
我在solve函数for循环中的else if和else块中加入了计数器，统计得出值为30143；而在foo函数中的计数器则加在了for循环的上面（外部），得出值为63653。如果将计数器放在函数开始时，它们的值均为97106。
这表明solve函数过滤了更多不可能的情况，从而获得了较好的性能。
当然这不是绝对的。。。
[2, 9, 50] solve: 52276，foo: 40831
[4, 9, 50] solve: 2112，foo: 2304
[2, 9, 100] solve: 2026084，foo: 3101490
看上去好像是在解集比较大的时候，solve比较占优。。。先睡觉，明天再研究。。 --------------------编程问答--------------------
这个可读性很好，顶一个！ --------------------编程问答-------------------- package test;
public class Test5 {
public static void main(String[] args) {
for(int a=0;a<=25;a++){
for(int b=0;b<=20;b++){
for(int c=0;c<=16;c++){
for(int d=0;d<=14;d++){
for(int e=0;e<=12;e++){
for(int f=0;f<11;f++){
if(a*4+b*5+c*6+d*7+e*8+f*9==100){
System.out.println(a+"个4 "
+b+"个5 "+
c+"个6 "+d+"个7 "+
e+"个8 "+f+"个9");
}
}
}
}
}
}
}
}
}
--------------------编程问答--------------------
