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

В файле содержится информация о совокупности 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 | ------------------------------------------------------------------

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

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

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

=B2+D2+G2

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

=ВПР(C2;A:F;6;0)

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

=F2-B2+1

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

=ЕСЛИ(И($E2<=H$1;$F2>=H$1);1;)

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

=СУММ(H2:H11)

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

=ЕСЛИ(H12=4;G13+1;0)

=МАКС(13:13)

Остается только сдвинуть необходимые процессы так, чтобы получился отрезок максимальной длины. Оптимальным вариантом будет сдвинуть процесс с номером 3 на 1 мс, с номером 4 на 6 мс. Таким образом получаем отрезок длины 12.

Ответ: 12