Encontrar el número mínimo de operaciones requeridas para calcular un número usando un rango de números especificado

Question

Permítanme comenzar con un ejemplo - Tengo un rango de números del 1 al 9. Y digamos que el número objetivo que quiero es 29 En este caso, el número mínimo de operaciones requeridas sería (9 * 3) +2 = 2 operaciones. De manera similar para 18, el número mínimo de operaciones es 1 (9 * 2 = 18). Puedo usar cualquiera de los 4 operadores aritméticos - +, -,/y *.

¿Cómo puedo averiguar programáticamente el número mínimo de operaciones requeridas? Gracias de antemano por cualquier ayuda brindada.

aclaración: enteros solamente, no se permiten decimales a mitad del cálculo. es decir, lo siguiente no es válido (a partir de los comentarios a continuación): ((9/2) + 1) * 4 == 22 Debo admitir que no pensé en esto a fondo, pero para mi propósito no lo hace importa si los números decimales aparecen a mitad del cálculo. ((9/2) + 1) * 4 == 22 es válido. Perdón por la confusion.

Answer 1

Para el caso especial donde conjunto Y = [1..9] y n> 0:

• n < = 9: 0 operaciones
• n < = 18: 1 operación (+)
• de lo contrario: Elimine cualquier divisor que se encuentre en Y. Si esto no es suficiente, realice una recursividad en el resto para todos los desplazamientos -9 .. +9. El desplazamiento 0 se puede omitir ya que ya se ha intentado.

Observe cómo la división no es necesaria en este caso. Para otros Y esto no se cumple.

Este algoritmo es exponencial en log (n). El análisis exacto es un trabajo para alguien con más conocimiento sobre álgebra que yo.

Para una mayor velocidad, agregue la poda para eliminar parte de la búsqueda de números más grandes.

Código de ejemplo:

def findop(n, maxlen=9999): 
    # Return a short postfix list of numbers and operations 

    # Simple solution to small numbers 
    if n<=9: return [n] 
    if n<=18: return [9,n-9,'+'] 

    # Find direct multiply 
    x = divlist(n) 
    if len(x) > 1: 
     mults = len(x)-1 
     x[-1:] = findop(x[-1], maxlen-2*mults) 
     x.extend(['*'] * mults) 
     return x 

    shortest = 0 

    for o in range(1,10) + range(-1,-10,-1): 
     x = divlist(n-o) 
     if len(x) == 1: continue 
     mults = len(x)-1 

     # We spent len(divlist) + mults + 2 fields for offset. 
     # The last number is expanded by the recursion, so it doesn't count. 
     recursion_maxlen = maxlen - len(x) - mults - 2 + 1 

     if recursion_maxlen < 1: continue 
     x[-1:] = findop(x[-1], recursion_maxlen) 
     x.extend(['*'] * mults) 
     if o > 0: 
      x.extend([o, '+']) 
     else: 
      x.extend([-o, '-']) 
     if shortest == 0 or len(x) < shortest: 
      shortest = len(x) 
      maxlen = shortest - 1 
      solution = x[:] 

    if shortest == 0: 
     # Fake solution, it will be discarded 
     return '#' * (maxlen+1) 
    return solution 

def divlist(n): 
    l = [] 
    for d in range(9,1,-1): 
     while n%d == 0: 
      l.append(d) 
      n = n/d 
    if n>1: l.append(n) 
    return l 

Answer 2

La idea básica es probar todas las posibilidades con operaciones k, para k a partir de 0. Imagine que crea un árbol de altura k que se bifurca para cada nueva operación posible con operando (4 * 9 ramas por nivel). Debe atravesar y evaluar el hojas del árbol para cada k antes de pasar al siguiente k.

No he probado este pseudo-código:

for every k from 0 to infinity 
    for every n from 1 to 9 
    if compute(n,0,k): 
     return k 


boolean compute(n,j,k): 
    if (j == k): 
    return (n == target) 
    else: 
    for each operator in {+,-,*,/}: 
     for every i from 1 to 9: 
     if compute((n operator i),j+1,k): 
      return true 
    return false 

No toma en cuenta la aritmética operadores de precedencia y apoyos, que requeriría algunas correcciones.

Answer 3

pregunta realmente fresco :)

Tenga en cuenta que usted puede comenzar desde el final! De su ejemplo (9 * 3) +2 = 29 es equivalente a decir (29-2)/3 = 9. De esa manera podemos evitar el doble circuito en la respuesta de cyborg. Esto sugiere el siguiente algoritmo para el conjunto Y y el resultado r:

nextleaves = {r} 
nops = 0 
while(true): 
    nops = nops+1 
    leaves = nextleaves 
    nextleaves = {} 
    for leaf in leaves: 
     for y in Y: 
     if (leaf+y) or (leaf-y) or (leaf*y) or (leaf/y) is in X: 
      return(nops) 
     else: 
      add (leaf+y) and (leaf-y) and (leaf*y) and (leaf/y) to nextleaves 

Ésta es la idea básica, el rendimiento se puede sin duda ser mejorado, por ejemplo, evitando "preclasificación", como r+a-a o r*a*b/a.

Answer 4

Creo que mi idea es similar a la de Sommerlund Peer:

Para grandes números, avanzar rápido, por multiplicación con grandes cifras.

¿Es Y = 29 primer? Si no, divídalo por el divisor máximo de (2 a 9). De lo contrario, podría restar un número para llegar a un número divisible. 27 está muy bien, ya que es divisible por 9, por lo

(29-2)/9=3 => 
3*9+2 = 29 

Así que tal vez - Yo no pienso en esto hasta el final: Buscar en el próximo número divisible por 9 a continuación Y. Si no se llega a una número que es un dígito, repita.

La fórmula muestra los pasos invertidos.

(voy a tratar de algunos números. :))

he intentado con 2551, que es

echo $((((3*9+4)*9+4)*9+4)) 

Pero no he probado cada resultado intermedio si es primo. Pero

echo $((8*8*8*5-9)) 

son 2 operaciones menos. Tal vez pueda investigar esto más tarde.