LINEBURG


<< Пред. стр.

страница 6
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>


6.5.3.3 ПРАВИЛЬНЫЕ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ

Правильными рекуррентными соотношениями (уравнениями) будем
называть такие рекуррентные соотношения, у которых количество или
значения аргументов у функций в правой части соотношения меньше
количества или, соответственно, значений аргументов функции в левой части
47
соотношения. Если аргументов несколько, то достаточно уменьшения одного
из аргументов.
Соотношения должны быть определены для всех допустимых значений
аргументов. Поэтому должны быть определены значения функций при
начальных значениях параметров.
В приведенных примерах соотношения связывали функции только с
двумя различными параметрами: S(i) и S(i - 1), а также a(i) и a(i - 1) для
любого натурального i. При этом были определены начальные значения S(0)
и a(0).
Отметим, что без этих начальных значений рекуррентное соотношение
S(i) = S(i - 1) + a(i), i>1, было бы неправильным, так как оно не определено
при i = 1.

Пример.
Написать рекуррентную формулу для подсчета количества различных
укладок плитками размера 1х2 коридора размера 2хN. При N=2 таких
укладок две:

11 12
22 21

Важнейшим моментом при решении задачи является способ сведения
задачи к подзадачам. Но не менее важным вопросом является и способ
построения решения исходной задачи из решений подзадач. Одним из
наиболее эффективных способов построения решения исходной задачи
является

6.5.3.4 ИСПОЛЬЗОВАНИЕ ТАБЛИЦ ДЛЯ ЗАПОМИНАНИЯ
РЕШЕНИЙ ПОДЗАДАЧ
В этом и заключается алгоритм решения задач, называемый методом
динамического программирования.
Задача может быть формализована в виде функции, которая зависит от
одного или нескольких аргументов. Если взять таблицу, у которой
количество элементов равно количеству всех возможных различных наборов
аргументов функции, то каждому набору аргументов может быть поставлен в
соответствие элемент таблицы. Вычислив элементы таблицы (решения
подзадач), можно найти и решение исходной задачи.
Одним из способов организации таблиц является такой подход, когда
размерность таблицы определяется количеством аргументов у функции,
соответствующей подзадаче.

Пример.
В заданной числовой последовательности A[1.. N] определить
максимальную длину последовательности подряд идущих одинаковых
элементов.
48
Пусть L(i) обозначает максимальную длину последовательности,
последним элементом которой является элемент с номером i. Тогда значение
L(i+1) может быть либо на 1 больше L(i), если элементы А(i+1) и А(i) равны,
либо L(i+1) будет равно 1, так как перед элементом с номером i+1 стоит
отличный от него элемент. Максимальное значение L(i)i=1,...,N и
соответствует решению задачи.

L[1]: = 1;
For i:=2 to N do
if A[i-1]: = A[i] then
L[i]:=L[i-1]+1
else
L[i]:=1;
IndL:=1;
For i:=2 to N do
if L[i]>L[IndL] then
IndL:=i;


ПРИМЕР.
В таблице c N строками и M столбцами, состоящей из 0 и 1,
необходимо найти квадратный блок максимального размера, состоящий из
одних единиц. Под блоком понимается множество элементов соседних
(подряд идущих) строк и столбцов таблицы. Интересующая нас часть
показана на рисунке.

111111
011101
111111
110111
101101
Положение любого квадратного блока может быть определено его
размером и положением одного из его углов.
Пусть T(i,j) есть функция, значение которой соответствует размеру
максимального квадратного блока, состоящего из одних единиц, правый
нижний угол которого расположен в позиции (i, j). Функция T(i, j) вычисляет
элемент таблицы B[i, j]. Для примера на рис. значения T(i, j) будут иметь вид

i\j 1 2 3 4 5 6
1 111111
2 012201
3 112311
4 120122
5 101101
49
Таким образом, наша задача свелась к вычислению максимального
значения функции Т при всевозможных значениях параметров i и j. Этой
функции может быть поставлена в соответствие таблица размера N*M.
Определим сначала значения элементов таблицы В, расположенных в
первой строке и в первом столбце. Получим: В(1, 1) = А[1, 1],
В(1, j) = А[1, j] при j>2,
В(i, 1) = A[i, 1] при i>2.
Эти соотношения следуют из того факта, что в этих случаях
рассматриваемая область матрицы А содержит только один элемент
матрицы.
При 2<i<N и 2<j<M для этой функции можно записать следующие
рекуррентные соотношения: B[i, j] = 0, если A[i, j] = 0 и
B[i, j] = min{B[i - 1, j], B[i, j - 1], B[i - 1, j - 1]} + 1, если A[i, j] = 1

