Computing número de destino de los números en un conjunto

Question

Estoy trabajando en un problema de tarea que me pregunta esto:

Tiven un conjunto finito de números, y un número objetivo, encontrar si el conjunto se puede utilizar para calcular el número objetivo usando operaciones matemáticas básicas (agregar, sub, mult, div) y usar cada número en el conjunto exactamente una vez (así que necesito agotar el conjunto). Esto tiene que hacerse con recursión.

Así, por ejemplo, si tengo el conjunto

{1, 2, 3, 4} 

y apuntar a 10, entonces podría llegar a ella mediante el uso de

((3 * 4) - 2)/1 = 10. 

Estoy intentando frase del algoritmo en seudo -code, pero hasta ahora no han llegado demasiado lejos. Estoy pensando que los gráficos son el camino a seguir, pero definitivamente agradecería ayuda en esto. Gracias.

Answer 1

Hablando en general, cuando necesita hacer algo recursivamente, ayuda comenzar desde el "fondo" y pensar hacia arriba. Considere: Tiene un conjunto S de n números {a,b,c,...}, y un conjunto de cuatro operaciones {+,-,*,/}. Vamos a llamar a su función recursiva que opera sobre el conjunto F(S)

• Si n es 1, entonces F(S) sólo será ese número.
• Si n es 2, F(S) puede haber ocho cosas:
  • recoger su número de la izquierda de S (2 opciones)
  • a continuación, elegir una operación para aplicar (4 opciones)
  • su número de la derecha será lo que quede en el conjunto
• Ahora, se puede generalizar a partir el caso n = 2:
  • Elija un número x de S ser el operando de la izquierda (n opciones)
  • elegir una operación de aplicar
  • el número de su mano derecha será F(S-x)

Te dejaré llevarlo desde aquí. :)

editar: Mark plantea una crítica válida; el método anterior no obtendrá absolutamente todo.Para solucionar ese problema, es necesario pensar en ello de una manera ligeramente diferente:

• En cada paso, primero escoge una operación (4 opciones), y luego
• particiónS en dos conjuntos, los operandos de la mano izquierda y derecha,
• y de forma recursiva se aplican a ambas particiones F

Encontrar todas las particiones de un conjunto en 2 partes no es trivial en sí, sin embargo.

Answer 2

Bueno, usted no mencionó la eficiencia, así que voy a publicar una solución de fuerza bruta realmente y le permiten optimizar si lo desea. Como puede tener parantheses, es fácil forzarlo usando Reverse Polish Notation:

En primer lugar, si su conjunto tiene n números, debe usar exactamente n - 1 operadores. Por lo que su solución será dada por una secuencia de 2n - 1 símbolos de {{su conjunto dado}, {*, /, +, -}}

st = a stack of length 2n - 1 
n = numbers in your set 
a = your set, to which you add *, /, +, - 
v[i] = 1 if the NUMBER i has been used before, 0 otherwise 

void go(int k) 
{ 
    if (k > 2n - 1) 
    { 
    // eval st as described on Wikipedia. 
    // Careful though, it might not be valid, so you'll have to check that it is 
    // if it evals to your target value great, you can build your target from the given numbers. Otherwise, go on. 

    return; 
    } 

    for (each symbol x in a) 
    if (x isn't a number or x is a number but v[x] isn't 1) 
    { 
     st[k] = x; 
     if (x is a number) 
     v[x] = 1; 

     go(k + 1); 
    } 
} 

Answer 3

Su mejor idea sobre la forma de abordar este problema es la hecho de que su profesor/profesor quiere que use recursividad. Es decir, este no es un problema de matemáticas - es un problema de búsqueda.

No dar demasiado lejos (es tarea después de todo), pero debe generar una llamada a la función recursiva utilizando un operador, un número y una lista que contenga los números restantes. La función recursiva extraerá un número de la lista y, utilizando la operación pasada, la combina con el número transferido (que es el total acumulado). Tome el total acumulado y llámese de nuevo con los elementos restantes de la lista (tendrá que repetir la lista dentro de la llamada, pero la secuencia de llamadas se realiza en profundidad). Haga esto una vez para cada uno de los cuatro operadores a menos que se haya logrado el Éxito en un tramo anterior de la búsqueda.

he actualizado esta opción para utilizar una lista en lugar de una pila

Cuando el resultado de la operación es el número de destino y su lista está vacía, entonces usted ha encontrado con éxito el conjunto de operaciones (los que trazó el camino a la hoja de éxito) - configure la bandera de éxito y desenrolle. Tenga en cuenta que los operadores no están en una lista ni están en la llamada: la función en sí misma siempre itera sobre los cuatro. Su mecanismo para "desenrollar" la secuencia del operador de la hoja exitosa para obtener la secuencia es devolver el operador actual y el número antepuesto al valor devuelto por la llamada recursiva (solo uno de ellos tendrá éxito ya que se detiene en el éxito; eso, obviamente, , es el que se debe usar). Si ninguno tiene éxito, entonces lo que devuelve no es importante de ninguna manera.

actualización Esto es mucho difícil cuando se tiene en cuenta expresiones como la que Daniel registró. Tiene combinatoria en los números y las agrupaciones (números debido a que/y - son sensibles a los pedidos incluso sin agrupar y agrupar porque cambia la precedencia). Entonces, por supuesto, también tienes la combinatoria de las operaciones. Es más difícil gestionar las diferencias entre (4 + 3) * 2 y 4 + (3 * 2) porque la agrupación no se repite como operadores o números (que puede iterar de forma amplia al hacer su profundidad-primero) llamadas recursivas).

Answer 4

