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