Первое соотношение показывает, что размер максимального
единичного блока с правым нижним углом в позиции (i, j) равен нулю в
случае A[i, j] = 0.
Убедимся в правильности второго соотношения. Действительно,
величина B[i - 1, j] соответствует максимальному размеру единичного блока
таблицы A с правым нижним углом в позиции (i - 1, j). Тогда размер
единичного блока с правым нижним углом в позиции (i, j) не превышает
величину B[i - 1, j] + 1, так как к блоку в позиции (i - 1, j) могла добавиться
только одна строка. Величина B[i, j - 1] соответствует максимальному
размеру единичного блока таблицы A с правым нижним углом в позиции (i, j
- 1). Тогда размер единичного блока с правым нижним углом в позиции (i, j)
не превышает величину B[i, j - 1] + 1, так как к блоку в позиции (i - 1, j) мог
добавиться только один столбец. Величина B[i - 1, j - 1] соответствует
максимальному размеру единичного блока таблицы A с правым нижним
углом в позиции (i - 1, j - 1). Тогда размер единичного блока с правым
нижним углом в позиции (i, j) не превышает величину B[i - 1, j - 1] + 1, так
как к блоку в позиции (i - 1, j - 1) могли добавиться только одна строка и
один столбец. Итак, размер единичного блока с правым нижним углом в
позиции (i, j) равен min{B[i - 1, j], B[i, j - 1], B[i - 1, j - 1]} + 1.

В[1, 1]: = A[1, 1];
For j:=2 to 6 do
В[1, j]: = A[1, j];
for i:= 2 to 5 do
В[i, 1]: = A[i, 1];
for i:=2 to 5 do
for j:=2 to 6 do
if A[i, j]: = 1 then
begin
B[i, j]: = min(B[i, j - 1], B[i - 1, j]);
B[i, j]: = min(B[i, j], B[i - 1, j - 1]) + 1
50
end
else
B[i, j]: = 0;

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ

Задача. Максимальная сумма
В заданной числовой последовательности A[1..N] найти максимальную
сумму подряд идущих элементов.
Входные данные:
Первая строка входного файла содержит число N (1<=N<=1000).
Следующие строки содержат элементы последовательности, A[i] (-
100<=A[i]<=100), разделенные пробелами и/или переводами строк.
Выходные данные:
Выходной файл должен содержать единственное число -
максимальную возможную сумму.

Пример входного Пример выходного
файла файла
3
8
5 -3 6
Задача. Минимальный штраф - 1.
Задана матрица натуральных чисел A[1..N, 1..M], m<=n. За каждый
проход через клетку (i, j) взимается штраф A[i, j]. Необходимо определить
путь с минимальным суммарным штрафом, с которым можно пройти из
клетки (1, 1) в клетку (n, m). При этом из текущей клетки можно переходить
в любую из 3-х соседних клеток, стоящих в строке с номером, на 1 большим
текущего номера строки.
Входные данные:
Первая строка входного файла содержит числа N и M (1<=N, M<=100).
Следующие строки входного файла содержат N*M натуральных чисел A[i, j]
(1<=A[i, j]<=100).
Выходные данные:
В первой строке выходного файла должен быть записан минимальный
штраф. В каждой из следущих N строк должны быть записаны два по числа
xi, yi -- i-ая клетка искомого пути.

Пример входного Пример выходного
файла: файла:
8
32 11
213423 21
32
51
Задача. Минимальный штраф – 2.
Задана матрица натуральных чисел A[1..N, 1..M]. За каждый проход
через клетку (i, j) взимается штраф A[i, j]. Необходимо определить путь с
минимальным суммарным штрафом, с которым можно пройти из некоторой
клетки первой строки в некоторую клетку N-ой строки. При этом из текущей
клетки можно переходить в любую из 3-х соседних клеток, стоящих в строке
с номером, на 1 большим текущего номера строки.
Входные данные:
Первая строка входного файла содержит числа N и M (1<=N, M<=100).
Далее идет N*M натуральных чисел A[i, j] (1<=A[i, j]<=100)
Выходные данные:
Первая строка выходного файла должна содержать штраф. В каждой из
следующих N строк должны быть записаны два числа xi, yi -- i-ая клетка
искомого пути.

Пример входного Пример выходного
файла файла
6
32 12
213423 21
31

6.5.3.6 ВОССТАНОВЛЕНИЕ РЕШЕНИЯ ПО МАТРИЦЕ

Пример.
Для заданной числовой последовательности A[1.. N] найти
максимальную длину подпоследовательности, такой, что каждый
последующий элемент подпоследовательности делится нацело на все
предыдущие. Входными параметрами является число N и
последовательность из N целых чисел, 1<N<100, |А[i]|<100, i=1,...,N. Кроме
того, необходимо указать сами элементы последовательности.

Входные данные Выходные данные
5 3
5 -3 6 0 -10 360

Обозначим через К(i) значение функции, которая равна длине
максимальной подпоследовательности в числовой последовательности А,
последним элементом которой равен элемент с индексом i.
Нам необходимо найти значение функции К(N). Таким образом, для
решения задачи достаточно последовательно вычислить значения К(i) для
всех значений i от 1 до N.
В силу условия задачи, для вычисления значения К(i+1) достаточно
использовать предыдущие значения К(j), j=1,...i, причем только те из них, для
которых выполняется условие А[i+1] mod A[j] = 0. Таким образом,
52
К(i+1)=max{К(j)}+1, j=1,...i, А[i+1]modA[j] = 0 или равно 1, если (i+1)-й
элемент не делится ни на один предыдущий. Для приведенного примера
функции К будет соответствовать массив К
i 12345
A 5 -3 6 0 -10
K 11232
Из матрицы К видно, что максимальная длина подпоследовательности
равна 3, при этом последним элементом такой последовательности является
4-й элемент. Для определения номера предпоследнего (а он является
последним элементом подпоследовательности, длина которой на единицу
меньше максимальной длины), достаточно найти такой индекс j, для
которого выполняются соотношения j=1,...i, А[i]modA[j] = 0 и К[i]-К[j] =1.
Зная предыдущий элемент (элемент с индексом 2), аналогичным
образом можно найти элемент, стоящий перед ним. Процесс заканчивается
тогда, когда будет найден элемент, который является начальным элементом
подпоследовательности (для которого значение функции К равно 1).
Нетрудно заметить, что элементы подпоследовательности (структура
решения) восстанавливается точно в обратном порядке, в котором
происходило заполнение матрицы, соответствующей подзадачам решаемой
задачи.
Для предыдущих задач были достаточно очевидны рекуррентные
соотношения, причем параметрами функции были только количество
исходных элементов. Однако очень часто на практике в качестве параметров
выступают и другие значения, например общая сумма, максимальные
значения элементов.

Пример.
Имеется 5 неделимых предметов. Для каждого предмета известна его
масса (в кг.). Величины массы являются натуральными числами. Ваша цель
состоит в том, чтобы определить, существует ли несколько предметов,
суммарная масса предметов которого ровно 16 кг. Если такой набор
существует, то требуется определить список предметов в наборе.
Пусть элемент M(i) таблицы M соответствует массе i-го предмета.
Через Т обозначим функцию, значение которой равно 1, если такой
набор имеется, и равно 0, если такого набора нет. Аргументами у этой
функции будут количество предметов и требуемая суммарная масса набора.
Для нашей задачи Т(5,16) определим подзадачи Т(i,j), где i обозначает
количество начальных предметов, из которых можно осуществлять выбор, а j
определяет требуемую суммарную массу требуемого набора. Отметим, что
определенный таким образом первый параметр i определяет как количество
предметов для подзадачи, так и значения масс из таблицы M.
Определим сначала начальные значения функции T. При нулевых
значениях одного из аргументов значение функции равны: T(0,j)=0 при j>1,
{нельзя без предметов набрать массу j>0} T(i,0)=0 при i>=0. {всегда можно
набрать нулевую массу }.
53
Определим возможные значения функции T(i,j) при ненулевых
значениях аргументов.
Решение подзадачи, соответствующей функции T(i,j) может быть
сведено к двум возможностям: следует брать предмет с номером i в набор
или нет.
Если предмет не берется, то решение задачи с i предметами сводится к
решению подзадачи с i-1 предметами, т.е. T(i,j)=T(i-1,j). Если предмет c
номером i берется, то это уменьшает суммарную массу для i-1 первых
предметов на величину M[i], т.е. T(i,j)=T(i-1,j-M[i]).
При этом необходимо учитывать, что вторая ситуация возможна только
тогда, когда масса i-го предмета не больше значения j.
Теперь для получения решения нам необходимо выбрать лучшую из
этих двух возможностей. Поэтому рекуррентное соотношение при i>1и j>1
имеет вид:
T(i,j)=T(i-1,j) при j<M[i];
T(i,j)=max(T(i-1,j),T(i-1,j-M[i])) при j<M[i].
Пусть заданы следующие значения массы для 5 предметов:
M[1]=4;
M[2]=5;
M[3]=3;
M[4]=7;
M[5]=6.
Таблица значений функции T, которую мы также назовем T, выглядит
следующим образом:
i\j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 1 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0
1 1 0 0 0 1 0 0 0 0 00 0 0 0 0 0 0
2 1 0 0 0 1 1 0 0 0 10 0 0 0 0 0 0
3 1 0 0 1 1 1 0 1 1 10 0 1 0 0 0 0
4 1 0 0 1 1 1 0 1 1 11 1 1 0 1 1 1
5 1 0 0 1 1 1 1 1 1 11 1 1 1 1 1 1
Следовательно, Т(5,16)=1, и набор существует. Для определения
списка предметов в наборе будем поступать следующим образом.
Рассмотрим элементы Т(5,16) и Т(4,16). Так как значения обоих этих
элементов равны, то это значит, что можно набрать массу 16 кг. С помощью
первых четырех предметов, т.е. предмет 5 в возможный набор можно не
включать.
Теперь рассматриваем элементы Т(4,16) и Т(3,16). Их значения не
равны, а это значит, что предмет 4 должен быть обязательно включен в
возможный набор (без предмета 5). Поэтому предмет 4 включается в набор, а
оставшаяся требуемая масса других элементов набора равна 16-М(4)=16-7=9.
Рассматриваем элементы Т(3,9) и Т(2,9). Их значения равны, а значит,
предмет 3 в набор не включаем.
Рассматриваем элементы Т(2,9) и Т(1,9). Их значения не равны, а это
значит, что предмет 2 должен быть обязательно включен в возможный набор
54
(без предметов 3, 5). Поэтому предмет 2 включается в набор, а оставшаяся
требуемая масса других элементов набора равна 9-М(2)=9-5=4.
Наконец, рассматриваем элементы Т(1,4) и Т(0,4). Их значения не
равны, а это значит, что предмет 1 должен быть обязательно включен в
возможный набор, а оставшаяся требуемая масса других элементов набора
равна 0.
Таким образом, в искомый набор входят элементы 1, 2, 4.

