Ekleme, bölme ve çarpma kullanarak sabit bir miktar adımda bir sayıya ulaşmak için algoritma

Question

Oyunda işte bir noktada çalışmak ve oyunda bir noktada oyuncu bonus oyuna fırlatılır. Kazanmaya ihtiyaç duydukları miktar önceden belirlenir, ancak x miktarında bu miktara ulaşmak için toplama, çarpma ve bölme kullanan bir algoritma geliştirmek isteriz. Adımların miktarı da zamanın önünde bilinecektir, bu yüzden algoritmanın sadece sayıya ulaşmak için bu adımı nasıl kullanacağını anlaması gerekir.

Kullanabileceğiniz tek hesaplamalar +1 ile +15, x2, x4,/2,/4 arasındadır. Adımlar sırasında hedef sayısını aşabilir, ancak son adımda hedef numaraya ulaşabilmeniz gerekir. adım miktarı, tipik olarak 15 ila 30 olduğu ve her zaman örneğin 0

başlar: miktarı: 100, adımlar: 10 == + 10, + 2, x2, + 4, X4, + 10,/2, +15, +15, +9

Miktar: 40, Adımlar: 12 == +15, +1, +5, +2, +1,/2, * 4, +6, + 6,/4, +5, * 2

Bunun gibi bir şey var mıdır merak ediyorum. Eminim bir şey bulabiliriz, ama işi halledebilecek ortak bir algoritma varsa, tekerleği yeniden icat etmek istemedim.

---

Güncelleme: Bir o biraz rastgele hedef sayısına ulaşmak için gereken rotayı yapmak @ FryGuy koduyla birkaç küçük değişiklikler yapılmış. Çözümü olduğu gibi çalıştı, ancak çalışmayı gördükten ve @Argote ve @Moron tarafından yapılan yorumları dikkate aldıktan sonra, oyuncularımıza cazip gelmesini sağlamak için bir randomizasyon seviyesinin gerekli olduğunu anladım. 10 eserden büyük bir hedefe ulaşmak için 10 adımdan fazla +1 eklendi, ancak onu nasıl kullanacağımız açısından 'sıkıcı' oluyor. Yorum yapan ve cevaplayan herkese çok teşekkürler.

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

Dinamik programlama kullanıyorum. İlk olarak, sayılar her adımda erişilebilir olduğu haritasını oluşturmak, o zaman orada alabilirdik öğrenmek için backtrack:

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

N düzeyi, N'nin adım sayısı olan derinlikli bir arama ağacıyla zorlayabilirsiniz. Bu, O (m^n) olur; burada m, izin verilen işlemlerin sayısıdır. *

muhtemelen daha iyi bir algoritma vardır ama bu, Örneğin N.

küçük değerleri için çalışmak {Genişlik, Derinlik} kullanmak -Birinci ara veya A olmalıdır. İstediğiniz çözümü geriye

Answer 3

eser Ligindeki ve sadece 2 en ve 4 en tarafından olmanın çarpma ile
bunda ne daha sonra bu işlemleri
gerçekleştirmek ve yapamayacağı zaman kolay son 4- için, bilmek yapar 5 adımda keyfi olarak 0

'a dönebilirsiniz. İlk aşamada rastgele işlemleri kullanabilir, yasa dışı işlemler yapmadığınızı kontrol edebilir ve ayrıca aralık için bir kontrol eklemeniz gerekir. 400 gibi bir sayı ile sonuçlanmak istemezsiniz ve sonra son işlemleriniz olarak 4'e kadar bir sayı bölmek zorunda kalmazsınız.