如何找到特定数字的确切 *** 作集？

如何找到特定数字的确切 *** 作集？

实际上，蛮力解决方案实际上不是那么多代码

（编辑：略微更改了代码，因为某些规则没有得到适当考虑）

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

s个Node代替的

List

。而且，“简单”，“低级”优化也是可能的（例如，找到完美匹配时尽早返回）。

关于您的实际问题，是否有解决方案比暴力破解“更好”：我的直觉是答案是否定的，但这取决于应该解决哪个问题。关键点在这里：假定您获得了可用数字的列表以及所需的结果值。并假设不可能从给定的输入值创建结果值。例如，当你有

input = { 1,2,3,4,5,6 }result = 10000000000;

我认为，为了真正 证明 这是不可能的，您 必须 列举所有组合（最后返回“最佳”组合，这里可能是

1*2*3*4*5*6

）。如果您跳过
任何一种 组合，应该如何确定它并不是 最佳组合 ？

但是再次：这只是一种直觉。也许有人……在数学上涉及更多……可以证明我错了……。