ГлавнаяИнформатикаКак решатьМежду населёнными пунктами A, B, C, D, E, F построены дороги

Между населёнными пунктами A, B, C, D, E, F построены дороги

2016-06-02 14:31:58

Формулировка задания: Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Задание входит в ЕГЭ по информатике для 11 класса под номером 3 (Анализ информационных моделей).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

  1. 9
  2. 13
  3. 14
  4. 15

Решение:

Рассмотрим все возможные пути, по которым можно попасть из пункта A в пункт F:

Из пункта A есть только 1 дорога в пункт B. Из пункта B можно попасть в пункты A, C, D и E, но пункт A нужно исключить, так как мы в нем уже были.

Из пункта C можно попасть только в пункт E (B исключаем). Из пункта E можно попасть в пункты D и F (B и C исключаем). Пункт D также нужно исключить, так как из него можно попасть только в в пункты B и E, где мы уже были. Длина маршрута A – B – C – E – F равна:

4 + 6 + 4 + 5 = 19

Из пункта D можно попасть в пункт E (B исключаем). Из пункта E можно попасть в пункты C и F (B и D исключаем). Пункт C также нужно исключить, так как из него можно попасть только в в пункты B и E, где мы уже были. Длина маршрута A – B – D – E – F равна:

4 + 3 + 2 + 5 = 14

Из пункта E можно попасть только в пункты C, D и F (B исключаем). Пункты C и D также нужно исключить, так как из них можно попасть только в в пункты B и E, где мы уже были. Длина маршрута A – B – E – F равна:

4 + 6 + 5 = 15

Из 3 маршрутов самым коротким является A – B – D – E – F, его длина равна 14. Таким образом, верным является ответ 3.

Ответ: 3

Есть другой способ решения?

Наверх