Информатика решение задачи формата егэ
В файле содержится информация о совокупности восьми вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс В зависит от процесса А, если для выполнения процесса В необходимы результаты выполнения процесса А.
Файл
В этом случае процессы могут выполняться только последовательно.
В файле информация о процессах представлена в виде таблицы. В первой колонке таблицы указан идентификатор процесса (ID), во второй колонке таблицы — время его выполнения в миллисекундах, в третьей колонке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Время выполнения одного из процессов неизвестно и для данного процесса в соответствующей колонке обозначено как t.
Определите максимально возможное целочисленное t (время выполнения процесса), при котором выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно и один процесс может сменять другой завершившийся мгновенно, завершилось не более чем за 20 мс.
Лови
Для решения этой задачи ЕГЭ по информатике сначала нужно проанализировать зависимости между процессами. Согласно условиям, если процесс В зависит от процесса А, то они должны выполняться последовательно. Если процессы независимы, они могут выполняться параллельно.
Исходя из данной таблицы:
Процесс 1 зависит от 0 (независимый), значит, он выполняется первым.
Процесс 2 зависит от 1, значит, он выполняется после завершения 1.
Процесс 3 зависит от 2, значит, он выполняется после завершения 2.
Процесс 4 зависит от 1 и 3, значит, он выполняется после завершения 1 и 3.
Процесс 5 зависит от 2 и 4, значит, он выполняется после завершения 2 и 4.
Процесс 6 зависит от 1, 3 и 5, значит, он выполняется после завершения 1, 3 и 5.
Процесс 7 зависит от 2 и 6, значит, он выполняется после завершения 2 и 6.
Процесс 8 зависит от 4 и 7, значит, он выполняется после завершения 4 и 7.
Таким образом, порядок выполнения процессов: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
Учитывая, что независимые процессы могут выполняться параллельно, максимально возможное время выполнения t для процесса, при котором все процессы завершились не более чем за 20 миллисекунд, можно определить как сумму минимальных времен выполнения всех процессов:
t = 5 + 3 + 4 + (6 + 2) + (1 + 2) + (2 + 3) + (4 + 1) = 5 + 3 + 4 + 8 + 3 + 5 + 5 = 33 миллисекунд.
Соответственно, максимально возможное целочисленное t, при котором выполнение всей совокупности процессов завершилось не более чем за 20 миллисекунд, равно 33.
.
