Algoritmo para alcanzar un número en una cantidad fija de pasos usando suma, división y multiplicación solamente

Question

Trabajando en un juego en el trabajo y en un punto del juego el jugador se lanza a un juego de bonificación. La cantidad que necesitan para ganar está predeterminada, sin embargo, nos gustaría encontrar un algoritmo que use suma, multiplicación y división para llegar a esa cantidad en x cantidad de pasos. La cantidad de pasos se conocerá también con anticipación, por lo que el algoritmo solo tendrá que descubrir cómo usar esa cantidad de pasos para alcanzar el número.

Las únicas computaciones que puede usar son de +1 a +15, x2, x4,/2,/4. Puede exceder el número objetivo durante los pasos, pero debe terminar en el número objetivo en el último paso. La cantidad paso es típicamente entre 15 y 30 años y que siempre comienzan en 0.

Por ejemplo: Cantidad: 100, Pasos: 10 == 10, 2, x2, 4, x4, 10,/2, 15, 15, 9

Cantidad: 40, Pasos: 12 == 15, 1, 5, 2, 1,/2, * 4, 6, + 6,/4, +5, * 2

Tengo curiosidad por si algo como esto ya podría existir? Estoy seguro de que podemos llegar a algo, pero no quería volver a inventar la rueda si hay un algoritmo común que pueda manejar el trabajo.

---

Actualización: hizo algunos cambios menores en el código de @ FryGuy para que sea la ruta que tarda en alcanzar el número de destino un tanto aleatoria. Su solución funcionó muy bien tal como está, pero después de verla funcionando y teniendo en cuenta los comentarios de @Argote y @Moron, me di cuenta de que necesitaba tener un nivel de aleatorización para hacerlo atractivo para nuestros jugadores. Agregó +1 más de 10 pasos para llegar a un número objetivo de 10 que funciona muy bien, pero es "aburrido" en términos de cómo lo usaríamos. Muchas gracias a todos los que comentaron y respondieron.

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace CR 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      while (true) 
      { 
       int targetNumber = 20; 
       int steps = 13; 
       int[] route = null; 
       Boolean routeAcceptable = false; 

       // Continue choosing routes until we find one that is acceptable (doesn't average above or target win, but does exceed it at least once) 
       while(!routeAcceptable) 
       { 
        routeAcceptable = CalculateRoute(targetNumber, steps, out route) && route.Average() < targetNumber && route.Max() > targetNumber; 
       } 

       foreach (int i in route.Reverse()) 
       { 
        Console.WriteLine(i); 
       } 
       Console.WriteLine("-----------------------"); 
       Console.ReadLine(); 
      } 
     } 

     static Boolean CalculateRoute(int targetNumber, int numSteps, out int[] route) 
     { 
      int maxValue = targetNumber * 16; 
      bool[,] reachable = new bool[numSteps + 1, maxValue]; 

      // build up the map 
      reachable[0, 0] = true; 
      for (int step = 0; step < numSteps; step++) 
      { 
       for (int n = 0; n < maxValue; n++) 
       { 
        if (reachable[step, n]) 
        { 
         foreach (int nextNum in ReachableNumbersFrom(n)) 
         { 
          if (nextNum < maxValue && nextNum > 0) 
          { 
           reachable[step + 1, nextNum] = true; 
          } 
         } 
        } 
       } 
      } 

      // figure out how we got there 
      int[] routeTaken = new int[numSteps + 1]; 
      int current = targetNumber; 
      for (int step = numSteps; step >= 0; step--) 
      { 
       routeTaken[step] = current; 
       bool good = false; 

       // Randomize the reachable numbers enumeration to make the route 'interesting' 
       foreach (int prev in RandomizedIEnumerbale(ReachableNumbersFromReverse(current))) 
       { 
        if (prev < targetNumber * 8) 
        { 
         if (reachable[step, prev]) 
         { 
          current = prev; 
          good = true; 

          // Avoid hitting the same number twice, again to make the route 'interesting' 
          for (int c = numSteps; c >= 0; c--) 
          { 
           reachable[c, prev] = false; 
          } 
          break; 
         } 
        } 
       } 

       if (!good) 
       { 
        route = routeTaken; 
        return false; 
       } 
      } 

      route = routeTaken; 
      return true; 
     } 

     static IEnumerable<int> ReachableNumbersFrom(int n) 
     { 
      // additions 
      for (int i = 1; i <= 15; i++) 
      { 
       yield return n + i; 
      } 

      // mults/divides 
      yield return n/2; 
      yield return n/4; 
      yield return n * 2; 
      yield return n * 4; 
     } 

     static IEnumerable<int> ReachableNumbersFromReverse(int n) 
     { 
      // additions 
      for (int i = 1; i <= 15; i++) 
      { 
       if (n - i >= 0) 
        yield return n - i; 
      } 

      // mults/divides 
      if (n % 2 == 0) 
       yield return n/2; 
      if (n % 4 == 0) 
       yield return n/4; 
      yield return n * 2; 
      yield return n * 4; 
     } 

     static IEnumerable<int> RandomizedIEnumerbale(IEnumerable<int> enumerbale) 
     { 
      Random random = new Random(System.DateTime.Now.Millisecond); 
      return (
       from r in 
        (
         from num in enumerbale 
         select new { Num = num, Order = random.Next() } 
        ) 
       orderby r.Order 
       select r.Num 
       ); 
     } 
    } 
} 

