В файле содержится информация о
В этом случае процессы могут выполняться только последовательно.
В файле информация о процессах представлена в виде таблицы. В первой колонке таблицы указан идентификатор процесса (ID), во второй колонке таблицы — время его выполнения в миллисекундах, в третьей колонке перечислены
Типовой пример организации данных в файле:
| ID процесса В | Время выполнения процесса В (мс) | ID процесса(ов) А |
|---|---|---|
| 1 | 4 | 0 |
| 2 | 3 | 0 |
| 3 | t | 1; 2 |
| 4 | 7 | 3 |
Определите максимально возможное целочисленное t (время выполнения процесса), при котором выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно и один процесс может сменять другой завершившийся мгновенно, завершилось не более чем за 22 мс.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.
В таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
Далее рассчитаем время выполнения оставшихся процессов:
f(4) = 3 + f(1) = 3 + 1 = 4;
f(5) = 5 + f(3) = 5 + 2 = 7;
f(6) = 1 + max(f(2), f(4),f(5)) = 1 + 7 = 8;
f(7) = 4 + f(6) = 4 + 8 = 12;
f(8) = 6 + f(7) = 6 + 12 = 18;
f(9) = 3 + f(8) = 3 + 18 = 21;
f(11) = 3 + f(10) = 3 + 7 = 10;
f(12) = t + max(f(9), f(11)) = t + 21.
Поскольку длительность
Ответ: 1.