4 Способ 1 — электронные таблицы (основной)

Способ 1 — электронные таблицы (основной)

Разберём на примере из условия — 6 процессов:

ID

Время

Зависит от

1

3

0

2

4

1

3

2

2; 4

4

5

0

5

8

1; 4

6

3

1

Считаем концы через ВПР и МАКС

Идея: чтобы найти конец процесса, надо взять концы всех процессов, от которых он зависит, выбрать из них максимум и прибавить своё время. Концы зависимостей «подтягиваем» функцией ВПР (поиск по таблице).

Пусть в столбце A — ID, в B — время, в C, D — номера зависимостей (если их две, разносим по двум столбцам). Тогда:

E2: =ВПР(C2; $A:$G; 7; 0) # конец первой зависимости (0 если её нет)

F2: =ВПР(D2; $A:$G; 7; 0) # конец второй зависимости

G2: =МАКС(E2:F2) + B2          # КОНЕЦ процесса = макс(концы зависимостей) + время

Столбец G и есть время конца каждого процесса. Для нашего примера концы получаются такие:

ID

Время

Начало

Конец

1

3

0

3

2

4

3

7

3

2

7

9

4

5

0

5

5

8

5

13

6

3

3

6

Проверка: процесс 3 зависит от 2 и 4, их концы 7 и 5, значит начало = 7, конец = 9. Всё как в условии — «начинается на 8-й мс, заканчивается на 9-й».

⚠️ Порядок вычислений и итерации

Процесс 3 зависит от процесса 4, у которого номер больше. Если заполнять формулы строго сверху вниз, ВПР для процесса 3 сошлётся на ещё не посчитанный конец процесса 4. Решение: в LibreOffice включи Сервис → Параметры → Вычисления → Итеративные вычисления (шагов 100). Тогда таблица «дорешается» сама. Либо заранее отсортируй процессы так, чтобы зависимости шли выше.

Отвечаем на вопрос

Дальше под конкретный вопрос берём нужную формулу по столбцу концов G:

=МАКС(G:G) # минимальное время всей совокупности

=СЧЁТЕСЛИ(G:G; "<=17") # сколько процессов завершится за первые 17 мс

Для примера минимальное время всей совокупности = МАКС концов = 13.

Способ 1 — электронные таблицы (основной) — Задание 22 ЕГЭ 2027 | Методички — Профиматика