Задание 9 ОГЭ по информатике

9

Способ 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.