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

Схема дорог: сколько путей

Дана схема дорог со стрелками. Нужно сосчитать число различных путей из одного города в другой, иногда — через заданный город или в обход него.

Метод подсчёта

  • В начальный город — 1 путь.
  • В любой другой — сумма путей в города, откуда в него ведут стрелки.
  • Считаем по порядку, пока не дойдём до конечного города.

Через город и мимо города

  • Через X: (пути до X) × (пути от X до конца).
  • Не через X: считаем, как обычно, но для X ставим 0.

Типичные ошибки

  • Пропустить стрелку при подсчёте суммы.
  • Посчитать город раньше, чем все города, из которых в него ведут стрелки.

Разобранные варианты

Сначала реши сам, потом открой разбор. В разборе — подсчёт по городам и программа на Python.

Вариант 1

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город I?

ABCDEFGHI

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

  1. A = 1 (начало)
  2. B = A = 1
  3. D = A = 1
  4. C = A + B = 1 + 1 = 2
  5. F = B + D = 1 + 1 = 2
  6. E = B + C + D = 1 + 2 + 1 = 4
  7. G = B + D + E + F = 1 + 1 + 4 + 2 = 8
  8. H = E + F = 4 + 2 = 6
  9. I = G + H = 8 + 6 = 14

Ответ: 14

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'E'), ('B', 'F'), ('B', 'G'), ('C', 'E'), ('D', 'E'), ('D', 'F'), ('D', 'G'), ('E', 'G'), ('E', 'H'), ('F', 'G'), ('F', 'H'), ('G', 'I'), ('H', 'I')]

def paths(v, visited):
    if v == 'I':
        return 1
    total = 0
    for a, b in edges:
        if a == v:
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 2

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K?

ABCDEFGHIJK

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

  1. A = 1 (начало)
  2. B = A = 1
  3. C = A = 1
  4. D = A + B = 1 + 1 = 2
  5. E = C = 1
  6. F = D = 2
  7. G = C + D = 1 + 2 = 3
  8. H = C + E = 1 + 1 = 2
  9. J = F + G = 2 + 3 = 5
  10. I = G + H = 3 + 2 = 5
  11. K = H + I + J = 2 + 5 + 5 = 12

Ответ: 12

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'D'), ('C', 'E'), ('C', 'G'), ('C', 'H'), ('D', 'F'), ('D', 'G'), ('E', 'H'), ('F', 'J'), ('G', 'I'), ('G', 'J'), ('H', 'I'), ('H', 'K'), ('I', 'K'), ('J', 'K')]

def paths(v, visited):
    if v == 'K':
        return 1
    total = 0
    for a, b in edges:
        if a == v:
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 3

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

ABCDEFGH

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

  1. A = 1 (начало)
  2. B = A = 1
  3. C = A = 1
  4. D = C = 1
  5. E = B + C + D = 1 + 1 + 1 = 3
  6. F = D + E = 1 + 3 = 4
  7. G = D + F = 1 + 4 = 5
  8. H = F + G = 4 + 5 = 9

Ответ: 9

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('D', 'E'), ('D', 'F'), ('D', 'G'), ('E', 'F'), ('F', 'G'), ('F', 'H'), ('G', 'H')]

def paths(v, visited):
    if v == 'H':
        return 1
    total = 0
    for a, b in edges:
        if a == v:
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 4

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город I?

ABCDEFGHI

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

  1. A = 1 (начало)
  2. B = A = 1
  3. C = A + B = 1 + 1 = 2
  4. E = B = 1
  5. D = B + C = 1 + 2 = 3
  6. F = D + E = 3 + 1 = 4
  7. G = B + D + E = 1 + 3 + 1 = 5
  8. H = D = 3
  9. I = D + F + G + H = 3 + 4 + 5 + 3 = 15

Ответ: 15

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('B', 'G'), ('C', 'D'), ('D', 'F'), ('D', 'G'), ('D', 'H'), ('D', 'I'), ('E', 'F'), ('E', 'G'), ('F', 'I'), ('G', 'I'), ('H', 'I')]

def paths(v, visited):
    if v == 'I':
        return 1
    total = 0
    for a, b in edges:
        if a == v:
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 5

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город I?

ABCDEFGHI

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

  1. A = 1 (начало)
  2. B = A = 1
  3. C = A + B = 1 + 1 = 2
  4. D = C = 2
  5. E = C = 2
  6. H = B + D = 1 + 2 = 3
  7. F = D + E = 2 + 2 = 4
  8. G = E = 2
  9. I = F + G + H = 4 + 2 + 3 = 9

Ответ: 9

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'H'), ('C', 'D'), ('C', 'E'), ('D', 'F'), ('D', 'H'), ('E', 'F'), ('E', 'G'), ('F', 'I'), ('G', 'I'), ('H', 'I')]

def paths(v, visited):
    if v == 'I':
        return 1
    total = 0
    for a, b in edges:
        if a == v:
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 6

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город J?

ABCDEFGHIJ

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

  1. A = 1 (начало)
  2. B = A = 1
  3. D = A = 1
  4. C = A + B = 1 + 1 = 2
  5. G = B + D = 1 + 1 = 2
  6. E = A + C = 1 + 2 = 3
  7. F = B + C + D = 1 + 2 + 1 = 4
  8. H = E + G = 3 + 2 = 5
  9. I = E + F + G = 3 + 4 + 2 = 9
  10. J = H + I = 5 + 9 = 14

Ответ: 14

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('B', 'C'), ('B', 'F'), ('B', 'G'), ('C', 'E'), ('C', 'F'), ('D', 'F'), ('D', 'G'), ('E', 'H'), ('E', 'I'), ('F', 'I'), ('G', 'H'), ('G', 'I'), ('H', 'J'), ('I', 'J')]

