9
Шешімі: Количество путей в графе
ОГЭ · Информатика · Тапсырма 9 · Графы и пути
КүрделіФИПИ07A4c6Қысқа жауап≈ 3 минутТалдау 3 қадамЖауап сверен с ключом
Условие
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешім по шагам
3 қадам1
Начинаем с города А: количество путей в А принимаем равным 1.
2
Двигаясь по направлению стрелок, для каждой следующей вершины складываем количества путей, ведущих в неё из всех предшествующих вершин.
После последовательного подсчёта для всех вершин графа сумма количеств путей, приходящих в город Л, равна 22.
Жауап
22
22
так ответ выглядит в бланкеГде здесь ошибаются
Считать дороги вместо путей.
Учитывать движение против направления стрелок.
Не складывать пути, приходящие в вершину по разным дорогам.