LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

каждая из которых имеет от 1 до 4 дверей в соседние комнаты, путник долго
блуждал по нему, пока не нашёл клад. Во время поиска он составил описание
своего маршрута, обозначая каждый переход из комнаты в комнату буквами:
С(север), В(восток), Ю(юг), З(запад).
Опишите алгоритм, определяющий по заданной записи самый
короткий путь назад.
Решение:
Подходящей структурой данных для представления информации о
лабиринте является квадратная таблица L, каждая клетка которой
соответствует комнате. Размеры таблицы можно установить заведомо
большими лабиринта, для чего достаточно подсчитать количество букв в
исходной записи переходов. Значение L(i,j) следует устанавливать так,
чтобы по нему можно было определить возможные переходы в соседние
комнаты, например, в виде четырёхразрядного двоичного числа, где первый
разряд равен 1, если из комнаты (i,j) возможен переход на север, второй
разряд соответствует переходу на юг, третий - на запад, а четвёртый - на
восток. Вход в лабиринт находится в некоторой клетке (i0,j0).
Алгоритм проведём в два этапа.
На первом этапе занесём в нашу таблицу всю информацию о
лабиринте, которая содержится в записи переходов путника. На втором этапе
найдём кратчайший путь, ведущий из конечной клетки маршрута в
начальную. Для этого применим так называемый волновой алгоритм,
состоящий из прямого и обратного ходов. Во время прямого хода
74
просматриваются комнаты, достижимые от входа за 1 шаг, за 2 шага и т.д.
Во время обратного хода строится кротчайший путь, ведущий назад.
Первый этап
Установим 0 во все значения L(i,j).
Установим текущее положение в лабиринте i:=i0, j:=j0.
НЦ пока есть символы в записи
читаем очередной символ S
ЕСЛИ S="C", то
устанавливаем 1 в первый разряд L(i,j),
устанавливаем 1 во второй разряд L(i+1, j) (считаем, что переход
черездверь возможен в обе стороны),
меняем текущее положение i:=i+1;
ЕСЛИ S="Ю", то
устанавливаем 1 во второй разряд L(i,j),
устанавливаем 1 в первый разряд L(i-1,j),
меняем текущее положение i:=i-1;
ЕСЛИ S="3", то
устанавливаем 1 в третий разряд L(i,j),
устанавливаем 1 во четвёртый разряд L(i,j+1),
меняем текущее положение j:=j+1;
ЕСЛИ S="В", то
устанавливаем 1 в четвёртый разряд L(i,j),
устанавливаем 1 во третий разряд L(i,j-1),
меняем текущее положение j:=j-1;
КЦ
Запоминаем ik:=i и jk:=j - координаты комнаты с кладом.
Второй этап
Прямой ход волнового алгоритма .
заведём числовую таблицу V того же размера, что и L. Значением каждого
элемента V(i,j) таблицы будет минимально возможное количество шагов,
которые ведут из комнаты (i0,j0) в комнату (i,j) в лабиринте. Сначала
заполним таблицу V числами -1.
Установим номер очередного шага h:=0.
Присвоим элементу V(i0,j0) значение h.
НЦ ПОКА V(ik,jk)= -1
Просматриваем клетки таблицы (i,j), в которых V(i,j)=h. По информации,
содержащейся в L, заносим число h+1 во все клетки таблицы V,
соответствующие комнатам смежным комнате (i,j), которые ещё содержат -1
(т.е ещё не проходились). После просмотра увеличиваем h на 1.
КЦ
Обратный ход волнового алгоритма
Установим текущее положение i:=ik, j:=jk.
Установим h:=(i,j).
НЦ пока h<>0
75
Используя информацию таблицы L, находим комнату, смежную комнате (i,j),
в которой записано число h-1, и устанавливаем текущее положение,
соответствующее найденной комнате. В зависимости от того, в какую
сторону эта комната находится от предыдущей, выводим один из символов :
"С", "Ю", "З" или "В".
Уменьшаем h на 1.
КЦ

