Задание №22 ЕГЭ Информатика с ответом и решением
Ответ: 17
Условие
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы — время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Типовой пример организации данных в файле:
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A |
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 1; 2 |
| 4 | 7 | 3 |
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Выполните задания, используя данные из файла ниже:
Подсказки — как подойти к решению
- Задача сводится к поиску критического пути: время окончания процесса = его собственное время выполнения + максимум времён окончания всех процессов, от которых он зависит. Простое сложение всех времён не подходит — параллельные ветви выполняются одновременно.
- Данные лежат в файле таблицей: идентификатор процесса, время выполнения в миллисекундах и через «;» идентификаторы процессов, от которых он зависит (0 — процесс независимый). Аккуратнее читать файл программой, а не глазами, и обрабатывать процессы от независимых к зависимым.
- Заполняй столбец «время окончания»: у независимых процессов он равен их длительности, у остальных — длительности плюс максимум по уже посчитанным предшественникам. Ответ — максимум по всей таблице, а не время процесса из последней строки и не сумма длительностей.
Решение
| F | G |
|---|---|
| Время, мс | ID процесса |
1 |
2 |
| 3 | 2 |
|---|---|
| 4 | 1 |
| 5 | 3 |
6 |
| 7 | 9 |
|---|---|
| 8 | 10 |
9 |
10 |
| 11 | 5 |
|---|---|
| 12 | 4 |
| 13 | 11 |
| 14 | 6, 12 |
| 15 | 7 |
16 |
| 17 | 8 |
|---|
Используя данные из файла, составим таблицу, на какой мс может закончится каждый из процессов. Процессы с ID «1», «2», «9» и «10» независимые, поэтому их выполнение закончится на 4, 3, 7 и 8 мс соответственно. Процесс с ID «3» может выполняться только после завершения процессов с ID «1» и «2», поэтому он может завершиться на 5 мс. Процессы с ID «4» и «5» зависят от процесса с ID «3», значит, они завершатся через 5 + 7 = 12 мс и 5 + 6 = 11 мс соответственно. Процесс с ID «6» зависит от процесса с ID «5», значит, он завершится через 11 + 3 = 14 мс. Процесс с ID «7» зависит от процессов с ID «4» и «6», следовательно, поскольку процесс с ID «6» завершится только на 14 мс, процесс с ID «7» выполнится на 14 + 1 = 15 мс. Процесс с ID «8» зависит от процесса с ID «7», значит, он выполнится на 15 + 2 = 17 мс. Процесс с ID «11» зависит от процесса с ID «9», поэтому он выполнится на 7 + 6 = 13 мс. Процесс с ID «12» зависит от процесса с ID «10», поэтому он выполнится на 8 + 6 = 14 мс.
Таким образом, вся совокупность процессов завершится на 17 мс.
Ответ: 17.
Приведём другое решение на языке Python.
import sys
d = {'0': 0}
for elem in sys.stdin:
num, dur, *subs = elem.replace(';', ' ').split()
d[num] = max([d[i] for i in subs]) + int(dur)
print(max(d.values()))
Запустив программу вводим данные из таблицы построчно, цифры в строках разделяем пробелом. Закончив ввод всех строк таблицы необходимо нажать CTRL + D.
Примечание.
Заметим, что данный способ работает для любой таблицы, но уместен только для таблиц с небольшим количеством строк (процессов).
Приведём другое решение Никитиной Елизаветы на языке Python.
f = open("22.txt").read().split("\n")
m = {}
for i in f:
s = i.split()
if s[2] == '0':
m[s[0]] = int(s[1])
else:
w = s[2].split(";")
sp = []
for j in w:
j = j.replace(" ", "")
sp.append(int(m[j]))
m[s[0]] = int(s[1]) + max(sp)
print(max(m.values()))
Примечание.
Данные из таблицы необходимо сохранить в текстовый документ.
Типичные ошибки
- Это время завершения процесса, от которого зависит последний процесс цепочки: сам последний зависимый процесс не учтён. Ответом должно быть самое позднее время окончания среди всех процессов.
- Это время завершения одной из параллельных ветвей, а не максимум по всем процессам. Ветви выполняются одновременно, поэтому ориентируйся на самое позднее окончание, а не на первую посчитанную цепочку.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №22 по информатике