事實上,蠻力解決方案實在是沒有那麼多的代碼
(編輯:改變了代碼略有下降,因爲一些規則沒有得到適當的考慮)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class NumberPuzzle
{
public static void main(String[] args)
{
List<Integer> numbers = Arrays.asList(2,4,5,25,75,100);
Integer result = 268;
solve(numbers, result);
}
private static void solve(List<Integer> numbers, Integer result)
{
List<Node> nodes = new ArrayList<Node>();
for (int i=0; i<numbers.size(); i++)
{
Integer number = numbers.get(i);
nodes.add(new Node(number));
}
System.out.println(nodes);
List<Node> all = create(nodes);
System.out.println("Found "+all.size()+" combinations");
List<Node> best = new ArrayList<Node>();
Integer minDifference = Integer.MAX_VALUE;
for (Node n : all)
{
//System.out.println(n);
Integer e = n.evaluate();
Integer difference = Math.abs(e - result);
if (difference < minDifference)
{
best.clear();
minDifference = difference;
best.add(n);
}
else if (difference.equals(minDifference))
{
best.add(n);
}
}
for (Node n : best)
{
System.out.println(n+" = "+n.evaluate());
}
}
private static List<Node> create(List<Node> nodes)
{
if (nodes.size() == 1)
{
return nodes;
}
List<Node> result = new ArrayList<Node>(nodes);
for (int i=0; i<nodes.size(); i++)
{
List<Node> copy = new ArrayList<Node>(nodes);
Node node = copy.remove(i);
List<Node> others = create(copy);
for (int j=0; j<others.size(); j++)
{
Node other = others.get(j);
result.add(new Node(node, '+', other));
result.add(new Node(node, '*', other));
result.add(new Node(node, '-', other));
result.add(new Node(other, '-', node));
Integer vNode = node.evaluate();
Integer vOther = other.evaluate();
if (vOther != 0 && vNode % vOther == 0)
{
result.add(new Node(node, '/', other));
}
if (vNode != 0 && vOther % vNode == 0)
{
result.add(new Node(other, '/', node));
}
}
}
return result;
}
static class Node
{
Integer value;
Node left;
Character op;
Node right;
Node(Node left, Character op, Node right)
{
this.left = left;
this.op = op;
this.right = right;
}
Node(Integer value)
{
this.value = value;
}
Integer evaluate()
{
if (op != null)
{
Integer lv = left.evaluate();
Integer rv = right.evaluate();
switch (op)
{
case '+': return lv + rv;
case '-': return lv - rv;
case '*': return lv * rv;
case '/': return rv.equals(0) ? Integer.MAX_VALUE : lv/rv;
}
}
return value;
}
@Override
public String toString()
{
if (op == null)
{
return String.valueOf(value);
}
return "("+left.toString()+op+right.toString()+")";
}
}
}
它發現頗有些解決方案....
(編輯:根據變化的代碼更新)
(2*(4+(5+(25+100)))) = 268
(2*(4+(5+(100+25)))) = 268
(2*(4+(25+(5+100)))) = 268
(2*(4+(25+(100+5)))) = 268
(2*(4+(100+(5+25)))) = 268
(2*(4+(100+(25+5)))) = 268
((5*(4-(25-75)))-2) = 268
((5*(4+(75-25)))-2) = 268
(2*(5+(4+(25+100)))) = 268
((5*(4+(25-(75-100))))-2) = 268
((5*(4-((75-100)-25)))-2) = 268
((5*(4+(25+(100-75))))-2) = 268
((5*(4+(25+(100-75))))-2) = 268
((5*(4+(25-(75-100))))-2) = 268
((5*(4-((75-100)-25)))-2) = 268
((5*(4+(75-25)))-2) = 268
((5*(4-(25-75)))-2) = 268
((5*(4-(75-(25+100))))-2) = 268
((5*(4+((25+100)-75)))-2) = 268
((5*(4-(75-(100+25))))-2) = 268
((5*(4+((100+25)-75)))-2) = 268
(2*(5+(4+(100+25)))) = 268
((5*(4+(100+(25-75))))-2) = 268
((5*(4+(100-(75-25))))-2) = 268
((5*(4-((75-25)-100)))-2) = 268
((5*(4+(100-(75-25))))-2) = 268
((5*(4-((75-25)-100)))-2) = 268
((5*(4+(100+(25-75))))-2) = 268
((5*((4+75)-25))-2) = 268
((((4*75)-25)-5)-2) = 268
(2*(5+(25+(4+100)))) = 268
((5*(25+(4-(75-100))))-2) = 268
((5*(25-((75-100)-4)))-2) = 268
((5*(25+(4+(100-75))))-2) = 268
((5*(25+(4+(100-75))))-2) = 268
((5*(25+(4-(75-100))))-2) = 268
((5*(25-((75-100)-4)))-2) = 268
((5*((75+4)-25))-2) = 268
((((75*4)-25)-5)-2) = 268
((5*(25-(75-(4+100))))-2) = 268
((5*(25+((4+100)-75)))-2) = 268
((5*(25-(75-(100+4))))-2) = 268
((5*(25+((100+4)-75)))-2) = 268
(2*(5+(25+(100+4)))) = 268
((5*(25+(100+(4-75))))-2) = 268
((5*(25+(100-(75-4))))-2) = 268
((5*(25-((75-4)-100)))-2) = 268
((5*(25+(100-(75-4))))-2) = 268
((5*(25-((75-4)-100)))-2) = 268
((5*(25+(100+(4-75))))-2) = 268
((5*(75+(4-25)))-2) = 268
((5*(75-(25-4)))-2) = 268
((5*((4+(25+100))-75))-2) = 268
((5*((4+(100+25))-75))-2) = 268
((5*(75-(25-4)))-2) = 268
((5*(75+(4-25)))-2) = 268
((5*((25+(4+100))-75))-2) = 268
((5*((25+(100+4))-75))-2) = 268
((5*((100+(4+25))-75))-2) = 268
(((75+(100+(4*25)))-5)-2) = 268
((5*((100+(25+4))-75))-2) = 268
(((75+(100+(25*4)))-5)-2) = 268
(2*(5+(100+(4+25)))) = 268
((5*(100+(4+(25-75))))-2) = 268
((5*(100+(4-(75-25))))-2) = 268
((5*(100-((75-25)-4)))-2) = 268
((5*(100+(4-(75-25))))-2) = 268
((5*(100-((75-25)-4)))-2) = 268
((5*(100+(4+(25-75))))-2) = 268
(2*(5+(100+(25+4)))) = 268
((5*(100+(25+(4-75))))-2) = 268
((5*(100+(25-(75-4))))-2) = 268
((5*(100-((75-4)-25)))-2) = 268
((5*(100+(25-(75-4))))-2) = 268
((5*(100-((75-4)-25)))-2) = 268
((5*(100+(25+(4-75))))-2) = 268
((5*(100-(75-(4+25))))-2) = 268
((5*(100+((4+25)-75)))-2) = 268
(((100+(75+(4*25)))-5)-2) = 268
((5*(100-(75-(25+4))))-2) = 268
((5*(100+((25+4)-75)))-2) = 268
(((100+(75+(25*4)))-5)-2) = 268
(2*(25+(4+(5+100)))) = 268
(2*(25+(4+(100+5)))) = 268
((((4*75)-5)-25)-2) = 268
(2*(25+(5+(4+100)))) = 268
((((75*4)-5)-25)-2) = 268
(2*(25+(5+(100+4)))) = 268
(2*(25+(100+(4+5)))) = 268
(2*(25+(100+(5+4)))) = 268
((((5*(4+75))-100)-25)-2) = 268
((((5*(75+4))-100)-25)-2) = 268
((75-(5-(100+(4*25))))-2) = 268
((75+((100+(4*25))-5))-2) = 268
((75-(5-(100+(25*4))))-2) = 268
((75+((100+(25*4))-5))-2) = 268
((75+(100-(5-(4*25))))-2) = 268
((75-((5-(4*25))-100))-2) = 268
((75+(100+((4*25)-5)))-2) = 268
((75+(100-(5-(25*4))))-2) = 268
((75-((5-(25*4))-100))-2) = 268
((75+(100+((25*4)-5)))-2) = 268
(2*(100+(4+(5+25)))) = 268
(2*(100+(4+(25+5)))) = 268
(2*(100+(5+(4+25)))) = 268
(2*(100+(5+(25+4)))) = 268
((100-(5-(75+(4*25))))-2) = 268
((100+((75+(4*25))-5))-2) = 268
((100-(5-(75+(25*4))))-2) = 268
((100+((75+(25*4))-5))-2) = 268
(2*(100+(25+(4+5)))) = 268
(2*(100+(25+(5+4)))) = 268
((((5*(4+75))-25)-100)-2) = 268
((((5*(75+4))-25)-100)-2) = 268
((100+(75-(5-(4*25))))-2) = 268
((100-((5-(4*25))-75))-2) = 268
((100+(75+((4*25)-5)))-2) = 268
((100+(75-(5-(25*4))))-2) = 268
((100-((5-(25*4))-75))-2) = 268
((100+(75+((25*4)-5)))-2) = 268
(((100*((75-5)-2))/25)-4) = 268
(((100*((75-5)-2))/25)-4) = 268
(((100*((75-2)-5))/25)-4) = 268
(((100*((75-2)-5))/25)-4) = 268
(((100*(75-(2+5)))/25)-4) = 268
(((100*(75-(5+2)))/25)-4) = 268
(4*(75-(2*(100/25)))) = 268
(4*(75-(2*(100/25)))) = 268
(4*(75-((2*100)/25))) = 268
(4*(75-((100*2)/25))) = 268
((((4*75)-25)-2)-5) = 268
((((75*4)-25)-2)-5) = 268
(((75+(100+(4*25)))-2)-5) = 268
(((75+(100+(25*4)))-2)-5) = 268
(((100+(75+(4*25)))-2)-5) = 268
(((100+(75+(25*4)))-2)-5) = 268
((((4*75)-2)-25)-5) = 268
((((75*4)-2)-25)-5) = 268
((75-(2-(100+(4*25))))-5) = 268
((75+((100+(4*25))-2))-5) = 268
((75-(2-(100+(25*4))))-5) = 268
((75+((100+(25*4))-2))-5) = 268
((75+(100-(2-(4*25))))-5) = 268
((75-((2-(4*25))-100))-5) = 268
((75+(100+((4*25)-2)))-5) = 268
((75+(100-(2-(25*4))))-5) = 268
((75-((2-(25*4))-100))-5) = 268
((75+(100+((25*4)-2)))-5) = 268
((100-(2-(75+(4*25))))-5) = 268
((100+((75+(4*25))-2))-5) = 268
((100-(2-(75+(25*4))))-5) = 268
((100+((75+(25*4))-2))-5) = 268
((100+(75-(2-(4*25))))-5) = 268
((100-((2-(4*25))-75))-5) = 268
((100+(75+((4*25)-2)))-5) = 268
((100+(75-(2-(25*4))))-5) = 268
((100-((2-(25*4))-75))-5) = 268
((100+(75+((25*4)-2)))-5) = 268
((((4*75)-5)-2)-25) = 268
((((75*4)-5)-2)-25) = 268
((((5*(4+75))-100)-2)-25) = 268
((((5*(75+4))-100)-2)-25) = 268
((((4*75)-2)-5)-25) = 268
((((75*4)-2)-5)-25) = 268
((75+(2*(4+(5+100))))-25) = 268
((75+(2*(4+(100+5))))-25) = 268
((75+(2*(5+(4+100))))-25) = 268
((75+(2*(5+(100+4))))-25) = 268
((75+(2*(100+(4+5))))-25) = 268
((75+(2*(100+(5+4))))-25) = 268
((((5*(4+75))-2)-100)-25) = 268
((((5*(75+4))-2)-100)-25) = 268
((100*(75-(2*4)))/25) = 268
((100*(75-(4*2)))/25) = 268
(75-(2+(5-(100+(4*25))))) = 268
(75-(2-((100+(4*25))-5))) = 268
(75+(((100+(4*25))-5)-2)) = 268
(75-(2+(5-(100+(25*4))))) = 268
(75-(2-((100+(25*4))-5))) = 268
(75+(((100+(25*4))-5)-2)) = 268
(75-(2-(100-(5-(4*25))))) = 268
(75+((100-(5-(4*25)))-2)) = 268
(75-(2+((5-(4*25))-100))) = 268
(75-(2-(100+((4*25)-5)))) = 268
(75+((100+((4*25)-5))-2)) = 268
(75-(2-(100-(5-(25*4))))) = 268
(75+((100-(5-(25*4)))-2)) = 268
(75-(2+((5-(25*4))-100))) = 268
(75-(2-(100+((25*4)-5)))) = 268
(75+((100+((25*4)-5))-2)) = 268
(75-(5+(2-(100+(4*25))))) = 268
(75-(5-((100+(4*25))-2))) = 268
(75+(((100+(4*25))-2)-5)) = 268
(75-(5+(2-(100+(25*4))))) = 268
(75-(5-((100+(25*4))-2))) = 268
(75+(((100+(25*4))-2)-5)) = 268
(75-(5-(100-(2-(4*25))))) = 268
(75+((100-(2-(4*25)))-5)) = 268
(75-(5+((2-(4*25))-100))) = 268
(75-(5-(100+((4*25)-2)))) = 268
(75+((100+((4*25)-2))-5)) = 268
(75-(5-(100-(2-(25*4))))) = 268
(75+((100-(2-(25*4)))-5)) = 268
(75-(5+((2-(25*4))-100))) = 268
(75-(5-(100+((25*4)-2)))) = 268
(75+((100+((25*4)-2))-5)) = 268
(75-(25-(2*(4+(5+100))))) = 268
(75+((2*(4+(5+100)))-25)) = 268
(75-(25-(2*(4+(100+5))))) = 268
(75+((2*(4+(100+5)))-25)) = 268
(75-(25-(2*(5+(4+100))))) = 268
(75+((2*(5+(4+100)))-25)) = 268
(75-(25-(2*(5+(100+4))))) = 268
(75+((2*(5+(100+4)))-25)) = 268
(75-(25-(2*(100+(4+5))))) = 268
(75+((2*(100+(4+5)))-25)) = 268
(75-(25-(2*(100+(5+4))))) = 268
(75+((2*(100+(5+4)))-25)) = 268
(75+(100-(2+(5-(4*25))))) = 268
(75-((2+(5-(4*25)))-100)) = 268
(75+(100-(2-((4*25)-5)))) = 268
(75-((2-((4*25)-5))-100)) = 268
(75+(100+(((4*25)-5)-2))) = 268
(75+(100-(2+(5-(25*4))))) = 268
(75-((2+(5-(25*4)))-100)) = 268
(75+(100-(2-((25*4)-5)))) = 268
(75-((2-((25*4)-5))-100)) = 268
(75+(100+(((25*4)-5)-2))) = 268
(75+(100-(5+(2-(4*25))))) = 268
(75-((5+(2-(4*25)))-100)) = 268
(75+(100-(5-((4*25)-2)))) = 268
(75-((5-((4*25)-2))-100)) = 268
(75+(100+(((4*25)-2)-5))) = 268
(75+(100-(5+(2-(25*4))))) = 268
(75-((5+(2-(25*4)))-100)) = 268
(75+(100-(5-((25*4)-2)))) = 268
(75-((5-((25*4)-2))-100)) = 268
(75+(100+(((25*4)-2)-5))) = 268
(100+(2*(4+(5+75)))) = 268
(100+(2*(4+(75+5)))) = 268
(100+(2*(4+(75+(25/5))))) = 268
(100+(2*(4+(75+(25/5))))) = 268
(100+(2*(5+(4+75)))) = 268
(100+(2*(5+(75+4)))) = 268
(100-(2+(5-(75+(4*25))))) = 268
(100-(2-((75+(4*25))-5))) = 268
(100+(((75+(4*25))-5)-2)) = 268
(100-(2+(5-(75+(25*4))))) = 268
(100-(2-((75+(25*4))-5))) = 268
(100+(((75+(25*4))-5)-2)) = 268
((((5*(4+75))-25)-2)-100) = 268
((((5*(75+4))-25)-2)-100) = 268
(100+(2*(75+(4+5)))) = 268
(100+(2*(75+(4+(25/5))))) = 268
(100+(2*(75+(4+(25/5))))) = 268
(100+(2*(75+(5+4)))) = 268
(100-(2-(75-(5-(4*25))))) = 268
(100+((75-(5-(4*25)))-2)) = 268
(100-(2+((5-(4*25))-75))) = 268
(100-(2-(75+((4*25)-5)))) = 268
(100+((75+((4*25)-5))-2)) = 268
(100-(2-(75-(5-(25*4))))) = 268
(100+((75-(5-(25*4)))-2)) = 268
(100-(2+((5-(25*4))-75))) = 268
(100-(2-(75+((25*4)-5)))) = 268
(100+((75+((25*4)-5))-2)) = 268
(100+(4*(2+(25+(75/5))))) = 268
(100+(4*(2+(25+(75/5))))) = 268
(100+(4*(25+(2+(75/5))))) = 268
(100+(4*(25+(2+(75/5))))) = 268
(100-(5+(2-(75+(4*25))))) = 268
(100-(5-((75+(4*25))-2))) = 268
(100+(((75+(4*25))-2)-5)) = 268
(100-(5+(2-(75+(25*4))))) = 268
(100-(5-((75+(25*4))-2))) = 268
(100+(((75+(25*4))-2)-5)) = 268
(100-(5-(75-(2-(4*25))))) = 268
(100+((75-(2-(4*25)))-5)) = 268
(100-(5+((2-(4*25))-75))) = 268
(100-(5-(75+((4*25)-2)))) = 268
(100+((75+((4*25)-2))-5)) = 268
(100-(5-(75-(2-(25*4))))) = 268
(100+((75-(2-(25*4)))-5)) = 268
(100-(5+((2-(25*4))-75))) = 268
(100-(5-(75+((25*4)-2)))) = 268
(100+((75+((25*4)-2))-5)) = 268
((((5*(4+75))-2)-25)-100) = 268
((((5*(75+4))-2)-25)-100) = 268
(100+(75-(2+(5-(4*25))))) = 268
(100-((2+(5-(4*25)))-75)) = 268
(100+(75-(2-((4*25)-5)))) = 268
(100-((2-((4*25)-5))-75)) = 268
(100+(75+(((4*25)-5)-2))) = 268
(100+(75-(2+(5-(25*4))))) = 268
(100-((2+(5-(25*4)))-75)) = 268
(100+(75-(2-((25*4)-5)))) = 268
(100-((2-((25*4)-5))-75)) = 268
(100+(75+(((25*4)-5)-2))) = 268
(100+(75-(5+(2-(4*25))))) = 268
(100-((5+(2-(4*25)))-75)) = 268
(100+(75-(5-((4*25)-2)))) = 268
(100-((5-((4*25)-2))-75)) = 268
(100+(75+(((4*25)-2)-5))) = 268
(100+(75-(5+(2-(25*4))))) = 268
(100-((5+(2-(25*4)))-75)) = 268
(100+(75-(5-((25*4)-2)))) = 268
(100-((5-((25*4)-2))-75)) = 268
(100+(75+(((25*4)-2)-5))) = 268
但當然,由於交換性,其中許多是冗餘的。
人們可以很容易地避免在強力變體中檢查的許多解決方案。第一步可能是避免創建包含可交換元素的節點,並且可能實現一個equals
方法,用於我在那裏繪製的快速骯髒的Node
類,該類考慮了交換性,然後使用Set
節點而不是List
。此外,「簡單」,「低級別」優化也是可能的(例如,當找到完美匹配時提早返回)。
關於你的實際問題,是否有比強力更好的解決方案:我的直覺是答案是「否」,但這取決於應該解決哪個問題。關鍵點在於:假設給出了可用數字的列表和期望的結果值。並假設,從給定的輸入值創建結果值是不可能的。例如。當你有
input = { 1,2,3,4,5,6 }
result = 10000000000;
我認爲,要想真正證明,這是不可能的,你有枚舉所有組合(返回到底「最好」的一個,在這裏可能會是1*2*3*4*5*6
)。如果你跳過任何組合,你應該如何確定它不完全是最好的?
但是,這只是一種直覺。也許有人更...數學參與...可以證明我錯了......
蠻力解決方案並不是那麼多的代碼行,可能不是一個更快的解決方案。 – Kevin
如果任務是要找到最佳答案,那麼你必須經歷所有可能性,只需用盡可能多的'if'語句來增強代碼,以避免一些無用的計算。 –
你是否總是得到6個數字來產生第一個數字?而且,僅僅出於好奇,在這個問題出現的背景下呢? –