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

22. Вычислительные процессы: В файле содержится информация о совокупности N вычислительных…

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

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

Для приведённой таблицы процесс $3$ начинается на $8$-й мс, заканчивается на $9$-й мс.

Используя данные из файла, составим таблицу, на какой мс может закончиться каждый из процессов. Независимые процессы $1$, $2$ и $12$ завершатся на $3$, $4$ и $6$ мс соответственно.

Процесс $3$ зависит от $2$ и завершится на $4+1=5$ мс, процесс $19$ тоже зависит от $2$ и завершится на $6$ мс. Процесс $5$ зависит от $12$ и завершится на $6+1=7$ мс. Процесс $6$ зависит от $3$ и $12$: позже заканчивается $12$ (на $6$ мс), значит $6$ завершится на $6+6=12$ мс.

От процесса $6$ дальше зависит целая ветка. Процессы $11$, $17$ и $24$ завершаются на $14$ мс, процесс $20$ — на $15$ мс. Процесс $18$ зависит от $11$ и $2$, стартует после $14$ мс и завершается на $14+6=20$ мс. Процесс $9$ зависит от $3$, $17$ и $12$ и завершается на $14+6=20$ мс.

Процесс $8$ зависит от $20$, $6$ и $18$: позже заканчивается $18$ (на $20$ мс), значит $8$ завершится на $20+3=23$ мс. От него зависит $23$, который завершится на $23+2=25$ мс. Процесс $4$ зависит от $5$ и $18$ и завершится на $20+6=26$ мс.

Процесс $13$ зависит от $4$ и $23$: позже заканчивается $4$ (на $26$ мс), поэтому $13$ завершится на $26+3=29$ мс. И наконец, процесс $21$ зависит от $6$, $1$ и $13$, стартует после $29$ мс и завершается на $29+5=34$ мс. Для сравнения, вторая длинная ветка идёт через процесс $7$ ($28$ мс) и $16$ ($32$ мс) — она короче.

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

Время, мсID процесса
$3$$1$
$4$$2$
$5$$3$
$6$$12$, $19$
$7$$5$
$8$$25$
$12$$6$
$14$$11$, $17$, $24$
$15$$20$
$19$$15$
$20$$9$, $18$
$23$$8$
$25$$10$, $22$, $23$
$26$$4$
$28$$7$, $14$
$29$$13$
$32$$16$
$34$$21$

Приведём другое решение на языке Python.

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-16.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]).replace(' ', '').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))   # 34

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

Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

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