Задача к ЕГЭ по информатике на тему «Поиск отрезка времени выполнения 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 | ------------------------------------------------------------------

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

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.

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

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

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

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

=ВПР(C2;$A$1:$H$9;8;0)

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

=H2-B2+1

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

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

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

=СУММ(J2:J8)

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

=ЕСЛИ(J9=1;I10+1;0)

=МАКС(10:10)

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

Ответ: 23