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

Способ 1. Подсчёт количества путей В город А первоначально можно попасть одним способом: \(P(А)=1\). В города Б и Г ведёт по одной дороге из А: \(P(Б)=1\), \(P(Г)=1\). В город В можно попасть непосредственно из А или через Б: \(P(В)=P(А)+P(Б)=1+1=2\). В город Д можно попасть только из В: \(P(Д)=P(В)=2\). В город И можно попасть из В или из Г: \(P(И)=P(В)+P(Г)=2+1=3\). В город Е можно попасть только из Г: \(P(Е)=P(Г)=1\). В город К ведут дороги из В, Д, И, Г и Е: \(P(К)=P(В)+P(Д)+P(И)+P(Г)+P(Е)=2+2+3+1+1=9\). Ответ: 9. Способ 2. Программное решение на Python # Заполняем словарь, который описывает схему дорог # Для каждого города указаны города, в которые из него можно попасть graph = { 'А': ['Б', 'В', 'Г'], 'Б': ['В'], 'В': ['Д', 'И', 'К'], 'Г': ['И', 'Е', 'К'], 'Д': ['К'], 'И': ['К'], 'Е': ['К'], 'К': [] } # Функция подсчитывает количество путей из указанного города в город К def count_paths(city): # Если мы достигли города К, значит найден один полноценный путь if city == 'К': return 1 # Счётчик путей из текущего города в город К count = 0 # Перебираем все города, в которые можно попасть из текущего города for next_city in graph[city]: # Подсчитываем рекурсивно количество путей из следующего города # и прибавляем их в общему количеству count += count_paths(next_city) # Возвращаем количество найденных путей return count # Вызываем функцию для города А и выводим результат подсчётов путей из А в К print(count_paths('А')) Программа последовательно рассматривает все возможные дороги, пока не достигнет города К. Каждый раз, когда программа попадает в К, она засчитывает один найденный путь. Ответ: 9.