Изменения

Перейти к: навигация, поиск

Задача о расстановке знаков в выражении

28 байт убрано, 03:56, 8 января 2014
Доказательство
== Доказательство ==
Рассмотрим ее, например, в такой формулировке. В арифметическом выражении, операндами которого являются целые числа, а операциями — бинарные арифметические операции “+” и “*”, расставить скобки так, чтобы результат оказался максимальным.
Подзадачами, через которые мы будем выражать оптимальное решение, будут задачи об оптимальной расстановке скобок в произведениях наших операндов, начиная с i-го и заканчивая j-м. Запоминать результат оптимального решения соответствующей подзадачи мы будем в элементе d[i, j] матрицы, размером n*n, диагональные элементы которой (d[i, i]) равны операндам, а для i > j все элементы равны 0. Пусть мы хотим подсчитать значение арифметического выражения для операндов, начиная с i-го и заканчивая j-м для i < j. Если мы предположим, что последней будет выполняться арифметическая операция, расположенная после операнда с номером k (k < j) и эта операция — сложение, то результат подсчета будет равен сумме элементов d[i, k] и d[k+1, j] нашей матрицы. С умножением ситуация несколько более сложная. Так как операндами могут быть и отрицательные числа, то для нахождения максимума из произведений нужно знать не только максимальные, но и минимальные значения для арифметических операций над операндами с i-го по k-й и с k+1-го по j-й соответственно. Значит для любой последовательности операндов нужно хранить значение как максимально, так и минимально возможного результата выполнения арифметических операций над ними. Однако, дополнительная матрица для хранения минимальных значений не нужна. Так как для i > j матрица d не заполнена, мы можем отвести эти элементы для хранения минимумов, только запоминать результат решения этой подзадачи для операндов, начиная с i-го и заканчивая j-м, мы будем в элементе d[j, i]. Тогда в общем случае, если после k-го операнда стоит операция умножения, то максимальный результат будет равен max(d[i, k] * d[k+1, j], max(d[k, i] * d[j, k] +1], d[i, k+1] * d[j, k+1], d[i][k, i] * d[k+1, ][j]).);
== Реализация ==
Анонимный участник

Навигация