Миннурова Азиза Ильдусовна,

учитель математики и информатики

МБОУ «Средняя общеобразовательная школа № 85 с углубленным изучением отдельных предметов» 

РТ, г. Казань

Методика решения задач по формализации и моделированию, алгоритмы их выполнения

(Задача ОГЭ)

Задание 9. На рисунке – схема дорог, связывающих А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К.

Замечание. Как видим, можем перемещаться только от А. Например, от А до Б: односвязная, однонаправленная дорога. То есть мы можем перемещаться только из города А до города Б, обратной связи нет. Иными словами, добраться из города Б в А мы не сможем никак.

Здесь сеть разветвленная, поэтому вариантов будет много.

Начнем решение. Задачу такого типа можем решить одним способом. Начинаем с буквы А. После этого начинаем перебирать по алфавиту, т. е. ищем Б. Из Б в В и так далее. Как только дошли до конца, ищем новый вариант, работая по алфавиту, но заменяя предпоследний город.

Построим первый маршрут. Начинаем с А, потом по алфавиту у нас Б, после идет В, затем Г и дальше Д. Но к городу Д не можем идти, так как связи между Г и Д у нас нет. Следовательно, идем к городу Ж, так как есть связь между ними и потом к К. Запишем это все теперь кратко:

1. А → Б → В →Г → Ж → К. 

Во втором маршруте мы должны изменить предпоследний маршрут, то есть из Г не можем уже пойти в Ж. У нас есть только вариант из Г в К. В итоге получим второй маршрут:

2. А → Б → В → Г→ К.

Далее нам нужно опять убрать предпоследнюю букву – это Г. Получается мы должны из В переместиться к К, так как других вариантов уже нет:

3. А → Б → В → К.

Затем заменяем В, следовательно, продолжаем маршрут после Б. Из Б мы можем двигаться только к Е, а из Е к К. И все:

4.  А → Б → Е → К.

После ищем следующий маршрут. Маршрут А → Б мы полностью перебрали, больше вариантов нет. Следующий маршрут – из А в В. Идем из А в В, по алфавиту потом идет Г, затем Д, но в Д мы не сможем идти, потому что нет связи, следовательно, идем к Ж и доходим до К. Распишем это все:

5. А → В → Г → Ж → К.

Сейчас убираем снова предпоследний маршрут, то есть Ж. В итоге у нас получается, что из Г мы можем только в К:

6. А → В → Г → К.

Продолжаем таким же образом. Еще раз убираем предпоследний маршрут – это Г, потому что других вариантов у нас нет. В итоге получим следующий маршрут:

7. А → В → К.

Пункт А и В мы разобрали. Следующий пункт из А в Г. Как и в предыдущих случаях мы идем по алфавиту. Получается один маршрут:

8. А → Г → Ж → К.

Убираем предпоследний город, и получается еще один маршрут:

9. А → Г → К.

Маршрут, который двигается с А в Г мы разобрали. Остается последний случай – это из А в Д. Работаем по алфавиту и получаем еще один новый маршрут:

10.  А → Д → Г → Ж → К.

Снова убираем предпоследний город Ж, и остается такой вариант:

11.  А → Д → Г → К.

Убираем Г. В итоге из Д двигаемся к Ж, из Ж к К. Запишем и этот полученный нами маршрут:

12.  А → Д → Ж → К.

В итоге мы нашли 12 различных маршрутов, с помощью которых мы можем попасть из города а в город К. В качестве ответа выписывают значения, которые мы нашли – это 12.

Ответ: 12.

Алгоритм выполнения задания:

1. Перебирать варианты начиная с А по алфавиту, изменяя предпоследнюю букву.
2. Подсчитать варианты, которые получились.
3. Записать в ответ получившееся число вариантов.