correttezza e logica di algoritmo: passi minimi ad uno

Question

problema dichiarazione:

Su un intero positivo, è possibile eseguire uno qualsiasi dei seguenti 3 passaggi.

1. Sottrarre 1 da esso. (N = n - 1)

2. Se la sua divisibile per 2, dividere per 2. (se n% 2 == 0, allora n = n/2)

3. Se la sua divisibile per 3, dividere da 3. (se n% 3 == 0, allora n = n/3)

Dato un intero positivo n e compito è trovare il numero minimo di passi che prende n a uno.

La mia soluzione ricorsiva (in C++) confronta tutti i 3 casi in cui N è divisibile per 3, mentre la soluzione generale confronta solo 2, ma fornisce comunque la soluzione corretta.

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)); 
     } 
} 

Ma la soluzione generale è,

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)); 
     } 
} 

La mia domanda è, come mai non ci confrontiamo tutti i 3 casi, ma ancora deriviamo alla soluzione corretta. Non riesco a seguire l'algoritmo della soluzione generale. Qualsiasi aiuto per farmi capire sarebbe apprezzato enormemente.

Answer 1

La "soluzione generale" non è corretto. A volte è ottimale dividere per 2 e quindi sottrarre 1, e il codice di soluzione generale non lo consente.

La "soluzione generale" produce risultati non corretti per 642.

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

Tuttavia, questo è ottimale, essendo una corta:

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

Si può vedere la soluzione generale inizia dividendo per 3 e la soluzione ottimale inizia dividendo per 2 e quindi sottraendo 1 ... che è esattamente il caso che è stato rimosso.

Anche se non è direttamente pertinente alla tua domanda, ecco il codice che ho usato per trovare il contro-esempio (anche se molto riordinato da quando l'ho scritto). Usa i due algoritmi che hai dato, ma li memorizza per un aumento esponenziale della velocità.Utilizza anche un trucco per restituire due risultati da min_steps: non solo la lunghezza del percorso più breve, ma anche il primo passo in quel percorso. Ciò rende estremamente comodo ricostruire il percorso senza scrivere molto codice aggiuntivo.

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))) 

ecco l'output, tra cui run-volte:

$ 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

Se n è divisibile per 3e divisibile per 2, allora non importa se si divide da 3 prima e poi dal 2 nella fase successiva, oppure 2 prima e poi dal 3 nella fase successiva.

Esempio: 18 = 3*3*2

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

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