Программная реализация:
T[0, 0] := 1;
for j := 1 to 16 do T[0, j] := 0;
for i := 1 to 5 do T[i, 0] := 0;
for i := 1 to 5 do begin
for j := 1 to 16 do begin
if j >= M[i] then begin
T[i, j] = max(T[i - 1, j], T[i - 1, j - M[i]])
end else begin
T[i, j] = T[i - 1, j];
end;
end;
end;

sum := 16;
if T[5, 16] = 1 then begin
for i := 5 downto 1 do begin
if T[i, sum] = T[i - 1, sum] then begin
writeln (i, "---No")
end else begin
writeln (i, "---Yes");
sum := sum - M[i];
end;
end;
end else begin
writeln("No solution");
end;

ПРИМЕР решения задачи методом ДП.
В таблице размером N*N, где N<13, клетки заполнены случайным
образом цифрами от 0 до 9. Предложить Чебурашке алгоритм, позволяющий
найти маршрут из клетки (1,1) в клетку (N,N) и удовлетворяющий
следующим условиям:
1. любые две последовательные клетки в маршруте имеют общую
сторону;
2. количество клеток маршрута минимально;
3. сумма цифр в клетках маршрута максимальна.
55


АЛГОРИТМ:
Будем искать наилучшие пути, идущие из клетки (1,1) во все остальные
клетки таблицы, в частности и в клетку (N,N). Для этого в некоторой
вспомогательной таблице B того же размера, что и А, будем отмечать суммы
цифр оптимальных путей, ведущих в соответствующие клетки. Так в
клетке(1,1) таблицы В окажется число А(1,1), потому что путь, ведущий в
нее , состоит из одной клетки. Так же легко заполняются клетки (1,2) и (2,1)
таблицы В. В них тоже ведут единственные пути. и суммы цифр вдоль них
равны А(1,1)+А(1,2) и А(1,1)+А(2,1) соответственно.
Поясним сказанное на конкретном примере. Пусть таблица А размером
5*5 имеет вид, представленный на рис.2. Нумерация клеток идет от левого
верхнего угла. Проследим за заполнением таблицы В. О клетках (1,2) и (2,1)
уже говорилось. Чтобы заполнить клетку (2,2), заметим, что в нее можно
попасть либо из клетки (1,2), либо из клетки (2,1). Следовательно, в клетку
(2,2) таблицы В надо записать либо число В(1,2)+А(2,2), либо число
В(2,1)+А(2,2), в зависимости от того, какое из них больше. Заполнение
остальных клеток таблицы В аналогично.
Если путь, ведущий в эту клетку один, то в клетку вписывается сумма
цифр вдоль этого пути. Такими клетками являются клетки вида (1,J) и (J,1).
Если же в клетку (I,J) можно попасть из клеток для которых
подсчитаны значения В, то необходимо выбрать М=мах{B(I,J-1), B(I-1,J} и
записать в клетку B(I,J) число М+А(I,J).
Клетку B(I,J) соединим чертой с той клеткой, где был достигнут

<< Пред. стр.

страница 6
(всего 10)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign