Динамические структуры. Динамические структуры (1). Динамические структуры (списки, очереди, деревья)

Название	Динамические структуры (списки, очереди, деревья)
Анкор	Динамические структуры
Дата	27.04.2022
Размер	24.11 Kb.
Формат файла
Имя файла	Динамические структуры (1).docx
Тип	Документы #499513

Динамические структуры (списки, очереди, деревья)

Операции над массивами должны быть реализованы со сложностью О(1)

Вдоль реки расположено N участков. При открытии рынка земли с этими участками возможны следующие операции:

- объединение (когда два, рядом расположенных участка объединятся в один);

- деление (когда участок делится на два рядом расположенных).

Определить состояние участков после заданного потока операций.

Поток операций задается массивом следующего формата:

P= {On₁, On₂, …, Rn₁, Rn₂, …},

где О – операция объединения i-ого участка с (i+1) -ым участком;

R - операция разделения i-ого участка на два участка;

(операции объединения и разделения чередуются в случайном порядке)

На упаковочный станок подаются коробки разного формата, которые отличаются скоростью обработки (T_i). Если станок занят, то коробка сбрасывается в накопитель. Определить состояние линии через время T₀ при заданном потоке поступления коробок на линию.

Поток поступления задается массивом следующего формата:

P={T₁,t₁, T₂,t₂, … T_n,t_n},

где T_i, t_i - соответственно время поступления коробки и время ее обработки.

На конвейерной линии, детали обрабатываются последовательно на N станках. Время обработки на каждом станке задано в виде массива:

O={O₁,, O₂, … O_n},

Поток поступления деталей задается массивом следующего формата:

T={T₁,, T₂, … T_n},

где T_i, - соответственно время поступления i-ой детали.

Если при передаче детали с j-ого станка на (j+1)-ый станок (j+1)-ый станок оказывается занятым, то деталь сбрасывается в накопитель (j+1)-ого станка. Определить состояние линии через время T₀ при заданном потоке поступления коробок на линию.

Интенсивность потока телефонных звонков в агентство по заказу железнодорожных билетов, имеющему один телефон, составляет P вызовов/час. Продолжительность оформления заказа на билет равна t минут. Агентство работало T₀ часов. По запросу с клавиатуры определить среднее время ожидания в очереди за период времени T₁..T₂ (T₂0) .

На вокзале имеется M билетных касс. При покупке билетов возможны два варианта: покупается билет в пункт, с которым есть прямое сообщение, и билет с пересадкой в пункт, с которым нет прямого сообщения. Время оформления первого варианта билета вдвое меньше времени оформления второго варианта. Количество пассажиров, покупающих билеты по обоим вариантам примерно одинаково. Время оформления билета по первому варианту составляет O минут. Поток пассажиров задан в виде массива следующего формата:

P={T₁,v₁, T₂,v₂, … T_n,v_n},

где T_i, v_i - соответственно время подхода пассажира к кассе и вариант покупки.

Определить размер очереди через время Т₀.

Международный переговорный пункт имеет M телефонных аппаратов. В среднем за сутки поступает P заявок на переговоры. Поток клиентов равномерно распределен во времени. Средняя длительность переговоров составляет t мин. Определить размер очереди через время Т₀. (Например: m=4, p=320, t=5 мин, Т₀=6 часов).

Контроль готовой продукции фирмы осуществляют M контролеров. Если изделие поступает на контроль, когда все контролеры заняты, то оно сбрасывается в накопитель. Изделия поступают со скоростью V изд./ч. и их поток равномерно распределен во времени. Среднее время на проверку одного изделия - t мин. Определить количество изделий в накопителе через время Т₀. (V=20, t=7, T₀=3 часа)

Справочный зал имеет M терминалов. Поток пользователей равномерно распределен во времени. Среднее количество пользователей равно P чел/сутки. Время работы одного пользователя на терминале составляет в среднем t минут. Определить, среднее время ожидания. (Например, m=5, p=140 чел/сутки, t=40 мин, Т₀=24 часа).

Система скорой помощи располагает M-ым количеством врачебных бригад. Поток вызовов распределен равномерно по времени и составляет P вызовов в час. Время обслуживания каждого вызова составляет t. Определить состояние очереди при заданных m, p и t через время Т₀. (Например, m=15, p=12, t=75 мин, Т₀=24 часа).

Центральный процессор ПК в любой момент времени выполняет либо приоритетную программу, либо фоновую программу, либо находится в состоянии ожидания. Данные о программах, необходимых для исполнения, хранятся в массиве следующего формата:

P=(P_i, V_i, T_i),

где P_i V_i, T_i. – являются соответственно приоритетом, временем исполнения и временем поступления на обработку i-ой программы.

Определить среднее время загрузки процессора за период работы ПК, равный T₀.

Интернет-сервис предоставляет услуги доступа к БД. Средняя скорость поступлений заявок на доступ к информации составляет t заявок/мин. Время работы каждого пользователя с БД представляет собой случайную величину и составляет от 5 до 30 мин. Система может одновременно обслуживать до 5 пользователей. Если количество пользователей больше 5, то последний пользователь становится в очередь.

Сервис начинает работать в момент времени T₀.Определить время ожидания доступа к БД очередного клиента через время T_n после начала работы сервиса.

Морской порт имеет M причалов. В него на загрузку/выгрузку заходят суда. Если нет свободных причалов, то судно становится в очередь на загрузку. Поток судов задан массивом следующего формата:

P=(V_i, T_i),

где V_i, T_i. – являются соответственно временем загрузки/выгрузки и временем подхода i-ого судна к порту. Определить состояние очереди судов через время T₀.

Аэропорт имеет M взлетно-посадочных полос. На взлет/посадку формируется очередь из самолетов. Если нет свободных полос, то самолет становится в очередь. Параметры самолетов заданы массивом следующего формата:

P=(T_i, V_i),

где T_i. V_i – время готовности и взлета i-ого самолета. Определить состояние очереди через время T₀.

На ремонтном предприятии (например, по ремонту бытовой техники) работает M мастеров. На предприятие поступают изделия для ремонта. Если все мастера заняты, то изделие становится в очередь. Изделия поступают со скоростью V изд./сутки. и их поток равномерно распределен во времени. Среднее время на ремонт одного изделия - t_i мин. Определить количество изделий в очереди через время Т₀. (m=5, V=10, t=2-16 часов, T₀=30 дней).

На предприятии по интернет-доставке продуктов работает M курьеров. На предприятие поступают заявки на поставку. Если все курьеры заняты, то заявка становится в очередь. Заявки поступают со скоростью V заявок/час и их поток равномерно распределен во времени. Среднее время на выполнение одной заявки - t_i мин. Определить состояние очереди через время Т₀. (m=5, V=10, t=20-40 мин, T₀=1 сутки).

На предприятии по предоставлению транспортных услуг имеется M автомобилей. На предприятие поступают заявки на обслуживание. Если все автомобили заняты, то заявка становится в очередь. Заявки поступают со скоростью V заявок/сутки и их поток равномерно распределен во времени. Среднее время на выполнение одной заявки - t_i часов. Определить состояние очереди через время Т₀. (m=5, V=10, t=2-8 часов, T₀=30 суток).

В салоне красоты работает M мастеров. В салон на обслуживание записываются клиенты. Если все мастера заняты, то клиент ставится в очередь. Клиенты записываются со скоростью V чел/час и их поток равномерно распределен во времени. Среднее время на обслуживание одного клиента - t_i минут. Определить состояние очереди через время Т₀. (m=5, V=10, t=30-120 мин, T₀=24 часа).