ЕГЭ–2026, информатика: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 22 № 55818 Добавить в вариант

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

Задание 22

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

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

Спрятать решение

Решение.

Заметим, что время выполнения всей совокупности процессов равно времени выполнения самого длинного процесса.

Посчитаем время выполнения процессов В, не зависящих от процессов А. Для этого введем в столбец D формулы для строк, в которых процесс А равен 0. Это процессы 1, 2, 9 и 10. В ячейку D2 введем =B2, в D3  — =B3, в D10  — =B10 и в D11  — =B11.

Посчитаем время выполнения процессов, зависящих от одного процесса А. Это процессы 4, 5, 6, 8, 11, 12 и 16. В ячейку D5 введем =B5+D4, где В5  — время процесса В, а D4  — время процесса, от которого зависит процесс В. В D6  — =B6+D4, в D7  — =B7+D6, в D9  — =B9+D8, в D12  — =B12+D10, в D13  — =B13+D11 и D17  — =B17+D16.

Посчитаем время выполнения процессов, зависящих от двух процессов А. Это процессы 3, 7, 14 и 15. В ячейку D4 введем =B4+МАКС(D2;D3), где В4  — время процесса В, а МАКС(D2;D3)  — максимальное время процессов, от которого зависит процесс В (выбираем максимальное, так как процессы могут идти параллельно). В D8  — =B8+МАКС(D5;D7), в D15  — =B15+МАКС(D4;D13) и в D16  — =B16+МАКС(D9;D14).

Посчитаем время выполнения процессов, зависящих от трех процессов А. Это процесс 13. В ячейку D14 введем =B14+МАКС(D8;D12;D13), где В14  — время процесса В, а МАКС(D8;D12;D13)  — максимальное время процессов, от которого зависит процесс В (выбираем максимальное, так как процессы могут идти параллельно).

Найдем максимальное время выполнения самого длинно процесса, введя формулу =МАКС(D2:D17), и получим время выполнения всех процессов  — 37.

Ответ: 37.

Приведём решение Евгения Джобса на языке Python.

# скопируем содержимое таблицы в файл

# и прочитаем его.

# Заменим точки с запятой на пробелы

file = open('22.txt').read().replace(';', ' ')

# преобразуем данные в список строк из чисел

nums = [[int(x) for x in s.split()]

for s in file.split('\n')]

# создадим словарь вида

# №процесса: (время выполнения, процессы)

pr = {c[0]:(c[1], c[2:]) for c in nums[:-1]}

# определим функцию, которая

# возвращает время работы процесса

# n - номер процесса

def f(n):

# если номер равен 0, то время выполнения 0

# (начало всех процессов)

if n == 0: return 0

# иначе максимальное время выполнения

# для всех предыдущиъ процессов

# плюс время выполнения процесса n

return max(f(x)

for x in pr[n][1]) + pr[n][0]

# находим максимальное значение

print(max(f(x) for x in pr))

Примечание.

Из файла следует удалить строку заголовков и разбить ячейки с перечнями процессов, от которых зависит данный процесс, на отдельные ячейки с помощью мастера «Текст по столбцам». Файл следует сохранить в формате txt.

Приведём решение Михаила Глинского на языке Python.

f=open('22.txt')

res={'0':0}

for s in f:

n,t,*ff=s.split()

res[n]=max([res[x] for x in ff])+int(t)

print(max(res.values()))

Примечание.

Источник: ЕГЭ по информатике 06.04.2023. Досрочная волна

Спрятать решение · Помощь