КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Продвижение очереди производится операторамиIf Bego <> Nil then Begin Kon:=Bego; Bego:=Bego^.Next; Dispose(Bego); End; В качестве примера рассмотрим следующую задачу, связанную с ведением очереди. Дан список клиентов, желающих посетить банк в некоторый период времени. Для каждого клиента заданы имя, момент прихода и время обслуживания. В банке работает один кассир. Если в момент прихода очередного клиента кассир занят, клиент становится в очередь. Обслуженный кассиром клиент покидает банк. Требуется промоделировать работу кассира, то есть последовательно выдать информацию о приходах и уходах клиентов из банка с указанием состояния очереди. Необходимо также найти среднее время обслуживания клиента. Будем считать, что список упорядочен по возрастанию моментов прихода клиентов. При работе банка встречаются два класса событий: · приход клиента и постановка его в очередь (если кассир не занят, то очередь будет состоять только из пришедшего клиента); · продвижение очереди. Пусть имеется N клиентов. Обозначим через M[I] момент прихода, а через T[I] время обслуживания i-го клиента. Рассмотрим алгоритм решения задачи. 1. S:=0 - общее время обслуживания клиентов. 2. R:=M[1]+T[1] - момент разгрузки очереди. 3. I:=1 - начало цикла по клиентам до I=N. 4. P:=M[I], где P - момент прихода очередного клиента. 5. Пока P>=R (приход клиента после ближайшей разгрузки очереди) и очередь не пуста, выполнить: 1) S:=S+R-M[J], где J-номер клиента из начала очереди; 2) разгрузить очередь, убрав клиента из ее начала, и выдать сообщение на экран; 3) если очередь не пуста, то R:=R+T[J+1] - следующий момент разгрузки очереди. 6. Если очередь пуста, то R:=M[I]+T[I]. 7. Постановка в очередь I-го клиента и выдача сообщения. 8. I:=I+1; если I<=N, то переход к шагу 4. 9. Если очередь не пуста, то ее полная разгрузка с выдачей сообщений. 10. H:=S/N - среднее время обслуживания клиента. 11. Выдача H; конец. Приведем текст программы. Очередь реализована с помощью массива. Начало очереди соответствует первому элементу массива, а конец - последнему элементу. Program Ochered; Uses Crt; Type klient=record Name: string; { имя } M: integer; { момент прихода } T: integer { время обслуживания } end; Var H: real; { среднее время обслуживания клиента } I, J, R, S, P, N, L: integer; Och: array [1..100] of integer; { очередь } Bego, Endo: integer; { начало и конец очереди } Kli: array [1..100] of Klient; { список клиентов по возрастанию моментов прихода } Procedure Razgruz; Begin J:=Och[Bego]; { номер клиента из начала очереди } S:=S+R-Kli[J].M; { учет времени его нахождения в очереди } Write('Время: ', R, ', обслужен клиент ', Kli[J].Name); Endo:=Endo-1; { разгрузка очереди } For L:=Bego to Endo do Och[L]:=Och[L+1]; if Endo>0 then { очередь не пуста } begin WriteLn(', следующий клиент ', Kli[J+1].Name); R:=R+Kli[J+1].T { следующий момент разгрузки } end else WriteLn(', очередь пуста !'); ReadLn { пауза } End; Begin ClrScr; { очистка экрана } For N:=1 to 100 do begin with Kli[N] do Begin WriteLn('Введите информацию об очередном клиенте:'); Write('Введите имя (к-признак конца): '); ReadLn(Name); if Name='к' then Break; { конец списка клиентов } Write('Укажите момент прихода: '); ReadLn(M); Write('Сообщите время обслуживания: '); ReadLn(T) end end; WriteLn; WriteLn(' ПРОТОКОЛ РАБОТА БАНКА'); N:=N-1; { число клиентов } S:=0; { для общего времени обслуживания } Bego:=1; { начало очереди всегда здесь ! } Endo:=0; { критерий пустой очереди } R:= Kli[1].M+ Kli[1].T; { ближайший момент разгрузки очереди } For I:=1 to N do begin P:=Kli[I].M; { момент прихода следующего клиента } While (P>=R) and (Endo>0) do Razgruz; { очередь сокращается до прихода следующего клиента } { и больше не разгружается } if Endo=0 then R:=Kli[I].M+Kli[I].T; { следующий момент разгрузки } Endo:=Endo+1; { постановка в очередь i-го клиента } Och[Endo]:=I; Write('Время: ', Kli[I].M,', прибыл клиент ', Kli[I].Name); if Endo=1 then WriteLn(', очереди нет, ура !') else WriteLn(', встал в очередь за клиентом ', Kli[Och[Endo-1]].Name); ReadLn { пауза } end; While Endo>0 do Razgruz; H:=S/N; WriteLn('Обслуживание закончено, перерыв на обед !'); WriteLn('Среднее время обслуживания клиента: ',h:5:2); ReadLn { пауза } End. В этом примере продвижение очереди связано со сдвигом всей заполненной части массива, что может быть трудоемкой операцией при большой размерности и частом повторении. Для преодоления этого недостатка используют кольцевые списки, в которых последний элемент связан с первым. Это позволяет из любого элемента списка добраться до нужного элемента. Кольцевые списки легче восстанавливаются в случае разрушения какой-либо связи. Рассмотрим кольцевую очередь, заданную массивом Och с N элементами. Начало и конец очереди заданы индексами Bego и Endo. Следующим после N-го элемента будем считать первый элемент массива. Тогда постановка в очередь выполняется командами Endo:= Endo mod N + 1; Och[Endo]:=NewElement; а продвижение производит оператор Bego:=Bego mod N + 1. Индексы Bego и Endo как бы двигаются по кольцу вдогонку друг за другом. Необходимым условием для постановки в очередь в этом случае является NumElement < N, где NumElement – число элементов в очереди, а при продвижении очереди должно быть NumElement >0. Буфер клавиатуры в MS DOS организован в виде кольцевой очереди.
|