| | если j>1 и Штраф[i, j] < Штраф[i – 1, j – 1] + A[i, j]

| | | то Штраф[i, j]: = Штраф[i – 1, j – 1] + A[i, j];

| | все

| | если j<m и Штраф[i, j] < Штраф[i – 1, j + 1] + A[i, j]

| | | то Штраф[i, j]: = Штраф[i – 1, j + 1] + A[i, j];

| | все

| кц

кц

9. а) Обозначим вершины N-угольника x0, ..., xN – 1 в порядке обхода по контуру. В дальнейшем будем считать, что если у нас в выкладках встречается вершина с индексом k, то это то же, что и вершина с номером k mod N (остаток от деления k на N).

Рассмотрим выпуклый L-угольник, вершинами которого являются L последовательных вершин данного N-угольника, начиная с xp и до xp + L – 1 (в порядке обхода по контуру). У этого L-угольника, L>1, будем считать, что отрезок [xp; xp + L – 1] – это его диагональ. Сумму диагоналей этой фигуры обозначим S(p, p + L – 1).

Очевидно, что по условию задачи:

S(p, p) = 0; S(p, p + 1) = 0 (у точки и отрезка нет диагоналей),

S(p, p + 2) = d(p, p + 2) (тут d(p, p + 2) – длина отрезка [xp; xp + 2]).

Предположим, что мы знаем S(p, p + L – 1) для всех p = 0, ..., N – 1 и L = 1, ..., k.

Найдем S(p, p + k).

Мы знаем, что диагонали разбивают k + 1 угольник на треугольники, и что [xp, xp + k] – диагональ, т. е. одна из сторон какого-то треугольника. Итак, мы зафиксировали две вершины треугольника – xp и xp + k. Третьей вершиной может быть либо xp + 1, либо xp + 2, ..., либо xp + k – 1. Если мы считаем, что третья вершина – это xi, то сумма длин диагоналей будет

НЕ нашли? Не то? Что вы ищете?

d(p, p + k) + S(p, i) + S(i, k). (1)

Тут мы уже знаем S(p, i) и S(i, k) – они, по предположению, были вычислены на предыдущих шагах. d(p, p + k) – это расстояние между вершинами xp и xp + k, его мы тоже можем вычислить.

Так как нас интересует минимальная сумма триангуляции (разбиения на треугольники), то мы ищем выражение (1) с минимальным значением

S(p, p + k) = d(p, p + k) + ( S(p, i) + S(i, k)) (2)

при i = p + 1, p + 2, ..., k – 1.

Находим S(p, p + k) для каждого p = 0, ..., N – 1.

Минимум S(p, p + N – 2) по p = 0, ..., N – 1, и даст искомую триангуляцию (действительно, S(p, p + N – 2) есть стоимость разбивки фигуры после проведения N – 3 диагоналей).

б) Алгоритм остается тем же, за исключением того, что вместо формулы (2) надо использовать следующую:

S(p, p + k) = max (d(p, p + k), S(p, i), S(i, k)),

где S(p, p + k) – длина максимальной диагонали в фигуре с вершинами xp, xp + 1, ..., xp + k (отрезок [xp, xp + k] считается диагона­лью). Мы берем минимум по всем возможным разбивкам фигуры, а стоимость разбивки определяется как максимум из длины диагонали d(p, p + k) и длин максимальных иагоналей S(p, i) и S(i, k).

10. Для x = a, ..., am и y = b1..., bn, ai и bi – символы, 1£ i£ m, 1£ j£ n, d(x, y) можно вычислить, применяя метод динамического программиро­вания.

Определим массив d[0..m, 0..n], элементы которого

d[i, j] = d(a1... ai, b1... bj), 0£ i£ m, 0£ j£ n.

Понятно, что

d[0, j] = j;

d[i, 0] = i;

Очевидным образом получаем

d[i, j] = min(d[i – 1, j] + 1, d[i, j – 1] + 1, d[i – 1, j – 1] + Pij)

где Pij = 1 если ai ¹ bj и Pij = 0 иначе (в правой части приведенного выше выражения первому элементу в min соответствует операция удаления из строки a1... ai – 1ai последнего элемента ai, после чего за d[i – 1, j] операцию строка a1... ai – 1 преобразуется в строку b1... bj, второму элементу – операция вставки символа bj в конец строки b1... bj – 1, полученной за d[i, j – 1] операцию из строки a1... ai, а третьему – контекстная замена ai на bj, замена осуществляется в случае ai¹bj (тогда Pij = 1) и не происходит при совпадении ai и bj).

Получаем необходимое d(x, y) = d[m, n].

Алгоритм может быть записан так:

for i: = 1 to m do

d[i, 0]: = i;

for j: = 1 to n do

d[0, j]: = j;

for i: = 1 to m do

for j: = 1 to n do

d[i, j] = min(d[i – 1, j] + 1, d[i, j – 1] + 1, d[i – 1, j – 1] + Pij);

11. Пусть строка x состоит из цифр 0 и 1 и имеет длину N, а строка y (из символов A и B) – длину M.

Заведем матрицу А размера N на M, при этом строки матрицы помечаются i-ой цифрой строки x, а столбец – j-м символом строки y.

Возьмем в качестве примера x = '00110', y = 'AAAABBAA'.

Первая цифра строки x (цифра 0) может быть преобразована в одну из последовательностей букв 'A', 'AA', 'AAA', 'AAAA', являющихся префиксами строки y. Заносим символ ' * ' в те столбцы первой строки, буквы-пометки которых соответствуют последним буквам возможных последовательностей.

Таким образом, помечаются элементы A[1, 1], A[1, 2], A[1, 3] и A[1, 4].

На каждом следующем шаге алгоритма будем преобразовывать очередную i-ю цифру строки x, которой соответствует i-я строка матрицы A.

Находим '*' в предыдущей строке при просмотре ее слева направо (этому столбцу соответствует последняя буква в какой-то из непустых последовательностей букв, порожденных на предыдущем шаге). Если текущую цифру можно преобразовать в последовательность букв, помечающих следующие за найденным столбцы, то в этих столбцах в рассматриваемой строке ставим ' * '.

Далее от места над последней помеченной ячейкой ищем в предыдущей строке ' * ' и, когда находим, повторяем указанные выше операции.

Эти действия проводим далее для i = 2, ..., N.

Вид матрицы после N шагов:

A

A

A

A

B

B

A

A

0

*

*

*

*

0

*

*

*

1

*

*

*

*

1

*

*

*

*

*

0

*

*

Если после N шагов в позиции (N, M) стоит x, то строки можно преобразовать друг в друга

Замечание: Можно обойтись и одномерным массивом. В самом деле, при заполнении следующей строки мы обращаемся только к элементам предыдущей строки, к каждому – по одному разу.

12. Определим через F[i, j] минимальное число операций, которое требуется для перемножения группы матриц с номерами от i до j включительно.

Ясно, что F[i, i] = 0.

Перемножение группы матриц с номерами от i до j может производиться различными способами, а именно, для некоторого выбранного k сначала перемножаются наилучшим способом матрицы с номерами от i до k, затем матрицы от k + 1-ой до j-ой, и, наконец, перемножаются получившиеся матрицы. Понятно, что k может быть величиной от i до j – 1. Учитывая требование получить наилучший результат, величина F[i, j] определяется как

F[i, j] = max(F[i, k] + F[k + 1, j] + n[i] * n[k + 1] * m[j]),

где k может быть величиной от i до j – 1, а n[i], n[k + 1], m[j] определяют размеры матриц, получившихся при перемножении в группах.

нц для i от 1 до s выполнять

| F[i, i]: = 0;

кц

нц для р от 1 до s – 1 выполнять

| нц для i от 1 до s – р выполнять

| | Kol: = бесконечность;

| | j: = i + p;

| | нц для k от i до j – 1 выполнять

| | | если Kol > F[i, k] + F[k + 1, j] + n[i] * n[k + 1] * m[j]

| | | | то Kol: = F[i, k] + F[k + 1, j] + n[i] * n[k + 1] * m[j];

| | | все

| | кц

| | F[i, j]: = Kol;

| кц

кц

В ячейке F[1, s] после завершения работы алгоритма будет находиться искомое минимальное число операций.

Подумайте, каким образом можно в произведении A1, ..., As расставить скобки так, чтобы они определяли оптимальный порядок умножений.

13. а). Рассмотрим сначала наиболее очевидный, но, как это обычно бывает, наименее эффективный (очень медленный) алгоритм. Мы будем генерировать все подпоследовательности данной N-элементной последовательности и для каждой из подпоследова­тельностей проверять, является ли она строго возрастающей и максимальной по длине.

Алгоритм: будем генерировать числа от 0 до 2n – 1, находить их двоичное представление и формировать подпоследовательность из элементов массива А с индексами, соответствующими единичным битам в этом представлении.

Всего существует 2n таких подпоследовательностей, поэтому даже при небольших n результата придется ждать очень долго.

Предположим, что при генерации подпоследовательностей мы нашли k-элементную строго возрастающую подпоследовательность. В дальнейшем имеет смысл рассматривать только подпоследова­тельности, состоящие из более чем k элементов (подумайте, почему?).

Рассмотрим исходную N-элементную последовательность. Если она не является искомой, то будем генерировать (N – 1)-элементные подпоследовательности. Если и среди них не найдено решение, то будем рассматривать подпоследовательности из (N – 2)-х элементов, и т. д.

В худшем случае (каком?) придется анализировать порядка 2n вариантов.

Для более быстрого решения этой задачи можно применить дихотомию по k – количеству элементов в подпоследовательности (как?).

Рассмотрим другое, более эффективное решение этой задачи. Заведем массивы A, B и C длины N: массив A[1.. N] используется для хранения чисел исходной последовательности. Элемент B[i] – значение длины максимальной возрастающей подпоследователь­ности, последний элемент которой A[i]. Величина C[i] есть индекс элемента, предшествующего элементу A[i] в этой максимальной подпоследовательности (A[i] = 0 если предшествующего элемента нет).

Если N = 1, то A[1] и есть искомая подпоследовательность. При этом B[1] = 1, C[1] = 0. Предположим, что мы заполнили массивы B и C от начала и до элемента i – 1. Попытаемся получить элементы B[i] и C[i]. Для этого будем просматривать массив A от 1 до i – 1-го элемента и искать такой индекс k, для которого одновременно выполняются следующие условия:

а) A[k]<A[i],

б) B[k] максимально.

Очевидно, что максимальную по длине подпоследовательность, заканчивающуюся элементом A[i], можно получить, приписав этот элемент к максимальной подпоследовательности с последним элементом A[k]. Следовательно, B[i] = B[k] + 1 и C[i] = k.

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6