ilyachalov (ilyachalov) wrote,
ilyachalov
ilyachalov

Categories:

Разбор упражнения с лифтами

Я уже разбирал ошибку в примере многофайловой программы elev в 13-й главе учебника Лафоре.

Эта программа является симулятором работы множества лифтов в многоэтажном здании. Лифты откликаются на запросы пассажиров с различных этажей. Каждый лифт может вместить множество пассажиров, каждый из которых может, зайдя в лифт, нажать кнопку любого из этажей. Количество лифтов и этажей в здании задается константами в файле, предоставляемом застройщиком. Я взял значения констант, которые использовались в учебнике: 4 лифта в 20-этажном здании.

Кабина каждого лифта кроме того, что реагирует на запросы с этажей и нажатия кнопок этажей пассажирами, еще и анализирует положение других кабин. К примеру, на запрос с этажа не двинутся сразу все свободные кабины, а поедет только одна, ближайшая.

Но алгоритм работы кабин не идеален. В третьем упражнении-проекте к 13-главе (стр.638-639) приводится пример одного из недостатков алгоритма и предлагается его исправить.

После запуска программы кабины лифтов находятся на первом этаже:


Недостаток алгоритма работы кабин. Пассажиры сначала нажали кнопку «вниз» вызова кабины с 20-го этажа, а через некоторое время кнопку «вниз» вызова кабины с 10-го этажа.


Запросы с этажей «вниз» на картинке обозначены символом «▼» (закрашенный треугольник с вершиной вниз), расположенным между соответствующим номером этажа и первой слева кабиной лифта.

На рисунке видно, что первая кабина лифта (они нумеруются слева направо) двинулась вверх. По алгоритму в данном случае она движется к дальнему запросу на 20-м этаже. Вторая и следующие кабины проводят анализ: между ближайшим запросом с этажа (10-й этаж) и их текущим расположением (1-й этаж) уже есть кабина, движущаяся к запросу с этажа. Значит, следует оставаться на месте.

Только после того, как первая кабина пройдет 10-й этаж и продолжит движение к запросу на 20-м этаже, вторая кабина начнет движение к запросу на 10-м этаже.

Требуется исправить алгоритм так, чтобы вторая кабина начала движение к запросу на 10-м этаже раньше.

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

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

Тот же принцип должен соблюдаться в противоположном направлении. Например, если все лифты находятся на 20-м этаже, а запросы поступили с 1-го и 10-го этажей.

Файлы проекта: elev4.
Tags: Образование, Программирование
Subscribe

  • Вчера открыл беговой сезон

    Обычно начинаю с мая, но в этом году весна выдалась ранняя. Пробежал свою любимую десяточку неожиданно с первого раза. Обычно начинаю с 3-4…

  • Marcus Nimbler закрыл свой канал на YouTube

    Любопытный персонаж из Германии по имени Marcus Nimbler вел свой канал на «YouTube» с 25 февраля 2016 г. За это время у него накопилось 131 тыс.…

  • Сбыча мелких мечт

    В качестве эпиграфа: Но со временем я заметил, что для этого мира такое положение дел вполне естественно в любой области. Поначалу всегда есть две…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments