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

22. Вычислительные процессы: Определите максимальное количество процессов, которые параллельно…

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

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

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

Определите максимальное количество процессов, которые параллельно выполняются на $6$-й мс. Считать, что каждый процесс начинается в самое раннее допустимое время. Нумерация миллисекунд начинается с $1$.

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

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$-й мс.

Нужен отрезок работы каждого процесса. Процесс стартует сразу после того, как закончится последний из тех, от которых он зависит. Если процесс заканчивается на мс $f$ и длится $d$ мс, то занят он миллисекундами с $f-d+1$ по $f$. Процесс выполняется на $6$-й мс, если $f-d+1 \le 6 \le f$.

Независимые процессы $6$, $25$ и $17$ занимают мс $1$, $1$–$2$ и $1$–$4$ соответственно. Процесс $2$ зависит от $6$ и $25$, стартует после $2$ мс и работает с $3$ по $4$ мс; процесс $4$ зависит от $25$ и тоже занимает мс $3$–$4$. Процесс $7$ зависит от $25$, стартует после $2$ мс и работает с $3$ по $7$ мс — он захватывает шестую миллисекунду.

Дальше идут процессы, стартующие после $4$ мс. Процесс $8$ зависит от $17$ и $25$, позже заканчивается $17$ (на $4$ мс), поэтому $8$ занимает мс $5$–$10$. Процесс $14$ зависит от $4$ и занимает мс $5$–$9$. Процесс $23$ зависит от $17$ и занимает мс $5$–$9$. Процесс $20$ тоже зависит от $17$ и занимает мс $5$–$7$. Наконец, процесс $18$ зависит от $2$, $17$ и $4$ — все они заканчиваются на $4$ мс, значит $18$ работает с $5$ по $7$ мс.

Все эти пять процессов плюс процесс $7$ и дают ответ. Остальные либо заканчиваются раньше шестой миллисекунды ($6$, $25$, $17$, $2$, $4$), либо стартуют позже: ближайшие из них, $10$, $16$ и $22$, начинаются только на $8$-й мс.

Таким образом, на $6$-й мс параллельно выполняются процессы $7$, $8$, $14$, $18$, $20$ и $23$ — всего $6$ процессов.

ПроцессЗанятые мс
$6$$1$
$25$$1$–$2$
$17$$1$–$4$
$2$, $4$$3$–$4$
$7$$3$–$7$
$8$$5$–$10$
$14$, $23$$5$–$9$
$18$, $20$$5$–$7$
$22$$8$
$10$, $16$$8$–$11$
$5$, $21$$10$–$13$
$3$$12$–$16$
$1$$14$–$15$
$15$, $19$$14$–$16$
$24$$17$–$18$
$13$$17$–$20$
$9$, $12$$17$–$22$
$11$$23$–$26$

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

import pandas as pd
from functools import lru_cache

df = pd.read_excel('22-08.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)

# процесс занимает мс с finish-t+1 по finish
print(sum(1 for p in t if finish(p) - t[p] < 6 <= finish(p)))   # 6

Условие finish(p) - t[p] < 6 означает, что процесс успел стартовать до конца $6$-й миллисекунды, а 6 <= finish(p) — что он к этому моменту ещё не закончился. Вся совокупность процессов в этом файле завершается на $26$ мс.

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

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