Задание 9: подсчёт путей в схеме

1. 1. Стартовая вершина: A = 1.
2. 2. В B ведёт только стрелка из A, значит B = 1.
3. 3. В C ведут стрелки из A и из B: C = A + B = 1 + 1 = 2.
4. 4. В D ведут стрелки из B и из C: D = B + C = 1 + 2 = 3.
5. 5. В E ведут стрелки из C и из D: E = C + D = 2 + 3 = 5.
6. 6. В F ведут стрелки из D и из E: F = D + E = 3 + 5 = 8.
7. 7. Ответ: 8. Заметь, что числа пошли как 1, 1, 2, 3, 5, 8 — так и должно быть, потому что каждая следующая вершина суммирует две предыдущие.

Ответ: Ответ: 8

1. 1. A = 1. Из A выходят стрелки в B и C, поэтому B = 1 и C = 1.
2. 2. В D ведут стрелки из B и C: D = 1 + 1 = 2.
3. 3. В E ведут стрелки из B и C: E = 1 + 1 = 2.
4. 4. В F ведут три стрелки: из D, из E и напрямую из C. Значит F = D + E + C = 2 + 2 + 1 = 5.
5. 5. Ответ: 5. Если пропустить прямую стрелку C→F, получится 4 — это самая частая ошибка в таких схемах.
6. 6. Полезная проверка: перечисли пути вручную — A→B→D→F, A→B→E→F, A→C→D→F, A→C→E→F, A→C→F. Ровно пять, всё сходится.

Ответ: Ответ: 5

1. 1. Приём один: идём по городам в порядке, когда все входящие стрелки уже посчитаны, и для каждого пишем число путей из A в него.
2. 2. A = 1 (сам в себя, пустой путь). B: приходит только из A → 1. C: только из A → 1.
3. 3. D: приходит из B и C → 1 + 1 = 2. E: только из C → 1.
4. 4. F: приходит из D и E → 2 + 1 = 3.
5. 5. H: приходит из F и из C → 3 + 1 = 4.
6. 6. Ответ 4. Правило подсчёта: число путей в город равно сумме чисел во всех городах, откуда в него ведут стрелки. Считать можно только тогда, когда все такие города уже посчитаны, — поэтому порядок обработки решает всё.

Ответ: 4

1. 1. A = 1. B = 1 (из A). C = 1 (из A). D = 1 (из A).
2. 2. E: приходит из B и C → 1 + 1 = 2.
3. 3. F: приходит из C и D → 1 + 1 = 2.
4. 4. G: приходит из E и F → 2 + 2 = 4.
5. 5. Ответ 4. Обрати внимание: город C раздваивает свой единственный путь, отдавая единицу и в E, и в F, — число путей при этом не теряется и не удваивается, оно просто распределяется.
6. 6. Самопроверка: сумма чисел во всех «конечных» городах (куда стрелки только входят) обязана совпасть с ответом, если конечный город один.

Ответ: 4

1. 1. Порядок важен: C нельзя считать раньше B, потому что в C ведёт стрелка из B.
2. 2. A = 1. B = 1 (из A).
3. 3. C: приходит из A и B → 1 + 1 = 2.
4. 4. D: приходит из B и C → 1 + 2 = 3.
5. 5. E: приходит из D и C → 3 + 2 = 5.
6. 6. Ответ 5. Главная ошибка линии 9 — посчитать город, у которого ещё не все входящие стрелки обработаны: если бы C взяли равным 1 (только из A), в ответе вышло бы 3 вместо 5.
7. 7. Практический совет: перед подсчётом выпиши города в таком порядке, чтобы у каждого все «поставщики» стояли левее.

Ответ: 5

1. 1. Замысел: тот же приём, что вручную — обходим города в правильном порядке и суммируем. Порядок задаём сами, перечислив города так, чтобы каждый шёл после всех, откуда в него ведут стрелки.
2. 2. Код целиком (Python): arrows = [('A','B'), ('A','C'), ('A','D'), ('B','E'), ('C','E'), ('C','F'), ('D','F'), ('E','G'), ('F','G')] / order = ['A','B','C','D','E','F','G'] / ways = {v: 0 for v in order} / ways['A'] = 1 / for v in order: / for a, b in arrows: / if a == v: / ways[b] = ways[b] + ways[v] / print(ways['G']).
3. 3. Трассировка: после A — ways[B] = ways[C] = ways[D] = 1. После B — ways[E] = 1. После C — ways[E] = 2, ways[F] = 1. После D — ways[F] = 2. После E — ways[G] = 2. После F — ways[G] = 4. Печатается 4 — совпало со вторым разбором.
4. 4. Что проверить перед сдачей: список order обязан быть правильным. Если поставить C раньше B, программа посчитает неверно — ровно так же, как ошибается человек. Это хорошая иллюстрация того, что в задании 16 эксперт проверяет алгоритм, а не синтаксис.
5. 5. Как сохранять: текстовый файл с расширением .py.

Ответ: count_paths.py: суммирование по порядку городов, печатает 4