étapes minimum à une logique échoue pour certaines conditions

Question

Le puzzle est d'obtenir le nombre minimum d'étapes qu'il faut pour faire un numéro 1. Les opérations autorisées sont

1. You can subtract 1 from the number 
2. You can divide the number by 2 if it is divisible by 2. 
3. You can divide the number by 3 if it is divisible by 3. 

A la fin, vous devez faire le nombre 1 en effectuant les opérations ci-dessus. J'essaie d'obtenir une solution qui me donne le nombre minimum d'opérations ci-dessus nécessaires pour faire le numéro 1. Mon code (en Java) est le suivant.

public int minStepsBottomUp(int n) { 
     int[] memoArray = new int[n+1]; 
     memoArray[0] = 0; 
     memoArray[1] = 0; 
     for(int i=2;i<=n;++i){ 
      int r = 1 + memoArray[i-1]; 
      if(n % 2 == 0) { 
       r = Math.min(r, 1+memoArray[n/2]); 
      } 
      if(n % 3 == 0) { 
       r = Math.min(r, 1+memoArray[n/3]); 
      } 
      memoArray[i] = r; 
     } 
     return memoArray[n]; 
    } 

Mais je reçois une results.Example ambiguë - si le nombre est de 5, je reçois le nombre d'étapes nécessaires minimun que 4. En fait, il devrait être 3. Quelqu'un peut-il expliquer s'il vous plaît où je suis allé mal?

Answer 1

Je propose inverser le problème: à partir de 1 nous atteindren en utilisant trois types d'opérations :

• ajouter 1
• multiplier par 2
• multiplier par 3

Par exemple, pour 5 nous aurons 3 opérations (multiplier par 3, ajouter 1, ajouter 1):

1 -> 3 -> 4 -> 5 

Jusqu'à présent, si bon, nous avons maintenant la norme programmation dynamique problème; C# mise en œuvre:

private static int Best(int value) { 
    if (value <= 0) 
    return -1; // or throw ArgumentOutOfRangeException 
    else if (value == 1) 
    return 0; 

    Dictionary<int, int> best = new Dictionary<int, int>() { {1, 0} }; 

    List<int> agenda = new List<int>() { 1 }; 

    for (int step = 1; ; ++step) 
    for (int i = agenda.Count - 1; i >= 0; --i) { 
     int item = agenda[i]; 

     agenda.RemoveAt(i); 

     int[] next = new int[] { item + 1, item * 2, item * 3 }; 

     foreach (int v in next) { 
     if (v == value) 
      return step; 

     if (!best.ContainsKey(v)) { 
      best.Add(v, step); 
      agenda.Add(v); 
     } 
     } 
    } 
} 

Tests:

// 3 
Console.WriteLine(Best(5)); 
// 3 
Console.WriteLine(Best(10)); 
// 7 
Console.WriteLine(Best(100)); 
// 19 
Console.WriteLine(Best(1000000)); 

Answer 2

Si le nombre est de 5 vous pouvez obtenir 1 en faisant:

int x = 5 - 1; 
x = x - 1; 
x= x/3; 

Answer 3

l'intérieur de votre boucle, vous utilisez au lieu de n i.

Par exemple, n% 2 == 0 doit être i% 2 == 0