Программная реализация:
type
ROOM=record
N,S,W,E:integer
end;
var
s:string; i0,j0,ik,jk,i,j,index,h:integer; l:array[1..50,1..50] of ROOM;
v:array[1..50,1..50] of integer;
begin
ReadLn(s);
i0:=25; j0:=25; i:=i0; j:=j0;
for index:=1 to ord(s[0]) do
begin
if s[index]=’C’ then
begin
l[i,j].N:=1; l[i+1,j].S:=1; i:=i+1;
end;
if s[index]=’Ю’ then
begin
l[i,j].S:=1;
l[i-1,j].N:=1;
i:=i-1;
end;
if s[index]='З' then
begin
l[i,j].W:=1;
l[i,j-1].E:=1;
j:=j-1;
end;
if s[index]=’В’ then
begin
l[i,j].E:=1; l[i,j+1].W:=1; j:=j+1;
end;
end;
ik:=i; jk:=j;
for i:=1 to 50 do
for j:=1 to 50 do
76
v[i,j]:=-1;
h:=0;
v[i0,j0]:=h;
while v[ik,jk]=-1 do
begin
for i:=1 to 50 do
for j:=1 to 50 do
if v[i,j]=h then
begin
if (l[i,j].N=1) and (v[i+1,j]=-1) then
v[i+1,j]:=h+1;
if (l[i,j].S=1) and (v[i-1,j]=-1) then
v[i-1,j]:=h+1;
if (l[i,j].W=1) and (v[i,j-1]=-1) then
v[i,j-1]:=h+1;
if (l[i,j].E=1) and (v[i,j+1]=-1) then
v[i,j+1]:=h+1;
end;
h:=h+1;
end;
i:=ik; j:=jk; h:=v[i,j];
while v[i,j]<>0 do
begin
if (i+1<=50) and (v[i+1,j]=h-1) and (l[i,j].N=1)
then
begin
Write('С');
i:=i+1;
end
else
if (i-1>0) and (v[i-1,j]=h-1) and (l[i,j].S=1)
then
begin
Write(’Ю’);
i:=i-1;
end else if (j-1>0) and(v[i,j-1]=h-1) and
(l[i,j].W=1)
then
begin Write('З'); j:=j-1;
end
else
if (j+1<=50) and(v[i,j+1]=h-1) and (l[i,j].E=1)
then
begin
Write('В');
77
j:=j+1;
end;
h:=h-1;
end;
Write(' ');
end.

ВАРИАНТ 2
(с использованием динамической памяти):

Procedure Wave (num_begin, num_end: integer);
{номера вершин начала и конца пути}

