|
Название задачи: Параллельные вычисления . |
 |
Условие
Задано арифметическое выражение, содержащее операции сложения, умножения, круглые скобки и операнды, которыми являются буквы английского алфавита. Нас будет интересовать скорость вычисления таких выражений на многопроцессорной машине, поэтому скобки в них будем расставлять в обязательном порядке для указания порядка проведения операций. Известно, что сложение двух чисел занимает время p, а умножение – время
q. Время, необходимое для вычисления сложного выражения
AoB, равно времени, затрачиваемому на выполнение операции
o, плюс максимальное из двух чисел – времени вычисления подвыражения A и времени вычисления
подвыражения B. Время вычисления операнда полагаем равным нулю.
Требуется написать программу, которая:
1. Определяет время, необходимое для вычисления заданного выражения на
многопроцессорной машине.
2. Находит эквивалентное заданному арифметическое выражение с
минимальным временем вычисления и само это время.
Выражения называется эквивалентными, если одно из них можно получить
из другого последовательностью следующих преобразований:
x + y → y + x
,
x * y → y * x
(коммутативный закон),
x + (y + z) → (x + y) + z , x * (y
* z) → (x * y) * z (ассоциативный закон).
Входные данные
В первой строке входного файла содержатся два целых числа p и q
(1 ≤ p,q ≤ 1000), во второй – арифметическое выражение длиной не более 200
символов.
Выходные данные
Первая строка выходного файла должна содержать ответ на первый пункт
задачи. Во вторую строку выведите эквивалентное заданному выражение с
минимальным временем вычисления, а в третью – само это время.
Пример входного файла
1 1
((a+(b+(c+d)))*e)*f
Пример выходного файла
5
((a+b)+(c+d))*(e*f)
3
Решение
Скачать архив тестов и решенийВыполняя синтаксический разбор заданного выражения методом рекурсивного спуска [Шень 95, гл. 13], построим соответствующее этому выражению дерево. Листам полученного дерева будут приписаны операнды, а внутренним вершинам – операции, над ними совершаемые. Таким образом, дерево будет содержать два типа внутренних вершин – +-вершины и *-вершины. (Пример работы с такими структурами данных см. в [Кнут 76, п. 2.3.2].)
Наложим на дерево, которое строится в процессе разбора, дополнительное требование: одна внутренняя вершина не может быть отцом другой внутренней вершины того же типа. Т.е. сыновьями +-вершины могут быть только операнды и *-вершины, а сыновьями *-вершины – только операнды и +-вершины. Выполнение этого требования достигается за счет отказа от бинарности дерева. Например, выражение ((a+b)+(c+d)) преобразуется к форме +(a,b,c,d). Использование этой формы корректно, так как заданными в условии задачи преобразованиями разрешается любой порядок сложений.
Теперь используем метод динамического программирования, сводя задачу
для дерева к аналогичным задачам для его поддеревьев (при программировании
это реализуется рекурсивной функцией). При этом используем жадный
алгоритм: как только вычислились два аргумента для операции, отнесенной к
корню рассматриваемого дерева (+-вершине или *-вершине), сразу начинаем их
складывать или, соответственно, умножать.
Упражнение
Докажите, что использование жадного алгоритма приведет к минимально
возможному времени вычисления.
