Изменения
Новая страница: «'''Задача о расстановке знаков в выражении''' — задача о нахождении максимального значения …»
'''Задача о расстановке знаков в выражении''' — задача о нахождении максимального значения выражения, полученного расстановкой знаков <tex dpi = "120">+, \times</tex> и скобок в последовательности <tex dpi = "130">a_1, a_2, \dots, a_n \ (a_i \ge 0)</tex>.
== Решение ==
Данная задача решается с использованием принципа оптимальности на подотрезке. Введём матрицу <tex>d</tex> размером <tex>n \times n</tex>, где <tex>d[i][j]</tex> будет равен максимальному значению, достигаемому на подотрезке <tex dpi = "130">a_i, a_{i+1}, \dots, a_j</tex>.
Получаем следующие соотношения: <br />
* <tex dpi = "141">d[i][i] = a_i </tex><br />
* <math>d[i][j] = \max_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k]*d[k+1][j])] \ (i < j)</math> <br />
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.
== Реализация ==
// d - матрица как в описании; a - последовательность из n элементов; i, j, k - счётчики
for i := 1 to n do
d[i][i] := a[i];
for i := n - 1 downto 1 do
for j := i + 1 to n do
for k := i to j - 1 do
d[i][j] := max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] * d[k+1][j]));
write(d[1][n]); // ответ
== Пример ==
Пусть дана последовательность 2, 1, 1, 2. Таблица <tex>d</tex> для неё будет выглядеть так:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| || j = 1 || j = 2 || j = 3 || j = 4
|-
| i = 1 || 2 || 3 || 4 || 9
|-
| i = 2 || 0 || 1 || 2 || 4
|-
| i = 3 || 0 || 0 || 1 || 3
|-
| i = 4 || 0 || 0 || 0 || 2
|}
== Решение ==
Данная задача решается с использованием принципа оптимальности на подотрезке. Введём матрицу <tex>d</tex> размером <tex>n \times n</tex>, где <tex>d[i][j]</tex> будет равен максимальному значению, достигаемому на подотрезке <tex dpi = "130">a_i, a_{i+1}, \dots, a_j</tex>.
Получаем следующие соотношения: <br />
* <tex dpi = "141">d[i][i] = a_i </tex><br />
* <math>d[i][j] = \max_{\mathop{k = i..j-1}}[\max(d[i][k]+d[k+1][j], d[i][k]*d[k+1][j])] \ (i < j)</math> <br />
Вычислим элементы таблицы <tex>d</tex>, тогда ответом на задачу будет значение <tex>d[1][n]</tex>.
== Реализация ==
// d - матрица как в описании; a - последовательность из n элементов; i, j, k - счётчики
for i := 1 to n do
d[i][i] := a[i];
for i := n - 1 downto 1 do
for j := i + 1 to n do
for k := i to j - 1 do
d[i][j] := max(d[i][j], max(d[i][k] + d[k+1][j], d[i][k] * d[k+1][j]));
write(d[1][n]); // ответ
== Пример ==
Пусть дана последовательность 2, 1, 1, 2. Таблица <tex>d</tex> для неё будет выглядеть так:
{| class="wikitable" cellpadding="4" border="1" style="border-collapse: collapse;"
|-
| || j = 1 || j = 2 || j = 3 || j = 4
|-
| i = 1 || 2 || 3 || 4 || 9
|-
| i = 2 || 0 || 1 || 2 || 4
|-
| i = 3 || 0 || 0 || 1 || 3
|-
| i = 4 || 0 || 0 || 0 || 2
|}
