Задание 22 · Параллельные процессы Python
SilverTests.ru · Учебник Решение без сдвигов (типы 1, 3, 4, 5)
Задание 22. Решение на Python
Типы 1, 3, 4, 5 — без сдвигов процессов
0Подготовка файла
Библиотека openpyxl на ЕГЭ может быть не установлена. Откройте файл 22.ods в LibreOffice Calc, затем Файл → Сохранить как → CSV (разделитель — запятая). Получится обычный текстовый файл 22.csv:
1ID,Длительность,Зависимости
21,3,0
32,5,0
43,2,1
54,4,1;2
65,3,3
76,6,0
87,2,4;5
98,3,6;7
Перед написанием кода откройте CSV в текстовом редакторе: какой разделитель столбцов — запятая или точка с запятой? Через что записаны зависимости? Есть ли строка заголовка?
1Чтение данных
Этот блок общий для всех типов. Читаем файл и сохраняем каждый процесс в словарь procs: ключ — ID, значение — длительность и список зависимостей.
1procs = {}
2
3with open('22.csv') as f:
4 lines = f.read().strip().split('\n')
5
6for line in lines[1:]: # пропускаем заголовок
7 parts = line.split(',')
8 pid = int(parts[0])
9 dur = int(parts[1])
10 dep_str = parts[2].strip()
11
12 if dep_str == '0' or dep_str == '':
13 deps = []
14 else:
15 deps = [int(x) for x in dep_str.split(';')]
16
17 procs[pid] = {'dur': dur, 'deps': deps}
стр 4 — read() читает файл целиком, strip() убирает лишние пробелы, split('\n') разбивает на строки.
стр 6 — lines[1:] пропускает заголовок. Если заголовка нет — уберите [1:].
стр 12–13 — зависимость '0' или пустая строка означает независимый процесс.
стр 15 — строка "1;2" разбивается на список [1, 2].
2Расчёт Старта и Конца
Тоже общий блок. Если процесс не зависит ни от кого, он стартует в 1-ю мс и заканчивается через dur мс. Если зависит — ждём завершения всех зависимостей и стартуем на следующую миллисекунду. Функция рекурсивная: чтобы узнать конец P7, нужен конец P4 и P5, а для P4 — конец P1 и P2. Цепочка раскручивается автоматически.
1end = {}
2start = {}
3
4def calc(pid):
5 if pid in end: # мемоизация
6 return end[pid]
7 p = procs[pid]
8 if not p['deps']: # независимый
9 start[pid] = 1
10 end[pid] = p['dur']
11 else:
12 mx = max(calc(d) for d in p['deps'])
13 start[pid] = mx + 1
14 end[pid] = mx + p['dur']
15 return end[pid]
16
17for pid in procs:
18 calc(pid)
стр 5–6 — мемоизация: если уже считали — сразу возвращаем, не пересчитываем.
стр 12 — max(calc(d) for d in deps) рекурсивно находит конец каждой зависимости и берёт максимум.
стр 13 — mx + 1: стартуем на следующую мс после завершения последней зависимости.
Результат для нашего примера:
| ID |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
| start |
1 |
1 |
4 |
6 |
6 |
1 |
10 |
12 |
| end |
3 |
5 |
5 |
9 |
8 |
6 |
11 |
14 |
Теперь словари start и end заполнены. Каждый тип решается за 1–3 строки кода.
3Тип 1 — Минимальное время завершения
Вопрос: через сколько миллисекунд завершатся все процессы?
Все закончатся, когда закончится последний — ищем максимум среди значений end:
1print(max(end.values())) # → 14
end.values() даёт [3, 5, 5, 9, 8, 6, 11, 14], максимум — 14 (процесс P8). Это длина критического пути P2→P4→P7→P8 = 5+4+2+3.
4Тип 3 — Завершились к моменту T
Вопрос: сколько процессов завершились к моменту T = 8?
Процесс завершился, если end ≤ T. Считаем такие:
1T = 8
2print(sum(1 for e in end.values() if e <= T)) # → 5
Проверяем: P1(3≤8)✓, P2(5)✓, P3(5)✓, P5(8)✓, P6(6)✓ — итого 5. Обратите внимание: P5 с концом ровно 8 тоже считается, потому что условие — «≤», а не «<».
Развёрнутый вариант без генератора
1count = 0
2for pid in end:
3 if end[pid] <= T:
4 count += 1
5print(count)
5Тип 4 — Работают, но не завершились
Вопрос: найдите сумму ID процессов, которые запустились, но ещё не завершились к T = 7.
Два условия одновременно: start[pid] ≤ T (уже начался) и end[pid] > T (ещё не закончил):
1T = 7
2total = 0
3for pid in procs:
4 if start[pid] <= T and end[pid] > T:
5 total += pid # суммируем ID, не +1!
6print(total) # → 9
Проверяем: P4 (старт 6 ≤ 7, конец 9 > 7) — да; P5 (старт 6 ≤ 7, конец 8 > 7) — да. Сумма ID: 4 + 5 = 9.
Частая ошибка — суммируют количество (2), а не ID (9). Внимательно читайте вопрос: «сумма ID» и «количество» — разные вещи. Если спрашивают количество — замените total += pid на total += 1.
6Тип 5 — Последний запуск
Вопрос: определите ID процесса, начинающего выполнение позже всех.
Ищем процесс с максимальным start:
1print(max(start, key=lambda pid: start[pid])) # → 8
Конструкция max(start, key=...) перебирает ключи словаря и выбирает тот, чьё значение максимально. Здесь P8 со стартом 12.
Развёрнутый вариант без lambda
1best_pid = None
2best_start = -1
3for pid in start:
4 if start[pid] > best_start:
5 best_start = start[pid]
6 best_pid = pid
7print(best_pid)
Стандартный паттерн «поиск максимума»: храним лучший результат и обновляем при нахождении большего.
7Полный шаблон
Весь код в одном блоке. Выдаёт ответы на все типы сразу (кроме Типа 2). Менять нужно только строки 3 и 4 — имя файла и значение T:
1# ═══ ПОЛНЫЙ ШАБЛОН ЗАДАНИЕ 22 ═══
2
3FILE = '22.csv' # ← имя файла
4T = 8 # ← подставьте T
5
6procs = {}
7with open(FILE) as f:
8 lines = f.read().strip().split('\n')
9for line in lines[1:]:
10 parts = line.split(',')
11 pid = int(parts[0])
12 dur = int(parts[1])
13 ds = parts[2].strip()
14 deps = [] if ds in ('0','') else [int(x) for x in ds.split(';')]
15 procs[pid] = {'dur': dur, 'deps': deps}
16
17end = {}
18start = {}
19def calc(pid):
20 if pid in end: return end[pid]
21 p = procs[pid]
22 if not p['deps']:
23 start[pid] = 1
24 end[pid] = p['dur']
25 else:
26 mx = max(calc(d) for d in p['deps'])
27 start[pid] = mx + 1
28 end[pid] = mx + p['dur']
29 return end[pid]
30for pid in procs: calc(pid)
31
32print('Тип 1:', max(end.values()))
33print('Тип 3:', sum(1 for e in end.values() if e <= T))
34print('Тип 4:', sum(p for p in procs if start[p]<=T and end[p]>T))
35print('Тип 5:', max(start, key=lambda p: start[p]))
Тип 1: 14
Тип 3: 5
Тип 4: 4
Тип 5: 8
Краткая справка
Тип 1 (мин. время) — max(end.values())
Тип 3 (завершились к T) — sum(1 for e in end.values() if e <= T)
Тип 4 (работают к T) — sum(pid for pid in procs if start[pid]<=T and end[pid]>T)
Тип 5 (послед. запуск) — max(start, key=lambda p: start[p])
Памятка к экзамену
Откройте CSV глазами — проверьте разделитель столбцов (, или ; или табуляция). Убедитесь, что lines[1:] пропускает именно заголовок, а не данные. Зависимости в разных файлах записаны по-разному: через ;, пробел или запятую — адаптируйте split(). Если зависимость равна 0 — процесс независимый; в некоторых файлах вместо нуля пустая строка.