Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

22. Вычислительные процессы: Например, для приведённой таблицы это 13 мс (процесс 5 может…

Задание #298197
Решено верно
Решено неверно
Сообщить о проблеме

В файле содержится информация о совокупности $N$ вычислительных процессов, которые могут выполняться параллельно или последовательно. Приостановка выполнения процесса не допускается. Будем говорить, что процесс $B$ зависит от процесса $A$, если для выполнения процесса $B$ необходимы результаты выполнения процесса $A$. В этом случае процессы $A$ и $B$ могут выполняться только последовательно.

Информация о процессах представлена в файле в виде таблицы. В первом столбце таблицы указан идентификатор процесса (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс независимый, то в таблице указано значение $0$.

Типовой пример организации данных в файле:

ID процесса $B$Время выполнения процесса $B$ (мс)ID процесса(-ов) $A$
$1$$3$$0$
$2$$4$$1$
$3$$2$$2$; $4$
$4$$5$$0$
$5$$8$$1$; $4$

Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно. Например, для приведённой таблицы это $13$ мс (процесс $5$ может выполниться только после окончания процесса $4$, их общая продолжительность $5 + 8 = 13$ мс).

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $106$, $107$ и $112$ завершатся на $3$, $5$ и $6$ мс соответственно. Процесс $105$ зависит от $107$, значит завершится на $5+1=6$ мс. Процесс $102$ тоже зависит от $107$ и завершится на $5+5=10$ мс, а процесс $119$ зависит от $112$ и $106$: позже заканчивается $112$ (на $6$ мс), поэтому $119$ завершится на $6+4=10$ мс.

Дальше процесс $101$ зависит от $102$ и $119$, оба заканчиваются на $10$ мс, значит $101$ завершится на $10+1=11$ мс. Процесс $109$ зависит от $112$ и завершится на $6+5=11$ мс, процесс $118$ зависит от $101$ и $109$ — оба на $11$ мс, поэтому $118$ завершится на $11+3=14$ мс. Процесс $110$ зависит от $118$ и $119$, позже заканчивается $118$, значит $110$ завершится на $14+6=20$ мс. Процесс $111$ зависит от $110$ и завершится на $20+4=24$ мс, а процесс $117$ зависит от $111$, следовательно, выполнится на $24+5=29$ мс.

Таким образом, вся совокупность процессов завершится на $29$ мс.

Время, мсID процесса
$3$$106$
$5$$107$
$6$$105$, $112$
$10$$102$, $119$
$11$$101$, $104$, $109$
$12$$123$
$13$$124$
$14$$103$, $116$, $118$
$15$$113$, $121$
$16$$108$
$17$$125$
$19$$114$
$20$$110$, $115$, $122$
$23$$120$
$24$$111$
$29$$117$

Приведём другое решение на языке 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.

Примечание. Способ работает при условии, что процессы в файле идут в таком порядке, что каждый встречается уже после всех тех, от которых он зависит. Если порядок произвольный, надёжнее читать файл целиком и считать время завершения рекурсией с кэшированием:

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-01.ods', engine='odf', header=None, skiprows=1)

t, dep = {}, {}
for _, row in df.iterrows():
    pid = int(row[0])
    t[pid] = int(row[1])
    s = str(row[2]).strip()
    dep[pid] = [] if s == '0' else [int(x) for x in s.split(';')]

@lru_cache(None)
def finish(p):                        # момент завершения процесса p
    return t[p] + max([finish(d) for d in dep[p]], default=0)

print(max(finish(p) for p in t))   # 29
Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение