Корректность и логика алгоритма: минимальные шаги к одному

Question

Постановка задачи:

На целое положительное число, вы можете выполнить любое из следующих 3-х шагов.

1. Вычесть 1 из него. (П = п - 1)

2. Если его делится на 2, делят на 2. (если п% 2 == 0, то п = п/2)

3. Если его делится на 3, разделить на 3. (если п% 3 == 0, то п = п/3)

Учитывая положительное целое число п и Ваша задача найти минимальное количество шагов, которые принимает п к одному.

Мое рекурсивное решение (на C++) сравнивает все 3 случая, когда N делится на 3, тогда как общее решение сравнивает только 2, но все же дает правильное решение.

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

Но общее решение,

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

Мой вопрос, как же мы не сравниваем все 3 случая, но все же получить на правильное решение. Я не могу следовать алгоритму общего решения. Любая помощь, которая позволила бы мне понять, была бы очень признательна.

Answer 1

"Общее решение" является неправильным. Когда-нибудь это оптимально разделить на 2, а затем вычесть 1, а общий код решения не позволяет этого.

«Общее решение» производит неправильные результаты для 642.

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

Однако это является оптимальным, будучи один короче:

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

Вы можете увидеть общее решение начинается путем деления на 3 , и оптимальное решение начинается с деления на 2, а затем на вычитание 1 ... это именно тот случай, который был удален.

Хотя это не имеет прямого отношения к вашему вопросу, вот код, который я использовал, чтобы найти встречный пример (хотя и очень убран, так как я его написал). Он использует два алгоритма, которые вы дали, но запоминает их для экспоненциального увеличения скорости.Он также использует трюк, возвращающий два результата из min_steps: не только длину кратчайшего пути, но и первый шаг в этом пути. Это делает его чрезвычайно удобным для восстановления пути без написания большого количества кода.

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

Вот выход, включая времена хода:

$ 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

Если n делится на 3и делящегося на 2, то это не имеет значения, если вы разделите 3 первыми, а затем 2 на следующей стадии, или 2 первым, а затем 3 на следующей стадии.

Пример: 18 = 3*3*2

а) 18/3 = 6, 6/3 = 2, 2/2 = 1 или

б) 18/2 = 9, 9/2 = #!?#, 9/3 = 3, 3/3 = 1 или ...