В файле содержится информация о совокупности N вычислительных процессов, которые могут выполняться параллельно или последовательно. Будем говорить, что процесс B зависит от процесса A, если для выполнения процесса B необходимы результаты выполнения процесса A. В этом случае процессы могут выполняться только последовательно.
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы — время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример организации данных в файле:
ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A
1
| 4 | 0
2 | 3 | 0
3 | 1 | 1;2
4 | 7 | 3
В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 — через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов = 5 + 7 = 12 мс.
Выполните задания, используя данные из файла ниже:
Задание 22
Информация о процессах представлена в файле в виде таблицы. В первой строке таблицы указан идентификатор процесса (ID), во второй строке таблицы — время его выполнения в миллисекундах, в третьей строке перечислены с разделителем «;» ID процессов, от которых зависит данный процесс. Если процесс является независимым, то в таблице указано значение 0.
Определите минимальное время, через которое завершится выполнение всей совокупности процессов, при условии, что все независимые друг от друга процессы могут выполняться параллельно.
Типовой пример организации данных в файле:
ID процесса B | Время выполнения процесса B (мс) | ID процесса(ов) A
1
| 4 | 0
2 | 3 | 0
3 | 1 | 1;2
4 | 7 | 3
В данном случае независимые процессы 1 и 2 могут выполняться параллельно, при этом процесс 1 завершится через 4 мс, а процесс 2 — через 3 мс с момента старта. Процесс 3 может начаться только после завершения обоих процессов 1 и 2, то есть через 4 мс после старта. Он длится 1 мс и закончится через 4 + 1 = 5 мс после старта. Выполнение процесса 4 может начаться только после завершения процесса 3, то есть через 5 мс. Он длится 7 мс, так что минимальное время завершения всех процессов = 5 + 7 = 12 мс.
Выполните задания, используя данные из файла ниже:
Задание 22
💡 Пошаговый разбор и решение:
Отсортируем данные в таблице так, чтобы все независимые процессы оказались в начале таблицы и любой процесс был расположен после всех процессов, от которых он зависит. Также в таблицу добавим столбец «Время окончания процесса» и запишем туда длительности независимых процессов.
A | B | C | D
ID процесса B | Время
выполнения
процесса B (мс)
| ID процесса(ов) A |
1 | 9 | 0 | 9
2 | 9 | 1 |
3 | 8 | 2 |
4 | 4 | 1;2 |
5 | 4 | 3;4 |
6 | 7 | 4 |
7 | 7 | 0 | 7
8 | 7 | 3;5 |
9 | 4 | 6;7 |
10 | 6 | 5 |
11 | 9 | 2;3 |
12 | 3 | 0 | 3
13 | 8 | 6;7 |
14 | 5 | 8;10 |
15 | 8 | 4;11 |
Далее рассчитаем время выполнения оставшихся процессов:
f(2) = 9 + f(1) = 9 + 9 = 18;
f(3) = 8 + f(2) = 8 + 18 = 26;
f(4) = 4 + max(f(1), f(2)) = 4 + 18 = 22;
f(5) = 4 + max(f(3), f(4)) = 4 + 26 = 30;
f(6) = 7 + f(4) = 7 + 22 = 29;
f(8) = 7 + max(f(3), f(5)) = 7 + 30 = 37;
f(9) = 4 + max(f(6), f(7)) = 4 + 29 = 33;
f(10) = 6 + f(5) = 6 + 30 = 36;
f(11) = 9 + max(f(2), f(3)) = 9 + 26 = 35;
f(13) = 8 + max(f(6), f(7)) = 8 + 29 = 37;
f(14) = 5 + max(f(8), f(10)) = 5 + 37 = 42;
f(15) = 8 + max(f(4), f(11)) = 8 + 35 = 43.
A | B | C | D
ID процесса B | Время
выполнения
процесса B (мс)
| ID процесса(ов) A |
1 | 9 | 0 | 9
2 | 9 | 1 | 18
3 | 8 | 2 | 26
4 | 4 | 1;2 | 22
5 | 4 | 3;4 | 30
6 | 7 | 4 | 29
7 | 7 | 0 | 7
8 | 7 | 3;5 | 37
9 | 4 | 6;7 | 33
10 | 6 | 5 | 36
11 | 9 | 2;3 | 35
12 | 3 | 0 | 3
13 | 8 | 6;7 | 37
14 | 5 | 8;10 | 42
15 | 8 | 4;11 | 43
Ответ: 43.
Приведём решение на языке Python.
def f(d):
if d[2] == [0]:
return d[1]
else:
maxx = 0
for i in d[2]:
if maxx Примечание.
Для считывания информации из файла необходимо конвертировать его из xlsx в csv.
A | B | C | D
ID процесса B | Время
выполнения
процесса B (мс)
| ID процесса(ов) A |
1 | 9 | 0 | 9
2 | 9 | 1 |
3 | 8 | 2 |
4 | 4 | 1;2 |
5 | 4 | 3;4 |
6 | 7 | 4 |
7 | 7 | 0 | 7
8 | 7 | 3;5 |
9 | 4 | 6;7 |
10 | 6 | 5 |
11 | 9 | 2;3 |
12 | 3 | 0 | 3
13 | 8 | 6;7 |
14 | 5 | 8;10 |
15 | 8 | 4;11 |
Далее рассчитаем время выполнения оставшихся процессов:
f(2) = 9 + f(1) = 9 + 9 = 18;
f(3) = 8 + f(2) = 8 + 18 = 26;
f(4) = 4 + max(f(1), f(2)) = 4 + 18 = 22;
f(5) = 4 + max(f(3), f(4)) = 4 + 26 = 30;
f(6) = 7 + f(4) = 7 + 22 = 29;
f(8) = 7 + max(f(3), f(5)) = 7 + 30 = 37;
f(9) = 4 + max(f(6), f(7)) = 4 + 29 = 33;
f(10) = 6 + f(5) = 6 + 30 = 36;
f(11) = 9 + max(f(2), f(3)) = 9 + 26 = 35;
f(13) = 8 + max(f(6), f(7)) = 8 + 29 = 37;
f(14) = 5 + max(f(8), f(10)) = 5 + 37 = 42;
f(15) = 8 + max(f(4), f(11)) = 8 + 35 = 43.
A | B | C | D
ID процесса B | Время
выполнения
процесса B (мс)
| ID процесса(ов) A |
1 | 9 | 0 | 9
2 | 9 | 1 | 18
3 | 8 | 2 | 26
4 | 4 | 1;2 | 22
5 | 4 | 3;4 | 30
6 | 7 | 4 | 29
7 | 7 | 0 | 7
8 | 7 | 3;5 | 37
9 | 4 | 6;7 | 33
10 | 6 | 5 | 36
11 | 9 | 2;3 | 35
12 | 3 | 0 | 3
13 | 8 | 6;7 | 37
14 | 5 | 8;10 | 42
15 | 8 | 4;11 | 43
Ответ: 43.
Приведём решение на языке Python.
def f(d):
if d[2] == [0]:
return d[1]
else:
maxx = 0
for i in d[2]:
if maxx Примечание.
Для считывания информации из файла необходимо конвертировать его из xlsx в csv.
Правильный ответ:
43
📚 Похожие разобранные задания по предмету:
ID 34230 • Задание №25
Напишите программу, которая перебирает целые числа, большие 600 000, в порядке возрастания и ищет среди них та...
ID 33966 • Задание №24
Текстовый файл состоит не более чем из 106 символов L, D и R. Определите длину самой длинной последовательност...
🔗 Другие задания линии №22 по предмету Информатика:
ID 33548
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполнят...
ID 33549
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполнят...
ID 33550
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполнят...
ID 33551
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполнят...
ID 33552
В файле содержится информация о совокупности N вычислительных процессов, которые могут выполнят...