def paths(v, visited):
    if v == 'J':
        return 1
    total = 0
    for a, b in edges:
        if a == v:
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 7

через H

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город I, проходящих через город H?

ABCDEFGHI

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

Шаг 1. Пути из A в H:

  1. A = 1 (начало)
  2. B = A = 1
  3. C = A = 1
  4. D = A = 1
  5. F = B = 1
  6. E = B + C + D = 1 + 1 + 1 = 3
  7. G = E = 3
  8. H = E + F + G = 3 + 1 + 3 = 7
  9. I = H = 7

Шаг 2. Пути из H в I (считаем заново, начиная с H):

  1. H = 1 (начало)
  2. I = H = 1

Шаг 3. Каждый путь до H можно продолжить любым путём после: 7 × 1 = 7.

Ответ: 7

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'E'), ('B', 'F'), ('C', 'E'), ('D', 'E'), ('E', 'G'), ('E', 'H'), ('F', 'H'), ('G', 'H'), ('H', 'I')]

def paths(v, visited):
    if v == 'I':
        return 1 if 'H' in visited else 0
    total = 0
    for a, b in edges:
        if a == v:
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 8

не через C

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K, не проходящих через город C?

ABCDEFGHIJK

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

  1. A = 1 (начало)
  2. B = A = 1
  3. C = 0 (через этот город ехать нельзя)
  4. D = A = 1
  5. F = B + C + D = 1 + 0 + 1 = 2
  6. G = D + F = 1 + 2 = 3
  7. H = E + F = 0 + 2 = 2
  8. I = F + G = 2 + 3 = 5
  9. J = H = 2
  10. K = I + J = 5 + 2 = 7

Ответ: 7

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'F'), ('C', 'E'), ('C', 'F'), ('D', 'F'), ('D', 'G'), ('E', 'H'), ('F', 'G'), ('F', 'H'), ('F', 'I'), ('G', 'I'), ('H', 'J'), ('I', 'K'), ('J', 'K')]

def paths(v, visited):
    if v == 'K':
        return 1
    total = 0
    for a, b in edges:
        if a == v and b != 'C':
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 9

через D

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H, проходящих через город D?

ABCDEFGH

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

Шаг 1. Пути из A в D:

  1. A = 1 (начало)
  2. B = A = 1
  3. C = A + B = 1 + 1 = 2
  4. D = A + B + C = 1 + 1 + 2 = 4
  5. E = B + C = 1 + 2 = 3
  6. F = D = 4
  7. G = C + D + E = 2 + 4 + 3 = 9
  8. H = F + G = 4 + 9 = 13

Шаг 2. Пути из D в H (считаем заново, начиная с D):

  1. D = 1 (начало)
  2. F = D = 1
  3. G = C + D + E = 0 + 1 + 0 = 1
  4. H = F + G = 1 + 1 = 2

Шаг 3. Каждый путь до D можно продолжить любым путём после: 4 × 2 = 8.

Ответ: 8

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'D'), ('C', 'E'), ('C', 'G'), ('D', 'F'), ('D', 'G'), ('E', 'G'), ('F', 'H'), ('G', 'H')]

def paths(v, visited):
    if v == 'H':
        return 1 if 'D' in visited else 0
    total = 0
    for a, b in edges:
        if a == v:
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Вариант 10

не через B

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K, не проходящих через город B?

ABCDEFGHIJK

Разбор

Идея. Число путей в город равно сумме чисел путей в города, из которых в него ведут стрелки. Считаем по порядку: сначала города, в которые стрелки приходят только из уже посчитанных.

  1. A = 1 (начало)
  2. B = 0 (через этот город ехать нельзя)
  3. D = A = 1
  4. C = A + B = 1 + 0 = 1
  5. E = A + B + D = 1 + 0 + 1 = 2
  6. F = B + D = 0 + 1 = 1
  7. G = A + B + D = 1 + 0 + 1 = 2
  8. H = E + G = 2 + 2 = 4
  9. I = B + C + E + F + G = 0 + 1 + 2 + 1 + 2 = 6
  10. J = E + G = 2 + 2 = 4
  11. K = F + G + H + I + J = 1 + 2 + 4 + 6 + 4 = 17

Ответ: 17

Решение на Python.

edges = [('A', 'B'), ('A', 'C'), ('A', 'D'), ('A', 'E'), ('A', 'G'), ('B', 'C'), ('B', 'E'), ('B', 'F'), ('B', 'G'), ('B', 'I'), ('C', 'I'), ('D', 'E'), ('D', 'F'), ('D', 'G'), ('E', 'H'), ('E', 'I'), ('E', 'J'), ('F', 'I'), ('F', 'K'), ('G', 'H'), ('G', 'I'), ('G', 'J'), ('G', 'K'), ('H', 'K'), ('I', 'K'), ('J', 'K')]

def paths(v, visited):
    if v == 'K':
        return 1
    total = 0
    for a, b in edges:
        if a == v and b != 'B':
            total += paths(b, visited | {b})
    return total

print(paths('A', {'A'}))

Для самостоятельного решения

Варианты 11–15 без разборов. Ответ можно проверить кнопкой.

Вариант 11

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город I?

ABCDEFGHI

Вариант 12

через G

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город J, проходящих через город G?

ABCDEFGHIJ

Вариант 13

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город J?

ABCDEFGHIJ

Вариант 14

не через F

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город I, не проходящих через город F?

ABCDEFGHI

Вариант 15

все пути

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H, I, J, K. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город K?

ABCDEFGHIJK