** ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G,...

0 голосов
342 просмотров
На ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G, Н. По каж­до­му со­еди­не­нию можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из пунк­та А в пункт Н?

Объясните подробно, как решите это задание (ответ: 4)
image

Информатика (388 баллов) | 342 просмотров
0

На ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G, Н. По каж­до­му со­еди­не­нию можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из пунк­та А в пункт Н?

Дан 1 ответ
0 голосов
Правильный ответ

1. Исходная точка А. Снабжаем букву индексом 1, получая А₁
2. На пути (стрелке) А в В пишем число, которое записано, как индекс А, т.е. 1.
2. Еще в В можно попасть из С, но мы не можем никак прийти из А в С, поэтому путь С->А не учитываем и ставим на этой стрелке 0. Суммируем числа, указанные на стрелках, ведущих в В (1+0=1) и эту сумму записываем индексом В, получая В₁
3. Переходим к точке D. На стрелку A->D переносим индекс из А, т.е. 1. Так же поступаем со стрелкой B->D. Сумму чисел со стрелок, ведущих в D (1+1=2) переносим в индекс D, получая D₂. Это означает, что в D можно прийти двумя путями.
4. Из D можно попасть в точки E и H, поэтому на соответствующих стрелках пишем индекс D, т.е. 2. В узел Е ведут еще два пути, но мы не можем на них попасть, поэтому проставляем на стрелках нули.И снова 2+0+0=2 записываем в индексе, но уже узла E₂.
5. Узел Н - конечный. В него ведут две стрелки с числом 2 и еще один путь из G, куда мы не можем попасть, поэтому ставим 0 на G->H. Складываем 2+2+0=4 и пишем индекс: H₄. Этот индекс и есть ответ.

Из А в Н ведут 4 пути.

(150k баллов)