Перейти к содержимому


Очередь


Сообщений в теме: 5

#1 yanush

    Пользователь

  • Пользователи
  • PipPip
  • 21 сообщений

Отправлено 22 декабря 2011 - 08:23

Очередь - это упорядочный набор связанных элементов, которые добавляются с одного конца и удаляются с другого конца.

Начала очереди будем называть UN а конец UK. Массив очереди обозначим Q

Операции с очередью:

1. Добавление элемента (допустим элемента x)

if UK<=Nmax then begin
 						Q[UK]:=x;
 						UK:=UK+1;
end;


2.Удаление элемента

if UN <> UK then begin
l:=Q[UN]
UN:=UN+1;
end;


3.Создать пустую очередь

UN:=1; UK:=1;

Задача №1

Вводится массив n на m элементов. Массив это лист бумаги. В этом массиве ( из этого листа ) вырезали k клеток. На сколько частей распадётся лист?

Итак ниже представлен рисунок задачи. Всего клеток вырезали 8. Т.е. k=8. Клетки которые вырезали помечены на рисунке как -1.

Изображение

Итак Решение задачи. Делаем дополнительную рамку из -1 для нашего листа. Ниже представлен рисунок.

Изображение


Итак теперь представим, что лист бумаги, представленный на последнем рисунке, это город. Город в котором все друг друга знают. на ша задача распростаранить сплетню. Ну например как бабушки возле подъезда сидят и сплетничают. Одна бабушка скажет другой что например её сосед начинающий панк-рокер. И вот он долбит и долбит в свою гитару и ей, бедной, не даёт спать. И вот она говорит об этом другой старушки, та следующей. И вот получается целая сеть бабушек которые передают новость своим знакомым. Для чего это всё написал? Потому-что следующий алгоритм который мы сделаем будет как раз основываться на распространении сплетни. Итак мы ищем соседние клетки клеток с -1. И заполняем их сначала 1. Напомню, что соседними будем считать клетки которые находятся от клетки с -1 вверху внизу справа и слева. Делаем это с помощью очереди. Скрин ниже.

Изображение


Итак соседние клетки -1 обычными 1 мы заполнили. Замечу, что заполнение мы начинали с левого верхнего угла. Дальше делаем ещё 2 очереди и заполняем таблицу 2 и 3. Если всё сделали правильно то получится вот такая таблица

Изображение

Ну вот с таблицами вроде всё. А теперь собственно сам алгоритм который выполняет нашу задачу.

var a:array [0..101,0..1001] of longint;
Q:array [1..2,1..10000] of longint;
i,j,n,m,UN,UK,i1,j1,SK,k,x1,y1:longint;
Procedure Sosed(x,y:longint);
begin
if a[x,y]=0 then begin
                  Q[1,UK]:=x; Q[2,UK]:=y;
                  UK:=UK+1; a[x,y]:=SK;
				end;
end;
Begin
 
readln(n,m);
readln(k);
for i := 1 to k do
  begin
  readln(i1, j1);
  a[i1, j1] := -1;
  end;
{for i := 1 to n do
  for j := 1 to m do
    read(a[i,j]);}
for i:=0 to m + 1 do begin
   				a[0,i]:=-1;
   				a[n+1,i]:=-1;
   				end;
for i:=1 to n do begin
                  A[i, 0]:=-1;
                  a[i, m+1]:=-1;
				end;
SK:=0;
for i:=1 to n do
for j:=1 to m do
  if a[i,j]=0 then begin UN:=1; UK:=1; SK:=SK+1; Q[1,UK]:=i; Q[2,UK]:=j; UK:=UK+1; a[i,j]:=SK;
   while UN<>UK do begin
   				i1:=Q[1,UN];
   				j1:=Q[2,UN];
   				UN:=UN+1;
   				Sosed(i1-1,j1);
   				Sosed(i1+1,j1);
   				Sosed(i1,j1-1);
   				Sosed(i1,j1+1);
   				end;
   				end;
for i:=1 to n do begin
for j:=1 to m do  write(a[i,j]:3);
writeln;
end;
writeln(sk);
end.

Ну вот и всё.

Другие задачи с очередью вы можете увидеть по ссылкам ниже

1. Кратчайший маршрут
2.Форма и вода

#2 dark.wizard

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений

Отправлено 22 декабря 2011 - 10:33

имхо, очередь все же структура данных, а не граф)

#3 yanush

    Пользователь

  • Пользователи
  • PipPip
  • 21 сообщений

Отправлено 22 декабря 2011 - 10:49

но к примеру поиск пути и поиск в ширину построен на очереди

#4 MakTraDe

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений

Отправлено 23 декабря 2011 - 09:34

Я лично согласен с Никитой, очередь на мой взгляд очень трудно назвать графом, я бы сказал нельзя, а поиск в ширину, к слову, - это всего лишь МЕТОД ОБХОДА ГРАФА.

#5 Andrew

    Пользователь

  • Пользователи
  • PipPip
  • 13 сообщений

Отправлено 14 ноября 2012 - 15:42

Киньте эту тему в структуры данных. Очередь используется не только для графов
redcode.do.am ( сайт пока пуст )

#6 Санек

    Продвинутый пользователь

  • Администраторы
  • 37 сообщений
  • ГородВитебск

Отправлено 14 ноября 2012 - 17:29

Просмотр сообщенияAndrew (14 ноября 2012 - 15:42) писал:

Киньте эту тему в структуры данных. Очередь используется не только для графов


Сделано





Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных