Задание №6525.
Построение математической модели. ЕГЭ по информатике
Файл, необходимый для выполнения задания: ссылка для скачивания.В файле содержится информация о совокупности
N вычислительных процессов, которые могут выполняться параллельно или последовательно.
Приостановка выполнения процесса не допускается. Будем говорить, что процесс
B зависит от процесса
A, если для выполнения процесса
B необходимы результаты выполнения процесса
A. В этом случае процессы
A и
B могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение 0.
Определите максимальное количество процессов, которые могут быть завершены за первые 17 мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с 1.
Типовой пример организации данных в файле.
Типовой пример организации данных во входном файле приводится только в демонстрационном варианте ЕГЭ!| ID процесса B | Время выполнения
процесса B (мс) | ID процесса(-ов) A |
| 1 | 3 | 0 |
| 2 | 4 | 1 |
| 3 | 2 | 2; 4 |
| 4 | 5 | 0 |
| 5 | 8 | 1; 4 |
Для приведённой таблицы найдём количество процессов, которые могут быть завершены за первые 7 мс. Это 3 процесса (за это время завершатся процессы 1, 2 и 4).
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
Пояснение:
Приведем решение данного задания на языке программирования Python. Для этого необходимо скопировать содержимое Excel файла в текстовый документ с расширением .txt.
import collections
def read_input(filename="input.txt"):
processes = {}
with open(filename, "r", encoding="utf-8") as f:
for line in f:
line = line.strip()
if not line or line.startswith("ID"): # пропустим заголовок
continue
parts = line.split("\t")
pid = int(parts[0])
duration = int(parts[1])
deps = parts[2].strip()
if deps == "0":
deps = []
else:
deps = list(map(int, deps.split(";")))
processes[pid] = (duration, deps)
return processes
def compute_finish_times(processes):
finish_times = {}
def dfs(pid):
if pid in finish_times:
return finish_times[pid]
duration, deps = processes[pid]
if not deps: # нет зависимостей
start_time = 0
else:
start_time = max(dfs(d) for d in deps)
finish_times[pid] = start_time + duration
return finish_times[pid]
for pid in processes:
dfs(pid)
return finish_times
processes = read_input("input.txt")
finish_times = compute_finish_times(processes)
# считаем, сколько процессов завершились за первые 17 мс
count = sum(1 for t in finish_times.values() if t <= 17)
print("Максимальное количество завершённых процессов за первые 17 мс:", count) |
Таким образом,
12 — максимальное количество процессов, которые могут быть завершены за первые 17 мс.
Показать ответ
12
Источник: Демонстрационный вариант ЕГЭ — 2026
Сообщить об ошибке
Тест с похожими заданиями