8.8. Задача «Расставить скобки»
Авторы: Алексей Толстиков, Александр Куликов
В этой статье вы научитесь находить оптимальный способ расставить скобки в арифметическом выражении, чтобы получить наибольшее значение. Задача учит динамическому программированию с двумя таблицами — для минимальных и максимальных значений подвыражений. Вы увидите, как даже простое выражение требует аккуратного перебора всех вариантов и рекурсивного деления на подзадачи.
Ключевые вопросы статьи
Почему результат арифметического выражения зависит от порядка скобок?
Как использовать динамическое программирование для перебора всех вариантов группировки?
Как устроены таблицы для хранения минимальных и максимальных значений подвыражений?
Упражнение
Для выражения существуют два способа расставить скобки: и .
Условие упражнения
Для максимального значения нужно поставить в скобки выражение .
- Входные данные: Ввод содержит только строку длиной для некого с символами . Каждый символ на чётной позиции — это цифра (то есть целое число от 0 до 9), а на нечетной позиции — одна из трёх операций из .
- Выходные данные: Максимальное значение данного арифметического выражения из всех возможных порядков арифметических операций.
- Ограничения: — таким образом, строка содержит максимум символов.
Пример 1
|
Ввод |
Вывод |
|
5-8+7*4-8+9 |
200 |
Решение
Рассмотрим решение задачи. Каждая из пяти операций в выражении
может быть последней — внешней. Рассмотрим случай, в котором последняя операция — «», то есть умножение. В этой ситуации нам необходимо поместить два подвыражения в скобки
таким образом, чтобы произведение значений было максимальным. Чтобы это выяснить, мы находим минимальные и максимальные значения данных двух подвыражений:
На основании этих значений мы заключаем, что общее значение произведения составляет .
Предположим, что вводный набор данных имеет форму
где каждая — это цифра, а каждая — базовая арифметическая операция. Сказанное выше предполагает, что мы вычисляем минимальное и максимальное значение каждого подвыражения в форме
где . Пусть и — минимальное и максимальное значение соответственно. Тогда
Базовый случай — это :
Эти два рекуррентных соотношения позволяют нам вычислить оптимальные значения , изучив все возможные варианты разделения на два подвыражения и .
Тогда наше рекуррентное соотношение говорит о том, что дерево состоит из корня и двух поддеревьев. Для нахождения оптимальной формы дерева мы анализируем все возможные корни (за это отвечает параметр ), а затем составляем дерево из двух оптимальных поддеревьев.
Как сделать из рекуррентного соотношения рекурсивный алгоритм
Как обычно, сделать из рекуррентного соотношения рекурсивный алгоритм довольно просто. Рекурсивная процедура берёт индексы и в качестве параметров и использует их для вычисления минимального и максимального значения подвыражения .
Перед тем, как начать вычисления, проверяется, не сохранены ли уже эти значения в , где — это ассоциативный массив, хранящий уже вычисленные результаты.
Если запись отсутствует, рекурсивная процедура вычисляет два значения, используя рекуррентное соотношение, сохраняет их в таблицу и выдаёт их. Конечный ответ соответствует и .
Время выполнения составляет : есть возможных пар , для каждой из которых рекурсивная процедура проверяет возможные значения для .
Для переведения рекурсивного алгоритма в итерационный используются двумерные таблицы и , в которых хранятся минимальные и максимальные значения всех подвыражений. Заполняя данные таблицы, нам нужно убедиться, что к окончанию вычислений оптимальных значений для оптимальные значения и для всех уже вычислены.
Один из способов сделать это — перечислить все пары в порядке возрастания значения . Чтобы это сделать, в псевдокоде ниже используется параметр .
MaxValue(d[0],op[0],d[1],op[1],…d[n]):
mins, maxs = 2d-arrays of size (n+1)×(n+1)
fill mins with +infinity, fill maxs with -infinity
for i from 0 to n:
mins[i][i]=d[i], maxs[i][i]←d[i]
for s from 1 to n:
for l from 1 to n-s:
r = l+s
for m from l to r-1:
a = mins[l][m] op[m] mins[m+1][r]
b = mins[l][m] op[m] maxs[m+1][r]
c = maxs[l][m] op[m] mins[m+1][r]
d = maxs[l][m] op[m] maxs[m+1][r]
mins[l][r] = min(mins[l][r],a,b,c,d)
maxs[l][r] = max(maxs[l][r],a,b,c,d)
return maxs[0][n]
Что дальше
Теперь вы умеете вычислять максимальное значение арифметического выражения, расставляя скобки в нужном порядке. Вы научились использовать динамическое программирование с запоминанием минимальных и максимальных значений и применять аккуратные рекурсивные формулы.
Далее — финальная статья раздела. В ней мы кратко обобщим ключевые идеи, которые вы встретили, и покажем, как они складываются в систему.
Ключевые выводы статьи
- Порядок выполнения операций влияет на результат арифметического выражения — важно правильно расставить скобки.
- Можно эффективно найти максимальное значение, если сохранять минимумы и максимумы всех подвыражений в таблицах.
- Динамическое программирование позволяет избежать повторных вычислений и уменьшает время работы с экспоненциального до кубического.
- Даже при небольшом числе операций количество возможных расстановок скобок велико — поэтому важно автоматизировать перебор.