Задание, на мой взгляд, самое скучное. Но выполнять его всё равно надо, поэтому - поехали. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз. Что это вообще такое? Это так называемая весовая матрица. В ней указаны расстояния между всеми пунктами. Точнее, между теми, которые сообщаются между собой. Чтобы решить нашу задачу, нужно начертить схему, на котоой все эти дороги будут отображены. Схема носит гордое дворянское название "граф". На графе нужно будет отметить протяжённость каждой дороги. Вот как это будет выглядеть: Какими способами можно попасть из A в D? Запишем их все, посчитаем их длины. ABCD = 2 + 3 % = 10 км ACD = 6 + 5 = 11 км AED = 8 + 3 = 11 км AECD = 8 + 2 + 5 = 15 км ACED = 6 + 2 + 3 = 11 км Всё, других нет, вроде? Точно, нет.
Публикация доступна с подпиской
ОГЭ по информатике (+ уровень 1)