Var
k : integer; {номер «фронта волны»}
num : integer; {номер текущей вершины}
flag : boolean; {признак необходимости строить очередной
фронт}
beg_qu, end_qu, elem_qu : list; {начало, конец элемента очереди}
Procedure Add (num : integer; var end_qu: list );
{добавление элемента к очереди}
Var
elem_qu: list;
begin
end_qu^.num:=num; {поместили элемент в конец очереди}
new(elem_qu); {выделили память под следующий элемент}
end_qu^.next:=elem_qu; {присоединили новый элемент}
end_qu:elem_qu
end;
Procedure Extract (var num : integer; var begin_qu : list);
{извлечь элемент из списка}
var
elem_qu: list;
begin
num:=beg_qu^.num; {считали первый элемент очереди}
elem_qu:=beg_qu; {запомнили ссылку на первый элемент для
последующего уничтожения}
beg_qu:=beg_qu^.next; {переносим указатель начала очереди на второй
элемент}
Dispose (elem_qu); {освобождаем память, уничтожив первый элемент}
end;
begin
new (elem_qu); {инициализация очереди и размещение в ней первого
элемента}
beg_qu:=elem_qu; {очередь пока пуста}
78
end_qu:=elem_qu;
Graf [num begin].num:= 1; {начальный этап}
Add (num_begin, end_qu); {поместили начало пути в очередь}
Flag:=true; {нужно строить фронт}
While flag and (not goal) do {строим очередной фронт}
begin
Extract (num, beg_qu); {берём значение очередного элемента очереди}
k:= Graf [num].num; {число шагов до извлечённого элемента – 1}
{просмотреть соседей, поместить очередной фронт и добавить
помеченные элементы в очередь}
ref:=Graf[num].next;
repeat
a:=ref^.num;
if a<>0 then begin
{обработка очередного соседа
if Graf [a].num=0
{пометить вершину следующим фронтом}
then begin
Graf[a].num := k+1;
Add(a, end_qu)
End;
ref:=ref^.next
{переходим к следующему соседу}
end;
until a=0;
if Graf[num_end].num<>0
then goal:= true {дошли до цели}
else
if beg_qu = end_qu then flag false {очередь пуста}
end;
end.

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РЕАЛИЗАЦИИ
УЧАЩИМИСЯ
Задача 1. ПУТЬ.
Найти кратчайшее расстояние между двумя вершинами в графе.
Найти все возможные пути между этими двумя вершинами в графе
непеpесекающиеся по
a) pебpам
b) веpшинам.
Задача 2.
Лабиринт задается матрицей смежности N*N, где C(i,j)=1, если узел i
связан узлом j посредством дороги. Часть узлов назначается входами, часть
79
- выходами. Входы и выходы задаются последовательностями узлов
X(1),..,X(p) и Y(1),..,Y(k) соответственно.
Найти максимальное число людей, которых можно провести от входов
до выходов таким образом, чтобы:
a) их пути не пересекались по дорогам, но могли пересекаться по
узлам;
b) их пути не пересекались по узлам;
Задача 3.
N шестеренок пpонумеpованы от 1 до N (N<= 10). Заданы M (0<=
<=M<=45) соединений паp шестеpенoк в виде (i,j), 1<=i<j<=N (шестеpня с
номеpом i находится в зацеплении с шестеpней j). Можно ли повеpнуть
шестеpню с номеpом 1?
Если да, то найти количество шестеpен, пpишедших в движение.
Если нет, то тpебуется убpать минимальное число шестеpен так, чтобы
в оставшейся системе пpи вpащении шестеpни 1 во вpащение пpишло бы
максимальное число шестеpен. Указать номеpа убpанных шестеpен ( если
такой набоp не один, то любой из них ) и количество шестеpен, пpишедших в
движение.
Задача 4.
Имеется N прямоугольных конвертов и N прямоугольных открыток
различных размеров. Можно ли разложить все открытки по конвертам, чтобы
в каждом конверте было по одной открытке. Замечание. Открытки нельзя
складывать, сгибать и т.п., но можно помещать в конверт под углом.
Например, открытка с размерами сторон 5:1 помещается в конверты с
размерами 5:1, 6:3, 4.3:4.3, но не входит в конверты с размерами 4:1, 10:0.5,
4.2:4.2.
Задача 5.
Составить программу для нахождения произвольного разбиения 20
студентов на 2 команды, численность которых отличается не более чем в 2
раза, если известно, что в любой команде должны быть студенты,
обязательно знакомые друг с другом. Круг знакомств задается матрицей
(20,20) с элементами


1,если i знаком с j
A(ij)= 0,иначе

