У вас есть калькулятор, который выполняет с целым числом $x$ только следующие операции: сложить $x$ и $1$, умножить $x$ на $2$ или умножить $x$ на $3$. Имея положительное целое число $n$, вы должны найти минимальное количество операций, необходимых для получения числа $n$ из числа $1$.
Попробуем решить эту задачу с помощью «жадной» стратегии: если текущее число не превышает $\frac{n}{3}$, то умножим его на 3; если оно больше $\frac{n}{3}$, но не больше $\frac{n}{2}$, то умножим его на 2; в остальных случаях добавим к нему 1. Это приводит к следующему псевдокоду.
GreedyCalculator(n):
numOperations = 0
currentNumber = 1
while currentNumber<n:
if currentNumber <= n/3:
currentNumber = 3*currentNumber
else if currentNumber <= n/2:
currentNumber = 2*currentNumber
else:
currentNumber = 1+currentNumber
numOperations = numOperations+1
return numOperations
💡 Остановитесь и подумайте:
Сможете ли вы найти такое число $n$, при котором GreedyCalculator(n)
приводит к неправильному ответу?
Входные данные: Целое число $n$.
Выходные данные: В первой строке: $k$ — минимальное число необходимых операций для получения $n$ из $1$. Во второй строке: последовательность промежуточных чисел. Так, вторая строка должна содержать положительные целые числа $a_0, a_1, \dotsc, a_{k}$, при которых $a_0=1$, $a_{k}=n$, и для всех $1 \le i \le k$ $a_{i}$ равно $a_{i-1}+1$, $2 a_{i-1}$ или $3a_{i-1}$. Если таких последовательностей много, то можно вывести любую из них.
Ограничения: $1 \le n \le 10^6$.
Пример 1
Ввод | Вывод |
---|---|
1 | 0 1 |
Пример 2
Ввод | Вывод |
---|---|
96234 | 14 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234 |
- Ещё один корректный вывод в этом случае — это «1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234».
Рассмотрим решение задачи. Пусть $calculator(n)$ — минимальное количество операций, необходимых для получения числа $n$ из числа $1$. Так как последняя операция в оптимальной последовательности — это «$+1$», «$\times 2$» или «$\times 3$», мы получаем следующее рекуррентное соотношение для $n \ge 1$:
Данное рекуррентное соотношение, вместе с базовым случаем $calculator(1)=1$, можно трансформировать в рекурсивный, а затем в итерационный алгоритм.
Calculator(n):
table[1..n]←[+infinity,…,+infinity]
table[1] = 0
for k from 2 to n:
table[k]=1+table[k−1]
if k is divisible by 2:
table[k]=min(table[k],1+table[k/2])
if k is divisible by 3:
table[k]=min(table[k],1+table[k/3])
return table[n]
Помните, что помимо оптимального значения необходимо вывести оптимальную последовательность операций. Для этого обратим внимание на то, что мы можем найти последнюю операцию следующим образом:
- это «$+1$», если $calculator(n)=1+calculator(n-1)$;
- это «$\times 2$», если $n$ можно разделить на $2$ и $calculator(n)=1+calculator(n/2)$;
- это «$\times 3$», если $n$ можно разделить на $3$ и $calculator(n)=1+calculator(n/3)$.
Эти действия позволяют нам выявить оптимальную последовательность:
- найти последнюю операцию;
- заменить $n$ на $n-1$, $\frac{n}{2}$ или $\frac{n}{3}$ (в зависимости от того, какой это из трёх случаев выше);
- повторить (пока $n>1$).
Calculator(n):
table[1..n]←[+infinity,…,+infinity]
table[1] = 0
for k from 2 to n:
table[k]=1+table[k−1]
if k is divisible by 2:
table[k]=min(table[k],1+table[k/2])
if k is divisible by 3:
table[k]=min(table[k],1+table[k/3])
operations = empty list
while n > 1:
append n to operations
if table[n]=1+table[n−1]:
n = n - 1
else if n is divisible by 2 and table[n]=1+table[n/2]:
n = n/2
else if n is divisible by 3 and table[n]=1+table[n/3]:
n = n/3
return operations
Время выполнения алгоритма составляет $O(n)$.