[Amicus Plato]

Вчера на федеральном тестировании по информатике среди прочего попались интересные задачи. До сегодняшнего дня я считала их задачами "на сообразительность". Очень удивлялась, тому, что они оказались в тестах по информатике. Там вроде и сообразительности особой не требовалось....
Сегодня знающие люди просветили меня, что это задачи из теории массового обслуживания.
Как оказалось, я ее должна была преподать в рамках информатики )))
Решала я их (и прорешала штук двадцать похожих) именно как решала бы задачи для младшей школы "на смекалку" — графическим способом.
И теперь вот думаю: наверное, для решения таких задач существуют специальные методы?

А задачи таковы (делятся они на две группы: в одной надо найти время, в другой количество людей; выпишу по одной из каждой группы):

1. Врач принимает каждого пациента 15 минут. К нему пришли 4 пациента с интервалом в 5 минут. Какое максимальное время сидения пациентов в очереди?

2. Врач принимает каждого пациента 15 минут. На прием пришли 5 пациентов с интервалом в 5 минут. Какое максимальное количество человек окажется в очереди?

(Сами числа беру с потолка, поэтому ответов не знаю сама)))
Решая, получила море удовольствия (хоть и очень краткосрочного)))!
Чего и вам желаю )))

Comments

[ili]

первая задача - 60 минут) а если он пришел одновременно с первым, то 75? Нет?

вторая - 4 человека

[Amicus Plato]

ili

Не всё так просто!
Они же приходят не все вместе!
Второй пришел через 5 минут после первого, а третий через пять минут после второго, и т.д. )))
Так что, например, пока пятый из второй задачи прибудет в очередь, первый уже и забудет, что был у врача...

[Заболекарь]

Странно сформулировано условие, на мой взгляд. Попробую ответить на всё, что могло подразумеваться.

Первая задача: всего врач будет принимать пациентов на протяжении шестидесяти минут (60=15*4). Если одного человека, ожидающего приёма перед дверью, считать за очередь — очередь просуществует сорок минут (40=15*4-5-15), если считать за очередь только двух и более человек — двадцать минут (20=15*4-10-30). Дольше всех придётся ждать четвёртому пациенту: он будет сидеть перед дверью целых полчаса (30=15*4-15-15)

Вторая задача: всего в очереди побывает четыре пациента (т.е. все, кроме первого), но не больше трёх пациентов будет стоять в очереди одновременно. Три пациента в очереди будут на протяжении десяти минут: когда пятый уже пришёл (двадцать минут после прихода первого, 20=5*4), а третьего ещё не приняли (тридцать минут после прихода первого, 30=15*2).

[Заболекарь]

Разумеется, это если считать, что, когда первый пациент пришёл, больница уже открылась) Иначе задача усложняется)

[Amicus Plato]

Заболекарь
больница уже открылась )))
(наверное)
По крайней мере, об этом никто не говорил... )))

А так... Я всё это откладывала на "оси времени".
С тем же результатом ))))
Просто интересно, есть ли общие формулы для этого дела.
(Но интересно не настолько, чтобы пускаться во все тяжкие и искать, а потом еще вникать...))))

[Заболекарь]

Общие формулы? Сейчас.

[Заболекарь]

Пусть время, которое врач тратит на одного пациента, обозначается у нас буквой t, а интервал между появлением пациентов буквой d. Время сидения в очереди обозначим буквой s (от немецкого Schlange, очередь. Мне так удобнее). Номер пациента обозначим буквой n.

Если t≤d, то s=0. Никакой очереди нет: пациент пришёл, его тут же принимают.
Если t>d, то для первого пациента s=t*0-d*0, для второго s=t*1-d*1, для третьего s=t*2-d*2 и так далее.
То есть s=(t-d)*(n-1);

Для первой задачи этого хватает: d и t не меняются, значит, максимальное время сидения в очереди будет у пациента с максимальным n, то есть у самого последнего. s=(15-5)*(4-1)=10*3=30;

Теперь вторая.

[Amicus Plato]

Заболекарь
мда... всё гениальное просто... )))

[Amicus Plato]

Вот мое решение первой задачи.
(Вторая решается аналогично, если графически):

Первый, красный, зашел на отметке "0" и вышел через 15 минут. Второй пришел через пять минут (от времени 0), зашел в 15, вышел в 30. И т.д.
"Пришел" — кружок, "вышел от врача" — кольцо того же цвета.
Сразу видно, кто где сколько пробыл, и каково количество ожидающих в данный момент.

[Заболекарь]

Количество человек в очереди обозначим буквой p. Количество пациентов (не только сидящих в очереди, но и ещё не пришедших, и уже принимающихся, и уже ушедших) обозначим буквой m.
Время обозначим буквой x. Вообще-то я бы его охотно обозначил через t, но t уже занято.
Речь, конечно, и здесь идёт о t>d, потому что иначе никакой очереди нет и p=0.

Если считать, что пациенты исправно прибывают каждые d минут, а их количество ничем не ограничено, то формула выглядит так:
p=x/d-x/t;
В данном случае результаты от обоих делений должны округляться вниз. По идее, вместо / должно стоять что-то другое. Или какие-то особенные скобочки вокруг. Я не помню, как это пишется. Кто вспомнит — пусть скажет, чтобы модератор поправил и убрал это пояснение.
Однако для решения задачи это бесполезно, потому что пациентов всего пять.
Поэтому формулу надо усложнить: p=x/d-x/t остаётся, но результаты делений теперь обрабатываются так: все результаты деления, которые больше m-1, округляются до m-1. Как это корректно пишется — понятия не имею. Надеюсь, мне расскажут, чтобы можно было исправить

Пример: пять пациентов, прибывают каждые пять минут, у врача проводят пятнадцать минут. На одиннадцатой минуте дела обстоят так: p=11/5-11/15=2-0=2; Два человека в очереди. На двадцатой минуте: p=20/5-20/15=4-1=3; Три человека в очереди.
Другой пример: всё то же самое, но пациентов не пять, а четыре. На одиннадцатой минуте p=11/5-11/15=2, ничего не изменилось. На двадцатой минуте 20/5-20/15=3-1=2; На одного человека в очереди меньше, потому что пятый пациент не пришёл.

[Trotil]

Такими задачками занимается теория СМО (систем массового облуживания)

В качестве параметров выступают такие данные, как интенсивность обслуживания, скорость входящего потока, кол-во людей, которых можно обслуживать одновременно...
Можно подсчитать среднюю длину очереди, среднее время обслуживания и т.д.

[Amicus Plato]

Заболекарь
Формулы просто замечательные!
А главное, действительно простые получились!
Целая часть числа обычно квадратными скобками обозначается: [х]

Trotil

Такими задачками занимается теория СМО (систем массового обслуживания)

Так ведь и я про то!
У меня как раз в посте про это и написано ))))

[Заболекарь]

Тогда s=(t-d)*(n-1) для первой задачи, p=[x/d]-[x/t] для бесконечного числа пациентов и... Как это пишется для конечного числа пациентов?

[Amicus Plato]

Заболекарь
для конечного надо думать...
Для бесконечного это функция возрастающая, а для конечного (числа пациентов при неограниченном сверху времени) должна быть точка перегиба.
Там максимум должен быть где-то посерёдке. По-моему, одной формулой не обойтись...

[Заболекарь]

По сути как раз ничего сложного. Я тут подумал и решил написать так:

[x/d]≤m-1 AND [x/t]≤m-1 → p=[x/d]-[x/t]
[x/d]≥m-1 AND [x/t]≤m-1 → p=(m-1)-[x/t]
[x/d]≥m-1 AND [x/t]≥m-1 → p=0

Очень не уверен, что это корректная запись, но суть понятна.
[x/d]≤m-1 AND [x/t]≥m-1 мы не рассматриваем, потому что нас интересует только t>d.

[Amicus Plato]

Заболекарь
ага, очень похоже!