특정 번호에 대한 정확한 작업 집합을 찾는 방법은 무엇입니까?

나는이 문제에 응답하는 프로그램을 구현하기 위해 노력하고 있어요 : (예를 들어
다른 6 개 번호 : 당신은 (268 예) : 특정 번호가 부여하는 경우특정 번호에 대한 정확한 작업 집합을 찾는 방법은 무엇입니까?

를 2,4,5,25 , 75,100)

정답이나 가장 가까운 답변을 제공하는 작업을 어떻게 찾을 수 있습니까? , + : 75 * 4-25-5-2 = 268

규칙 :

당신이 산술 연산을 사용할 수 있습니다

는이 작업을 사용하여 이전 예제에 응답 할 수 있습니다 -, *, /,().
나누기를 사용할 때 미리 알림은 0 (6/3은 괜찮지 만 6/4은 괜찮지 않음)이어야합니다.
동일한 번호를 두 번 이상 사용할 수 없습니다. 또한 숫자 사용을 피할 수 있습니다 (예 : 이전 예에서는 100).

모든 가능성을 쓰고 가장 가까운 것을 택하는 것보다 나은 해결책이 있습니까? 이 대답은 내가 너무 많은 코드 라인을 작성하게 만들 것이기 때문에 고마워!

사실

출처

2014-01-30 dehmey

무차별 대항력 솔루션은 많은 코드 라인이 아니라 아마도 더 빠른 해결책 일 것입니다. – Kevin

최상의 답변을 찾으려면 모든 가능성을 검토해야하며 쓸모없는 계산을 피하기 위해 최대한 많은 'if'문으로 코드를 향상시켜야합니다. –

첫 번째 숫자를 생성하려면 항상 6 개의 숫자가 필요합니까? 또한 호기심에서 벗어나이 문제가 어떤 맥락에서 발생 하는가? –

은 무력 솔루션은 정말 너무 많은 코드가 아닙니다

(편집 : 몇 가지 규칙이 제대로 고려되지 않았기 때문에, 코드를 약간 변경)이

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

하지만 물론 이러한 것들은 commutativity 때문에 중복됩니다.

brute-force 변형에서 확인 된 많은 솔루션을 쉽게 피할 수 있습니다. 첫 번째 단계 중 하나는 교환 가능 요소가 포함 된 노드를 만드는 것을 피할 수 있으며 거기에 스케치 한 Node 클래스의 equals 메서드를 구현할 수 있습니다.이 클래스는 commutativity를 고려하여 Set을 사용합니다. 노드 대신 List을 입력하십시오. 또한 '간단한', '낮은 수준'의 최적화가 가능할 수 있습니다 (예 : 완벽한 일치가있는 경우 조기 반환).

실제 질문과 관련하여 무차별 한 것보다 "더 나은"해결책이 있는지 여부 : 내 직감은 대답이 "아니오"라는 것이지만 해결해야 할 문제가 무엇인지에 달려 있습니다. 요점은 다음과 같습니다. 사용 가능한 숫자 목록과 원하는 결과 값이 있다고 가정합니다. 주어진 입력 값에서 결과 값을 생성 할 수 없다고 가정하십시오. 예 :정말 이 불가능하다고을 증명하기 위해, 당신은 결국 "최고"를 반환 (모든 조합을 열거이 생각

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

당신이있을 때, 여기에 아마있을 것이다 1*2*3*4*5*6). 을 (를) 번으로 건너 뛰면 정확하게 이 아닌지 어떻게 확인해야합니까?

다시 : 이것은 단지 느낌입니다. 어쩌면 더 많은 사람들이 ... 수학적으로 관련되어 ... 나를 잘못 증명할 수 있습니다 ....

출처

2014-01-30 17:40:55 Marco13

OP의 두 번째 규칙은 나머지가없는 부분 만 허용한다고 말합니다. – mdl

예, 미안 해요, 내가 이미 이것을 간과했다는 언급에 EDIT를 추가했습니다. 그에 따라 코드를 조정할 것입니다. – Marco13

코드가 수정되었습니다. 지금 올바른 것이어야합니다 .... – Marco13

특정 번호에 대한 정확한 작업 집합을 찾는 방법은 무엇입니까?

답변

관련 문제