Задача к ЕГЭ по информатике на тему «Поиск отрезка времени выполнения N процессов» №2

В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно.

Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы A и B могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.

Типовой пример организации данных в файле:

|--------------|--------------------------------|----------------| -ID-процесса B--Время-выполн-ени-я процесса B-(мс)-ID-процесса(ов)A- | 1 | 4 | 0 | |--------------|--------------------------------|----------------| |------2-------|---------------3----------------|-------0--------| -------3-----------------------1-----------------------1;2-------- | 4 | 7 | 3 | ------------------------------------------------------------------

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

Выделим столбец $C$ , перейдём во вкладку Данные, раздел «Текст по столбцам» и разделим наши данные, указав символом-разделителем точку с запятой. Столбец $G$ будет хранить данные о том в какую мс процесс начался, столбец $H$ – в какую мс закончился.

В ячейку $A1$ поставим значение 0. В ячейку $H2$ впишем формулу и растянем её вниз:

=B2+МАКС(E2:F2)+I2

В ячейку $E2$ впишем формулу и растянем её вправо до столбца $F$ , вниз до конца таблицы:

=ВПР(C2;$A$1:$H$9;8;ЛОЖЬ)

Таким образом мы нашли время, в которое каждый процесс завершается, относительно начала выполнения самого первого процесса. Для того чтобы найти время, в которое каждый процесс начинался относительно начала выполнения самого первого процесса в ячейку $G2$ запишем формулу и растянем ее вниз:

=H2-B2+1

Построим диаграмму. Для этого начиная с ячейки $I1$ заполним первую строку цифрами от 1 до 70. В ячейку $I2$ запишем формулу и растянем на весь диапазон:

=ЕСЛИ(И($G2<=J$1;$H2>=J$1);1;)

Таким образом диаграмма автоматически построилась и теперь, если в столбце сдвига указать какое-либо значение, то этот процесс и все зависящие от него процессы автоматически сдвинутся. Чтобы посчитать количество процессов, которые выполняются в каждую миллисекунду в ячейку $I14$ запишем формулу и растянем ее вправо:

=СУММ(J2:J13)

Для поиска отрезка максимальной длины в ячейку $I15$ запишем формулу и также растянем вправо и найдем максимальное значение по этому диапазону:

=ЕСЛИ(I14=3;H15+1;0)

=МАКС(15:15)

Остается только сдвинуть необходимые процессы так, чтобы получился отрезок максимальной длины. Оптимальным вариантом будет сдвинуть процесс с номером 7 на 14 мс, с номером 9 на 2 мс, с номером 10 на 6 мс и с номером 11 на 7 мс. Таким образом получаем отрезок длины 16.

Ответ: 16