Задание №22 ЕГЭ Информатика с ответом и решением
Ответ: 20
Условие
В файле содержится информация о совокупности 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 |
В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 — через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов равно 5 + 7 = 12 мс.
Выполните задания, используя данные из файла ниже:
Подсказки — как подойти к решению
- Разбери таблицу на ветки: независимые процессы стартуют сразу, а каждый зависимый ждёт завершения всех, кто указан в третьем столбце. Итоговое время считай по самой долгой ветке.
- Проверь, что не путаешь столбцы: второй — время работы процесса в миллисекундах, третий — идентификаторы процессов, от которых он зависит, а не наоборот.
Решение
Отсортируем данные в таблице так, чтобы все независимые процессы оказались в начале таблицы и любой процесс был расположен после всех процессов, от которых он зависит. Также в таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
| A | B | C | D |
|---|---|---|---|
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A | |
| 1 | 4 | 0 | 4 |
| 2 | 5 | 0 | 5 |
| 3 | 2 | 0 | 2 |
| 4 | 5 | 0 | 5 |
| 5 | 7 | 4 | |
| 6 | 2 | 3 | |
| 7 | 3 | 5 | |
| 8 | 1 | 4;5 | |
| 9 | 4 | 0 | 4 |
| 10 | 5 | 3 | |
| 11 | 1 | 6;7 | |
| 12 | 7 | 3;8 | |
| 13 | 3 | 2;4 | |
| 14 | 2 | 1;2 | |
| 15 | 4 | 9;11 |
Далее рассчитаем время выполнения оставшихся процессов:
f(5) = 7 + f(4) = 7 + 5 = 12;
f(6) = 2 + f(3) = 2 + 2 = 4;
f(7) = 3 + f(5) = 3 + 12 = 15;
f(8) = 1 + max(f(4), f(5)) = 1 + 12 = 13;
f(10) = 5 + f(3) = 5 + 2 = 7;
f(11) = 1 + max(f(6), f(7)) = 1 + 15 = 16;
f(12) = 7 + max(f(3), f(8)) = 7 + 13 = 20;
f(13) = 3 + max(f(2), f(4)) = 3 + 5 = 8;
f(14) = 2 + max(f(1), f(2)) = 2 + 5 = 7;
f(15) = 4 + max(f(9), f(11)) = 4 + 16 = 20.
| A | B | C | D |
|---|---|---|---|
| ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A | |
| 1 | 4 | 0 | 4 |
| 2 | 5 | 0 | 5 |
| 3 | 2 | 0 | 2 |
| 4 | 5 | 0 | 5 |
| 5 | 7 | 4 | 12 |
| 6 | 2 | 3 | 4 |
| 7 | 3 | 5 | 15 |
| 8 | 1 | 4;5 | 13 |
| 9 | 4 | 0 | 4 |
| 10 | 5 | 3 | 7 |
| 11 | 1 | 6;7 | 16 |
| 12 | 7 | 3;8 | 20 |
| 13 | 3 | 2;4 | 8 |
| 14 | 2 | 1;2 | 7 |
| 15 | 4 | 9;11 | 20 |
Ответ: 20.
Приведём решение на языке Python.
def f(d):
if d[2] == [0]:
return d[1]
else:
maxx = 0
for i in d[2]:
if maxx < f(index[i - 1]):
maxx = f(index[i - 1])
return maxx + d[1]
from csv import reader
with open("22_11.csv") as F:
s = reader(F, delimiter=';', quotechar='"')
next(s)
index = []
for i in s:
index.append([int(i[0]), int(i[1]), list(map(int, str(i[2]).split(';')))])
for i in range(len(index)):
print(i + 1, f(index[i]))
Примечание.
Для считывания информации из файла необходимо конвертировать его из xlsx в csv.
Приведём решение Владимира Артамонова на языке Python.
with open('22.txt') as file:
processes = {"0": 0}
for line in file.readlines():
num, time, related = line.split()
processes[num] = max([processes[i] for i in related.split(";")]) + int(time)
print(max(processes.values()))
Примечание.
Для считывания информации из файла необходимо конвертировать его из xlsx в txt.
Ответ: 20
· Помощь
Илья Пащук 14.10.2022 20:22
Это решение, которое на Python и использует openpyxl, не совсем корректно в том смысле, что на ЕГЭ доступа к openpyxl может и не оказаться. А вот экспорт в csv будет доступен всегда, так что лучше решать с ним, хоть так и длиннее.
Служба поддержки
Дельное замечание, поменяли. Спасибо!
Типичные ошибки
- Возможно, потеряна одна из зависимостей: если у процесса их две, ждать нужно более позднюю. Проверь ветки, идущие от середины таблицы.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №22 по информатике