Четвертое задание, контрольно-измерительных материалов основного государственного экзамена по информатике, содержит задачу на умение анализировать простейшие модели объектов. Работа предстоит с объектами: таблицы, графы, дерево.
Задача.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Есть несколько способов решения задачи, мы используем граф.
Переведм таблицу в граф и рассмотрим возможные варианты.
Условие задачи: кратчайший путь между пунктами А и Е, проходящий через пункт С.
1 вариант
1+2+3+2=8
2 вариант
4+3+2=9
3 вариант
4+2+5+2=13
В остальных вариантах путь не проходит через пункт С. Из возможных вариантов кратчайший путь равен 8.
Ответ: 8
Спасибо за просмотр, ставьте лайк и подписывайтесь на канал.
В комментариях можно оставлять задачи для разбора.