Презентация - ОГЭ по информатике. Задание 4. Формальные описания реальных объектов и процессов

ОГЭ по информатике
Задание 4. Формальные описания реальных объектов и процессов

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

.A.B.C.D.E
A..1...
B.1..2.2.7
C..2...3
D..2...4
E..7.3.4.

Решение: Преобразуем табличную модель в графическую (неориентированный граф). Поскольку табличная модель симметричная, то читаем только данные расположенные либо выше, либо ниже главной диагонали.

А
В

А
В
C

А
В
D
C

А
В
D
C
E

А
В
D
C
E

А
В
D
C
E

Найдём все варианты маршрутов из A в E и выберем самый короткий: A—B—C—E: длина маршрута 6 км. A—B—D—E: длина маршрута 7 км. A—B—E: длина маршрута 8 км. Самый короткий путь: A—B—C—E. Длина маршрута 6 км. Ответ: 6.