Aquí hay un código de Python para comenzar: solo imprime todas las expresiones posibles, sin preocuparse demasiado por la redundancia. Tendría que modificarlo para evaluar expresiones y compararlas con el número objetivo, en lugar de simplemente imprimirlas.

La idea básica es: dado un conjunto S de números, partición de S en dos subconjuntos left y right en todas las formas posibles (en el que no se preocupan por el orden o los elementos en left y right), de tal manera que left y right son ambos no vacíos. Ahora, para cada una de estas particiones, encuentre todas las maneras de combinar los elementos en left (¡recursivamente!), Y de manera similar para right, y combine los dos valores resultantes con todos los operadores posibles. La recursividad toca fondo cuando un conjunto tiene solo un elemento, en cuyo caso solo hay un valor posible.

Incluso si no conoce Python, la función expressions debería ser razonablemente fácil de seguir; la función splittings contiene algunas rarezas de Python, pero lo único que hace es encontrar todas las particiones de la lista l en las piezas izquierda y derecha.

def splittings(l): 
    n = len(l) 
    for i in xrange(2**n): 
     left = [e for b, e in enumerate(l) if i & 2**b] 
     right = [e for b, e in enumerate(l) if not i & 2**b] 
     yield left, right 

def expressions(l): 
    if len(l) == 1: 
     yield l[0] 
    else:  
     for left, right in splittings(l): 
      if not left or not right: 
       continue 
      for el in expressions(left): 
       for er in expressions(right): 
        for operator in '+-*/': 
         yield '(' + el + operator + er + ')' 

for x in expressions('1234'): 
    print x 

Answer 5

Esto no pretende ser la solución más rápida, sino más bien una instructiva.

• Se forma recursiva genera todas las ecuaciones en notación de sufijo
• También proporciona una traducción del posfijo a notación infija
• No se realiza ningún cálculo aritmético real, así que hay que poner en práctica que en su propia
  • tener cuidado con la división por cero

Con 4 operandos, 4 operadores posibles, ¡genera todos los 7680 = 5 * 4! * 4^3 expresiones posibles.

• 5 es catalán (3). El catalán (N) es el número de formas de paranthesize N + 1 operandos.
• 4! debido a que los 4 operandos son permutable
• 4^3 porque los 3 operadores tienen cada uno 4 elección

Esto definitivamente no escala bien, como el número de expresiones para N operandos es [1, 8, 192, 7680 , 430080, 30965760, 2724986880, ...].

En general, si usted tiene n+1 operandos, y debe insertar n operadores elegidos de k posibilidades, entonces no son posibles (2n)!/n! k^n ecuaciones.

¡Buena suerte!

import java.util.*; 

public class Expressions { 
    static String operators = "+-/*"; 

    static String translate(String postfix) { 
     Stack<String> expr = new Stack<String>(); 
     Scanner sc = new Scanner(postfix); 
     while (sc.hasNext()) { 
      String t = sc.next(); 
      if (operators.indexOf(t) == -1) { 
       expr.push(t); 
      } else { 
       expr.push("(" + expr.pop() + t + expr.pop() + ")"); 
      } 
     } 
     return expr.pop(); 
    } 

    static void brute(Integer[] numbers, int stackHeight, String eq) { 
     if (stackHeight >= 2) { 
      for (char op : operators.toCharArray()) { 
       brute(numbers, stackHeight - 1, eq + " " + op); 
      } 
     } 
     boolean allUsedUp = true; 
     for (int i = 0; i < numbers.length; i++) { 
      if (numbers[i] != null) { 
       allUsedUp = false; 
       Integer n = numbers[i]; 
       numbers[i] = null; 
       brute(numbers, stackHeight + 1, eq + " " + n); 
       numbers[i] = n; 
      } 
     } 
     if (allUsedUp && stackHeight == 1) { 
      System.out.println(eq + " === " + translate(eq)); 
     } 
    } 
    static void expression(Integer... numbers) { 
     brute(numbers, 0, ""); 
    } 

    public static void main(String args[]) { 
     expression(1, 2, 3, 4); 
    } 
} 

Answer 6

Antes de pensar en la forma de resolver el problema (como con los gráficos), lo que realmente ayuda a simplemente mirar el problema. Si te encuentras atascado y parece que no puedes encontrar ningún pseudo-código, lo más probable es que haya algo que te frene; Alguna otra pregunta o inquietud que aún no se ha abordado.Un ejemplo de pregunta 'adhesiva' en este caso podría ser, "¿Qué es exactamente recursivo sobre este problema?"

Antes de leer el siguiente párrafo, intente responder esta pregunta primero. Si supiera qué era recursivo sobre el problema, entonces escribir un método recursivo para resolverlo podría no ser muy difícil.

Desea saber si alguna expresión que usa un conjunto de números (cada número usado una sola vez) le da un valor objetivo. Hay cuatro operaciones binarias, cada una con un inverso. Entonces, en otras palabras, quieres saber si el primer número operado con alguna expresión de los otros números te da el objetivo. Bueno, en otras palabras, quieres saber si alguna expresión de los 'otros' números es [...]. De lo contrario, usar la primera operación con el primer número realmente no le da lo que necesita, así que intente con las otras operaciones. Si no funcionan, entonces tal vez no estaba destinado a ser.

Editar: Pensé en esto para una expresión infija de cuatro operadores sin paréntesis, ya que un comentario sobre la pregunta original decía que los paréntesis se añadieron por el bien de un ejemplo (¿para mayor claridad?) Y el uso de paréntesis no explícitamente establecido.

Answer 7

código pusedo:

Works(list, target) 
for n in list 
tmp=list.remove(n) 
return Works(tmp,target+n) or Works(tmp,target-n) or Works(tmp, n-target) or ... 

a continuación, sólo tiene que poner el caso base de pienso regalé a mucho..