В этом параграфе вы научитесь строить оптимальную последовательность операций, которая позволяет получить заданное число, начиная с 1. На первый взгляд кажется разумным всегда делить число пополам, если это возможно, — но такой жадный подход не гарантирует кратчайшего пути. Мы разберём, как динамическое программирование позволяет найти действительно минимальную последовательность шагов.
Ключевые вопросы параграфа
- Почему жадная стратегия не гарантирует оптимальный результат при построении последовательности операций?
- Как использовать динамическое программирование для поиска минимального числа шагов?
- Как восстановить оптимальную последовательность действий из таблицы значений?
Вводная информация по задаче
У вас есть калькулятор, который выполняет с целым числом только следующие операции: сложить и , умножить на или умножить на . Имея положительное целое число , вы должны найти минимальное количество операций, необходимых для получения числа из числа .
Попробуем решить эту задачу с помощью «жадной» стратегии: если текущее число не превышает , то умножим его на 3; если оно больше , но не больше , то умножим его на 2; в остальных случаях добавим к нему 1. Это приводит к следующему псевдокоду.
1GreedyCalculator(n):
2 numOperations = 0
3 currentNumber = 1
4 while currentNumber<n:
5 if currentNumber <= n/3:
6 currentNumber = 3*currentNumber
7 else if currentNumber <= n/2:
8 currentNumber = 2*currentNumber
9 else:
10 currentNumber = 1+currentNumber
11 numOperations = numOperations+1
12 return numOperations
Остановитесь и подумайте:
Сможете ли вы найти такое число , при которомGreedyCalculator(n)
приводит к неправильному ответу?
- Входные данные: Целое число .
- Выходные данные: В первой строке: — минимальное число необходимых операций для получения из . Во второй строке: последовательность промежуточных чисел. Так, вторая строка должна содержать положительные целые числа , при которых , , и для всех равно , или . Если таких последовательностей много, то можно вывести любую из них.
- Ограничения: .
Пример 1
Ввод |
Вывод |
1 |
0 |
Пример 2
Ввод |
Вывод |
96234 |
14 |
- Ещё один корректный вывод в этом случае — это «1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234».
Решение
Рассмотрим решение задачи. Пусть — минимальное количество операций, необходимых для получения числа из числа . Так как последняя операция в оптимальной последовательности — это «», «» или «», мы получаем следующее рекуррентное соотношение для :
Данное рекуррентное соотношение, вместе с базовым случаем , можно трансформировать в рекурсивный, а затем в итерационный алгоритм.
1Calculator(n):
2 table[1..n]←[+infinity,…,+infinity]
3 table[1] = 0
4
5 for k from 2 to n:
6 table[k]=1+table[k−1]
7 if k is divisible by 2:
8 table[k]=min(table[k],1+table[k/2])
9 if k is divisible by 3:
10 table[k]=min(table[k],1+table[k/3])
11 return table[n]
Помните, что помимо оптимального значения необходимо вывести оптимальную последовательность операций. Для этого обратим внимание на то, что мы можем найти последнюю операцию следующим образом:
- это «», если ;
- это «», если можно разделить на и ;
- это «», если можно разделить на и .
Эти действия позволяют нам выявить оптимальную последовательность:
- найти последнюю операцию;
- заменить на , или (в зависимости от того, какой это из трёх случаев выше);
- повторить (пока ).
1Calculator(n):
2 table[1..n]←[+infinity,…,+infinity]
3 table[1] = 0
4
5 for k from 2 to n:
6 table[k]=1+table[k−1]
7 if k is divisible by 2:
8 table[k]=min(table[k],1+table[k/2])
9 if k is divisible by 3:
10 table[k]=min(table[k],1+table[k/3])
11
12 operations = empty list
13 while n > 1:
14 append n to operations
15 if table[n]=1+table[n−1]:
16 n = n - 1
17 else if n is divisible by 2 and table[n]=1+table[n/2]:
18 n = n/2
19 else if n is divisible by 3 and table[n]=1+table[n/3]:
20 n = n/3
21 return operations
Время выполнения алгоритма составляет .
Что дальше
Теперь вы знаете, как находить минимальную последовательность операций для получения заданного числа, используя динамическое программирование. Вы научились строить таблицу значений и восстанавливать по ней путь — от цели к началу. А ещё убедились, что жадный подход может подвести, даже если кажется логичным.
Далее — задача на редактирование строк. Вы узнаете, как рассчитать расстояние между двумя строками, используя матрицу изменений, и зачем это нужно в задачах на сравнение, поиск и коррекцию.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Жадный алгоритм может не давать оптимальный результат — даже если кажется разумным.
- Динамическое программирование позволяет найти кратчайшую последовательность операций с минимальными затратами.
- Чтобы восстановить путь, нужно не только посчитать значения, но и зафиксировать переходы.
- Умение строить такие цепочки важно для задач, где нужно не только посчитать, но и объяснить, как получить ответ.