Answer 1

Yo usaría la programación dinámica. En primer lugar, construir un mapa de qué números son accesibles desde cada paso, a continuación, dar marcha atrás para descubrir cómo usted podría haber llegado allí:

void CalculateRoute(int targetNumber, int numSteps) 
{ 
    int maxValue = targetNumber * 16; 
    bool[,] reachable = new bool[numSteps + 1, maxValue]; 

    // build up the map 
    reachable[0, 0] = true; 
    for (int step = 0; step < numSteps; step++) 
    { 
     for (int n = 0; n < maxValue; n++) 
     { 
      if (reachable[step, n]) 
      { 
       foreach (int nextNum in ReachableNumbersFrom(n)) 
       { 
        if (nextNum < maxValue && nextNum >= 0) 
         reachable[step + 1, nextNum] = true; 
       } 
      } 
     } 
    } 

    // figure out how we got there 
    int current = targetNumber; 
    for (int step = numSteps; step >= 0; step--) 
    { 
     Console.WriteLine(current); 

     bool good = false; 
     foreach (int prev in ReachableNumbersFromReverse(current)) 
     { 
      if (reachable[step, prev]) 
      { 
       current = prev; 
       good = true; 
       break; 
      } 
     } 

     if (!good) 
     { 
      Console.WriteLine("Unable to proceed"); 
      break; 
     } 
    } 
} 

IEnumerable<int> ReachableNumbersFrom(int n) 
{ 
    // additions 
    for (int i = 1; i <= 15; i++) 
     yield return n + i; 

    // mults/divides 
    yield return n/2; 
    yield return n/4; 
    yield return n * 2; 
    yield return n * 4; 
} 

IEnumerable<int> ReachableNumbersFromReverse(int n) 
{ 
    // additions 
    for (int i = 1; i <= 15; i++) 
     yield return n - i; 

    // mults/divides 
    if (n % 2 == 0) 
     yield return n/2; 
    if (n % 4 == 0) 
     yield return n/4; 
    yield return n * 2; 
    yield return n * 4; 
} 

Answer 2

Puede forzarlo brutalmente con un árbol de búsqueda que tiene N niveles de profundidad donde N es el número de pasos. Esto sería O (m^n) donde m es el número de operaciones permitidas.

es probable que haya un mejor algoritmo pero esto debería funcionar para valores pequeños de N.

Por ejemplo, utilizar {amplitud, la profundidad} -En primer lugar Buscar o A *.

Answer 3

trabajar hacia atrás desde su solución deseada
con su división y la multiplicación único ser por 2 de y 4 de, hace que sea fácil saber cuando se puede o no puede realizar estas operaciones
y luego, durante el último 4- 5 pasos puede simplemente hacer que vuelva arbitrariamente a 0

Para agregar a esto; puede usar operaciones aleatorias en la fase inicial, verificando que no está realizando operaciones ilegales, y también debe incluir un control de rango. No desea terminar con un número como 400 y luego tener que dividirlo por 4 un montón de veces como sus últimas operaciones, para volver a 0.