Задача 6.
Имеется N человек и прямоугольная таблица А[1:N,1:N];элемент A[i,j]
равен 1, если человек i знаком с человеком j, А[i,j]=А[j,i]. Можно ли разбить
людей на 2 группы, чтобы в каждой группе были только незнакомые люди?
80
Задача 7.
На олимпиаду прибыло N человек. Некоторые из них знакомы между
собой. Можно ли опосредованно перезнакомить их всех между собой?
(Незнакомые люди могут познакомиться только через общего
знакомого).
Задача 8.
Пусть группа состоит из N человек. В ней каждый имеет (N/2) друзей и
не больше K врагов. У одного из них есть книга, которую все хотели бы
прочитать и потом обсудить с некоторыми из остальных.
Написать программу, которая:
• Находит способ передачи книги таким образом, чтобы она
побывала у каждого в точности один раз, переходя только от друга к другу и
наконец возвратилась к своему владельцу.
• Разбивает людей на S групп, где будет обсуждаться книга, таким
образом, чтобы вместе с каждым человеком в ту же самую группу вошло не
более P его врагов.
Примечание: предполагается, что S*P>=K.
Задача 9.
В заданном графе необходимо определить, существует ли цикл,
проходящий по каждому ребру графа ровно один раз.
Задача 10.
Имеется N городов. Для каждой пары городов (I,J) можно построить
дорогу, соединяющую эти два города и не заходящие в другие города.
Стоимость такой дороги A(I,J). Вне городов дороги не пересекаются.
Написать алгоритм для нахождения самой дешевой системы дорог,
позволяющей попасть из любого города в любой другой. Результаты задавать
таблицей B[1:N,1:N], где B[I,J]=1 тогда и только тогда, когда дорогу,
соединяющую города I и J, следует строить.
Задача 11.
В картинной галерее каждый сторож работает в течение некоторого
непрерывного отрезка времени. Расписанием стражи называется множество
пар [Т1(i), Т2(i)] - моментов начала и конца дежурства i-го сторожа из
интервала [0,EndTime].
Для заданного расписания стражи требуется:
a) проверить, в любой ли момент в галерее находится не менее двух
сторожей. Если условие (а) не выполнено, то:
b) перечислить все интервалы времени с недостаточной охраной
(менее 2 сторожей).
c) добавить наименьшее число сторожей с заданной, одинаковой для
всех длительностью дежурства, чтобы получить правильное расписание (т.е.
удовлетворяющее условию (а)).
81
d) проверить, можно ли обойтись без добавления новых сторожей,
если разрешается сдвигать времена дежурства каждого из сторожей с
сохранением длительности дежурства.
e) если это возможно, то составить расписание с наименьшим числом
сдвигов.
Задача 12.
Вводится N - количество домов и К - количество дорог. Дома
пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел -
двумя номерами домов - концов дороги и длиной дороги. В каждом доме
живет по одному человеку. Найти точку - место встречи всех людей, от
которой суммарное расстояние до всех домов будет минимальным.
Если точка лежит на доpоге, то указать номера домов – концов этой
доpоги и расстояние от первого из этих домов. Если точка совпадает с домом,
то указать номер этого дома.
Примечание: длины дорог - положительные целые числа.
Задача 13.
N колец сцеплены между собой (задана матрица A(n*n), A(i,j)=1в
случае, если кольца i и j сцеплены друг с другом и A(i,j)=0 иначе). Удалить
минимальное количество колец так, чтобы получилась цепочка.
Задача 14.
Янка положил на стол N выпуклых K-гранников и N различных типов
наклеек по K штук каждая. Ночью кто-то наклеил наклейки на грани, по
одной на грань. Помогите Янке расставить многогранники так, чтобы
наклейка каждого типа была видна pовно K-1 раз.
Задача 15.
Имеется N точек и M проводков. Проводком можно соединить
некоторую пару различных точек, причем пара может быть соединена не
более чем одним проводком. Все проводки должны быть использованы.
Пусть Di - количество проводков, которые будут соединены с точкой с
номером i, i=1, ..., N.
Необходимо соединить N точек с помощью M проводков таким
образом, чтобы сумма S=D1*D1 + D2*D2 + ... + Dn*Dn была максимальной.
Вывести величины Di в неубывающем порядке и. по требованию
(priznak=1), список соединений.

ВВОД:
<Введите N:> N (N<=100)
<Введите M:> M (M<=1000)
<PRIZNAK=> PRIZNAK
ВЫВОД:
<Результирующая конфигурация:> Di в неубывающем порядке.
<Сумма S> S
<Список соединений>
82
<Точку 1 соединить с> список точек
.....
<Точку N соединить с> список точек
Задача 16.
Задано N городов c номерами от 1 до N и сеть из M дорог с
односторонним движением между ними. Каждая дорога задается тройкой (i,
j, k), где i - номер города, в котором дорога начинается, j - номер города, в
котором дорога заканчивается, а k - ее длина (число k - натуральное). Дороги
друг с другом могут пересекаться только в концевых городах.
Все пути между двумя указанными городами A и B можно
упорядочить в список по неубыванию их длин (если есть несколько путей
одинаковой длины, то выбираем один из них). Необходимо найти один из
путей, который может быть вторым в списке.
Вывести его длину L и города, через которые он проходит.

ВВОД:
<Количество городов N:> N
<Количество дорог M:> M
<Начало, конец и длина дороги 1:> i1, j1, k1
......
<Начало, конец и длина дороги M:> iM, jM, kM

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign