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

Question

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

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

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

Вычтите 1 из этого. (n = n — 1)
Если его делится на 2, разделите на 2. (если n% 2 == 0, то n = n / 2)
Если его делится на 3, разделите на 3. (если n% 3 == 0, то n = n / 3)

Если задано положительное целое число n, и ваша задача — найти минимальное количество шагов, которое занимает n к одному.

Мое рекурсивное решение (в 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 случая, но все же получаем правильное решение? Я не могу следовать алгоритму общего решения. Любая помощь, чтобы дать мне понять, будет принята с благодарностью.

6

algorithm c++correctness logic

Решение

Другие решения

Если 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, или же …

0

Источник

Accepted Answer

«Общее решение» неверно. Иногда оптимально делить на 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

6