LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

максимум М. Для нахождения искомого маршрута достаточно пройти из
клетки (N,N) в клетку (1,1) по черточкам.

4— 7— 12—19— 4
4 35 7 5 || |
1 94 1 3 5 16—20—21 27
2 3Т 5 1 2 || | |
1 31 2 0 7 19 25—26 29
4 67 2 1 || | | |
8 22 26 28 29
таб. А ||
12 28—35—37—38
таб. В
Программная реализация:
var
i,k,j,N:integer;
a,b:array[1..13,1..13] of integer;
c:array[1..25,1..2] of integer;

FUNCTION max(a1,a2:integer):integer;
56
{Функция определения max из двух чисел }
var
d:integer;
begin
if a1>a2
then
d:=a1
else
d:=a2;
max:=d;
end;

BEGIN
ReadLn(N); {Размерность матрицы}
for i:= 1 to N do
for k:= 1 to N do
ReadLn(a[i,k]); {Ввод матрицы}

b[1,1]:=a[1,1]; {Заполнение матрицы В}
for i:=2 to N do
begin
b[1,i]:=a[1,i]+b[1,i-1];
b[i,1]:=a[i,1]+b[i-1,1];
end;
for i:= 2 to N do
for k:= 2 to N do
b[i,k]:=a[i,k]+max(b[i-1,k],b[i,k-1]);

i:=N; {Чтение пути от конца к началу}
k:=N;
j:=2*N-1;
c[1,1]:=1;
c[1,2]:=1;
while (i<>1) or (k<>1) do
begin
c[j,1]:=i;
c[j,2]:=k;
if i=1
then Dec(k)
else if k=1
then Dec(i)
else if max(b[i-1,k],b[i,k-1])=b[i,k-1]
then
Dec(k)
else
57
Dec(i);
Dec(j);
end;
Write(c[1,1],',',c[1,2]);
for i:=2 to 2*N-1 do
Write('->',c[i,1],',',c[i,2]);
WriteLn;
END.
Результат работы:
1,1->1,2->2,2->3,2->4,2->5,2->5,3->5,4->5,5

ПРИМЕР решения задачи методом ДП:
ОПТИМАЛЬНАЯ РАССТАНОВКА СКОБОК.
В арифметическом выражении, операндами которого являются целые
числа от 0 до 9, а операциями – бинарные операции «+» и «*», расставить
скобки так, чтобы результат оказался максимальным.

ПРОГРАММНАЯ РЕАЛИЗАЦИЯ:
type pt=array[1..4] of byte;
var r_max,r_min,n,m,t,i,j,k:longint; a:array[1..35,1..35] of longint;
op:array[1..35] of char; b:array[1..35,1..35] of pt;
b_max,b_min:pt;ex:extended;
procedure init;{Процедура читает из файла числа}
var ch:char; {Символьная переменная}
flgmin:boolean;{Флаг отрицательного числа}
begin
assign(input,'input.txt');{Связываем стандартный поток ввода с}
reset(input); {файлом "input.txt" и открываем его для чтения}
t:=0;n:=0; {Обнуляем переменные-счетчики}
flgmin:=false; {Флаг отриц. числа выставляем в false}
while not eoln(input) do {Читаем всю строку}
begin
read(ch); {Читаем символ}
case ch of {Обрабатываем символ}
'0'..'9':t:=t*10+(ord(ch)-48);{В t считываем текущее число}
'*','+':begin {Обнаружили арифметический знак}
inc(n); {Следовательно, увеличилось количество чисел}
op[n]:=ch; {Записываем в op операцию}
if flgmin then {Если число отрицательное то}
a[n,n]:=-t {Учитываем знак}
else a[n,n]:=t;
flgmin:=false; {Флаг отриц. след. числа выставляем в false}
t:=0;
end;
'-':flgmin:=true; {Текущее число - отрицательное}
58
end;
end;
inc(n); {Добавляем последнее число}
if flgmin then t:=-t;
a[n,n]:=t;
close(input); {Закрываем файл}
end;
procedure run; {Основная подпрограмма}
procedure fillmax(a,b,c,d:longint);
begin b_max[1]:=a;b_max[2]:=b;b_max[3]:=c;b_max[4]:=d;end;
procedure fillmin(a,b,c,d:longint);
begin b_min[1]:=a;b_min[2]:=b;b_min[3]:=c;b_min[4]:=d;end;
begin
for m:=1 to n-1 do {Идем по диогоналям}
for i:=1 to n-m do
begin
j:=i+m;{Считаем j координату}
r_max:=-maxlongint; {Максимальная сумма}
r_min:=maxlongint; {Минимальная сумма}
for k:=i to j-1 do
case op[k] of
'+':begin {Знак сложения}
if r_max<a[i,k]+a[k+1,j] then {Сумма больше...}
begin fillmax(i,k,k+1,j);r_max:=a[i,k]+a[k+1,j];end;
if r_min>a[k,i]+a[j,k+1] then {Сумма меньше...}
begin fillmin(k,i,j,k+1);r_min:=a[k,i]+a[j,k+1];end;
end;
'*':begin {Знак умножения}
if r_max<a[i,k]*a[k+1,j] then
begin fillmax(i,k,k+1,j);r_max:=a[i,k]*a[k+1,j];end;
if r_max<a[k,i]*a[j,k+1] then
begin fillmax(k,i,j,k+1);r_max:=a[k,i]*a[j,k+1];end;
if r_max<a[i,k]*a[j,k+1] then
begin fillmax(i,k,j,k+1);r_max:=a[i,k]*a[j,k+1];end;
if r_max<a[k,i]*a[k+1,j] then
begin fillmax(k,i,k+1,j);r_max:=a[k,i]*a[k+1,j];end;
if r_min>a[i,k]*a[k+1,j] then
begin fillmin(i,k,k+1,j);r_min:=a[i,k]*a[k+1,j];end;
if r_min>a[k,i]*a[j,k+1] then
begin fillmin(k,i,j,k+1);r_min:=a[k,i]*a[j,k+1];end;
if r_min>a[i,k]*a[j,k+1] then
begin fillmin(i,k,j,k+1);r_min:=a[i,k]*a[j,k+1];end;
if r_min>a[k,i]*a[k+1,j] then
begin fillmin(k,i,k+1,j);r_min:=a[k,i]*a[k+1,j];end;
end;
59
end;{Записываем лучшие результаты}
a[i,j]:=r_max;a[j,i]:=r_min;b[i,j]:=b_max;b[j,i]:=b_min;
end;
end;
procedure rec(x,y:byte);
begin {Процедура по массиву b востанавливает положение скобок}
if b[x,y,1]=b[x,y,2] then {Выводим 1-ое выражение}begin
if (a[b[x,y,1],b[x,y,2]]<0) then write('[');
write(a[b[x,y,1],b[x,y,2]]); {Если выражение-число, то пишем число}
if (a[b[x,y,1],b[x,y,2]]<0) then write(']');end else
begin write('(');rec(b[x,y,1],b[x,y,2]);write(')');end;
if b[x,y,2]>b[x,y,1] then{Выводим знак операции}write(op[b[x,y,2]])
else write(op[b[x,y,1]]);{Выводим 1-ое выражение}
if b[x,y,3]=b[x,y,4] then begin
if (a[b[x,y,3],b[x,y,4]]<0) then write('[');
write(a[b[x,y,3],b[x,y,4]]); {Если выражение-число, то пишем число}
if (a[b[x,y,3],b[x,y,4]]<0) then write(']');end else
begin write('(');rec(b[x,y,3],b[x,y,4]);write(')'); end;
end;
begin
init;run;
assign(output,'output.txt');
rewrite(output);
writeln(a[1,n]);{Выводим ответ}rec(1,n);{Выводим скобки}
close(output);
end.


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

1. ДВА РЮКЗАКА - 1
Дан массив чисел А[1..N], элементы которого являются натуральными
числами. Требуется определить, можно ли эти числа разбить на два
подмножества с одинаковой суммой элементов.
Входные данные:
В первой строке входного файла находится число N (1<=N<=100).
Далее идет N натуральных чисел A[i] (1<=A[i]<=100).
Выходные данные:
Если искомое разбиение существует, в выходной файл необходимо
вывести YES, иначе вывести NO.
Пример входного Пример выходного
файла файла
4
YES
4312
60
2. ДВА РЮКЗАКА – 2.
Дан массив чисел А[1..N], элементы являются натуральными числами.
Требуется разбить эти числа разбить на два подмножества, чтобы сумма
элементов в подмножествах отличалась минимальным образом. Входными
параметрами являются N, и N натуральных чисел. Ответом должны быть
номера элементов первого множества.
Входные данные:
В первой строке входного файла находится число N (1<=N<=100).
Далее идет N натуральных чисел A[i] (1<=A[i]<=100). Сумма всех A[i] не
превосходит 1000.
Выходные данные:
В выходной файл необходимо вывести разницу p (p>=0) и затем
вывести номера элементов из первого множества.
Пример входного Пример выходного
файла файла
4
013
4312


6.6 ВОЛНОВЫЕ АЛГОРИТМЫ.

