Korrektheit und Logik des Algorithmus: Mindestschritte zu eins

Question

Problembeschreibung:

Bei einer positiven ganzen Zahl können Sie einen der folgenden 3 Schritte ausführen.

1. 1 davon subtrahieren. (N = n - 1)

2. Wenn sein durch 2 teilbar, Dividieren durch 2 (wenn n% 2 == 0, dann n = n/2)

3. Wenn sein durch 3 teilbar, divide von 3. (wenn n% 3 == 0, dann n = n/3)

eine positive ganze Zahl n und Sie Aufgabe ist es, die minimale Anzahl von Schritten finden, die n Gegeben einem nimmt.

Meine rekursive Lösung (in C++) vergleicht alle 3 Fälle, wenn N durch 3 teilbar ist, während die allgemeine Lösung nur 2 vergleicht, aber immer noch die richtige Lösung gibt.

int min_steps(int N){ 
     if(N==1) return 0;  
     else{ 
       if(N%3==0){ 
         if(N%2==0) 
          return (1+min(min_steps(N/3),min_steps(N/2),min_steps(N-1))); 
         else 
          return(1+min(min_steps(N/3),min_steps(N-1))); 
       } 
       else if(N%2==0){ 
         return(1+min(min_steps(N/2),min_steps(N-1))); 
       } 
       else 
         return(1+min_steps(N-1)); 
     } 
} 

Aber die allgemeine Lösung ist,

int min_steps(int N){ 
     if(N==1) return 0;  
     else{ 
       if(N%3==0){ 
         return(1+min(min_steps(N/3),min_steps(N-1))); 
       } 
       else if(N%2==0){ 
         return(1+min(min_steps(N/2),min_steps(N-1))); 
       } 
       else 
         return(1+min_steps(N-1)); 
     } 
} 

Meine Frage ist, wie kommen wir alle drei Fälle nicht vergleichen, aber ableiten noch an der richtigen Lösung. Ich kann dem Algorithmus der allgemeinen Lösung nicht folgen. Jede Hilfe, die mich verstehen lässt, wäre sehr willkommen.

Answer 1

Die "allgemeine Lösung" ist falsch. Manchmal ist es optimal, durch 2 zu teilen und dann 1 zu subtrahieren, und der allgemeine Lösungscode lässt das nicht zu.

Die "allgemeine Lösung" falsche Ergebnisse für 642.

642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1 

Dies ist jedoch optimal ist, ein kürzer:

642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1 

Sie können die allgemeine Lösung sehen beginnt, indem durch 3 dividiert , und die optimale Lösung beginnt mit der Division durch 2 und anschließendes Subtrahieren von 1 ... was genau der Fall ist, der entfernt wurde.

Obwohl es nicht direkt relevant für Ihre Frage ist, hier ist der Code, den ich verwendet, um das Gegenbeispiel zu finden (wenn auch stark aufgeräumt, seit ich es geschrieben habe). Es verwendet die beiden Algorithmen, die Sie angegeben haben, speichert sie jedoch für eine exponentielle Geschwindigkeitserhöhung.Es verwendet auch einen Trick, um zwei Ergebnisse von min_steps zurückzugeben: nicht nur die Länge des kürzesten Pfads, sondern auch der erste Schritt in diesem Pfad. Dies macht es äußerst bequem, den Pfad zu rekonstruieren, ohne viel zusätzlichen Code zu schreiben.

def memoize(f): 
    """Simple memoization decorator""" 
    def mf(n, div2, cache={}): 
     if (n, div2) not in cache: 
      cache[n, div2] = f(n, div2) 
     return cache[(n, div2)] 
    return mf 

@memoize 
def min_steps(n, div2): 
    """Returns the number of steps and the next number in the solution. 

    If div2 is false, the function doesn't consider solutions 
    which involve dividing n by 2 if n is divisible by 3. 
    """ 
    if n == 1: 
     return 0, None 
    best = min_steps(n - 1, div2)[0] + 1, n-1 
    if n % 3 == 0: 
     best = min(best, (min_steps(n // 3, div2)[0] + 1, n//3)) 
    if n % 2 == 0 and (div2 or n%3): 
     best = min(best, (min_steps(n // 2, div2)[0] + 1, n//2)) 
    return best 

def path(n, div2): 
    """Generates an optimal path starting from n. 

    The argument div2 has the same meaning as in min_steps. 
    """ 
    while n: 
     yield n 
     _, n = min_steps(n, div2) 

# Search for values of n for which the two methods of finding 
# an optimal path give different results. 
for i in xrange(1, 1000): 
    ms1, _ = min_steps(i, True) 
    ms2, _ = min_steps(i, False) 
    if ms1 != ms2: 
     print i, ms1, ms2 
     print ' -> '.join(map(str, path(i, True))) 
     print ' -> '.join(map(str, path(i, False))) 

Hier ist die Ausgabe, einschließlich Laufzeiten:

$ time python minsteps.py 
642 10 11 
642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1 
642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1 
643 11 12 
643 -> 642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1 
643 -> 642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1 

real 0m0.009s 
user 0m0.009s 
sys 0m0.000s 

Answer 2

Wenn n teilbar durch 3und teilbar durch 2, dann spielt es keine Rolle, ob Sie durch 3 zuerst teilen und dann durch 2 im nächsten Schritt, oder durch 2 zuerst und dann durch 3 im nächsten Schritt.

Beispiel: 18 = 3*3*2

a) 18/3 = 6, 6/3 = 2, 2/2 = 1 oder

b) 18/2 = 9, 9/2 = #!?#, 9/3 = 3, 3/3 = 1 oder ...