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

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

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

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

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

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

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

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

=H2-B2+1

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

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

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

=СУММ(J2:J15)

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

=ЕСЛИ(J16=3;I17+1;0)

=МАКС(17:17)

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

Ответ: 15