Данные алгоритмы достаточно полно разобраны в разделе «Графы»
(раздел 7.4) и рассматривают способы поиска кратчайшего пути в графе. Тем
менее эти алгоритмы относятся и к динамическому программированию.
При реализации волновых алгоритмов часть таблицы, отведенная для
запоминания решений подзадач, остается незаполненной, а часть действий
алгоритма является лишней, что и отличает эти алгоритмы от рассмотренных
выше. Но именно эта возможность использовать избыточную память и
увеличивать количество производимых операций примерно в N раз делает
программы, реализующие эти алгоритмы, простыми для понимания и
реализации.

ЗАДАЧА О ЛАБИРИНТЕ.
Лабиринт задан массивом А размером N*N, в котором A[i,j]=1, если
клетка «проходима», и A[i,j]=0, если “непроходима”. Путник изначально
размещается в клетке [i0,j0]. Он может перемещаться в любую из соседних
«проходимых» клеток, если у нее есть общая сторона с той, в которой он
находится.
Определить, может ли путник выйти из лабиринта. Если да, то
напечатать путь от выхода до начального положения путника. Выходом
считается любая граничная точка массива А.

Алгоритм решения:
Запишем в клетку [i0,j0] число 2. Просмотрим все клетки лабиринта
(или исключим из рассмотрения заведомо недостижимые за один ход). Если
61
у рассматриваемой «проходимой» клетки, помеченной единицей, есть сосед,
помеченный двойкой (в общем случае числом K), то мы запишем в нее 3( в
общем случае К+1). Т.о. на каждом шаге алгоритма числом К будут
помечены все те клетки, до которых путник может добраться ровно за К-2
единичных перемещения (до которых за К-2 шага «докатилась волна»). Этот
процесс закончится , когда очередное число будет вписано в граничную
клетку либо, когда за весь просмотр массива ни одна из клеток не будет
помечена числом К (выхода в этом случае нет). Печать решения: если
последняя клетка помечена числом К, то предпоследняя – числом К-1, и т.д.
Полученный путь по построению является кратчайшим. Дополнительные
массивы можно не заводить, однако просмотр ряда клеток массива будет
избыточным.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ
Задача 1. ПРО БОЛЬНОГО ВОРА.
Вор, пробравшись в хранилище банка, обнаружил N СЛИТКОВ золота.
Но стоимость каждого слитка была разной из-за проб золота в них (С[I]). Вес
слитков тоже различался (M[I]). Поднять вор может только Х кг (перед
операцией его от волнения стукнул радикулит). Помогите больному вору
забрать наиболее драгоценный груз.
Задача 2. ЧИСЛА.
Имеется N положительных чисел X1,X2...XN и число N. Выяснить
можно ли получить N, складывая некоторые из чисел X1,X2...XN. Число
действий должно быть порядка N2.
Задача 3.
N различных станков один за другим объединены в конвейер.
Имеется N рабочих. Задана матрица C[N,N], где C[i,j] производительность i-
ого рабочего на j-ом станке. Определить
a) на каком станке должен работать каждый из рабочих, чтобы
производительность была максимальной.
b) то же, но станки расположены параллельно и выполняют
однородные опеpации.
Задача 4. ТРЕУГОЛЬНИК.
На рисунке изображен треугольник из чисел. Написать программу,
которая вычисляет наибольшую сумму чисел, расположенных на пути,
начинающемся в верхней точке треугольника и заканчивающемся на
основании треугольника:
• каждый шаг на пути может осуществляться вниз по диагонали
влево или вниз по диагонали вправо;
• число строк в треугольнике >1 и <100;
• треугольник составлен из целых чисел от 0 до 99.
7 62
8 3
8 1 0
2 7 4 4
4 5 2 6 5
Задача 5. АВТОЗАПРАВКА.
Вдоль кольцевой дороги расположено m городов, в каждом из которых
есть автозаправочная станция. Известна стоимость Z[i] заправки в городе с
номером i и стоимость C[i] проезда по дороге, соединяющей i - й и (i+1)-й
города, C[m] - стоимость проезда между первым и m-м городами. Для
жителей каждого города определить город, в который им необходимо
съездить, чтобы заправиться самым дешевым образом, и направление - «по
часовой стрелке» или «против часовой стрелки», города пронумерованы по
часовой стрелке.

АЛГОРИТМ: Введем два дополнительных массива
On, Ag: array[1..m] of record wh, qh:integer; end; .
On[i] означает, где следует заправляться (wh) и стоимость заправки (qh)
жителям i-го города, если движение разрешено только по часовой стрелке. В
этом случае жители города i имеют две альтернативы: либо заправляться у
себя в городе, либо ехать по часовой стрелке. Во втором случае жителям
города i надо заправляться там же, где и жителям города i+1, или в первом,
если i=m. Итак, On[i]=min{Z[i],C[i]+On[i+1].qh}. Откуда известно значение
On[i+1].qh? Необходимо найти город j с минимальной стоимостью заправки -
On[j]:=(j,Z[j]). После этого можно последовательно вычислять значения On[j-
1], On[j-2], ..., On[j+1]. Аналогичные действия необходимо выполнить при
формировании массива Ag[i], после этого для жителей каждого города i
следует выбрать лучший из On[i].qh и Ag[i].qh вариант заправки.

Задача 6. РЕСТОРАН.
В ресторане собираются N посетителей. Посетитель с номером i
приходит во время Ti и имеет благосостояние Pi. Входная дверь ресторана
имеет К состояний открытости. Состояние открытости двери может
изменяться на одну единицу за одну единицу времени, т.е. она или
открывается на единицу, или закрывается на единицу, или остается в
текущем состоянии. В начальный момент времени дверь закрыта (состояние
0.) Посетитель с номером i входит в ресторан только в том случае, если дверь
специально открыта для него, т.е когда состояние открытости двери
совпадает с его степенью полноты Si, в противном случае посетитель
обижается и уходит безвозвратно. Ресторан работает Т часов. Цель швейцара
- собрать посетителей с максимальным благосостоянием, правильно
открывая и закрывая двери.
Входные данные:
В первой строке значения N, K, T, разделенные пробелами.
63
(1<=N<=100, 1<=K<=100, 0<=T<=30000). Во второй строке находятся
времена прихода посетителей Т1, Т2...Tn, разделенные пробелами
(0<=Ti<=T, для всех i=1,2...N). В третьей строке находятся величины
благосостояния посетителей P1, P2...Pn, разделенные пробелами
(0<=Pi<=300) , в четвертой строке находятся значения степени полноты
посетителей Si, разделенные пробелами. Все исходные данные - целые числа.
Выходные данные:
Число - максимальное суммарное благосостояние посетителей , либо 0
(если нельзя добиться прихода в ресторан ни одного посетителя.) Написать
программу и тесты.


6.7 «ЖАДНЫЕ» АЛГОРИТМЫ
«Жадный» алгоритм - метод оптимизации, приспособленный к
задачам, в которых процесс принятия решений может быть разбит на
отдельные этапы (шаги).
Метод состоит в том, что оптимальное решение строится постепенно,
шаг за шагом. На каждом шаге оптимизируется решение ТОЛЬКО
ТЕКУЩЕГО ШАГА, не рассматривая оптимальность конечного результата,
иначе говоря, последовательность локально оптимальных (жадных) выборов
дает глобально оптимальное решение.


6.7.1 УСЛОВИЯ ПРИМЕНЕНИЯ «ЖАДНЫХ» АЛГОРИТМОВ
Если последовательность локально оптимальных (жадных) выборов
(подзадач) дает глобально оптимальное решение (т.е на каждом шаге данный
алгоритм берет «самый жирный кусок», а затем пытается сделать наилучший
выбор среди оставшихся, каковы бы они не были).

ЗАДАЧИ
Задача 1. ЗАДАЧА О ВОРЕ.
Вор, пробравшись в хранилище банка, обнаружил N мешков золотого
песка. Но стоимость мешков была разной из-за проб золота в них (С[I]). Вес
мешков тоже различался (M[I]). Поднять вор может только Х кг (перед
операцией его от волнения стукнул радикулит). Помогите бедному вору
выбрать наиболее драгоценный груз.
АЛГОРИТМ:
Необходимо набить рюкзак по MAX стоимости груза. Произведем
сортировку стоимости содержимого мешков (С[I]/M[I]) по убыванию. Будем
заполнять рюкзак вора, складывая мешки с золотом, начиная с самого
дорогого мешка, пока есть место в рюкзаке. Если в конце заполнения мешок
полностью не входит в рюкзак, золото следует отсыпать ровно столько,
чтобы заполнить рюкзак до конца.
Задача 2. ЗАДАЧА О ВЫБОРЕ ЗАЯВОК.
64
Пусть даны N заявок на проведение занятий в одной и той же
аудитории. Два разных занятия не могут перекрываться по времени. В
каждой заявке указано начало и конец занятия (S[i] и F[i] для i- той заявки).
Разные заявки могут пересекаться, и тогда можно удовлетворить только одну
из них. Конец одной заявки может совпадать с началом другой. Выбрать
такие заявки, чтобы их количество было МAX.
АЛГОРИТМ:
Упорядочим заявки в порядке возрастания времени окончания. На
каждом шаге будем делать такой выбор заявки, чтобы оставшееся свободное
время было максимальным.
Задача 3.ЗАДАЧА О ВОСХОЖДЕНИИ.
N альпинистов решили покорить вершину Эльбруса. Каждый I – тый
альпинист может нести S[i] кг припасов и съедает за один день C[i]
припасов. Какое максимальное число альпинистов дойдет до вершины и
вернется обратно, если альпинисты могут делиться припасами на привале, а

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign