チャレンジ！ アルゴリズム② 解答
こんなふうに計算します。まず、●に左から順に番号を付けます。正確には、出て行ってる矢印が無いものを１つずつ取り、その順番に番号を付けます。このルート図はぐるぐる回り続けるルートがないので、必ずこういう順番付けができます。茶色の●は番号０とします。
次に、番号の小さい順に、「茶色の●までいくつルートがあるか」を計算していきます。1番は出口が一つ、直接茶色につながっているので、一通り。２番は直接茶色に行くか、１番を通るかの２通り。図に書いてみると、
こうなります。１番２番は計算したので黄色にして、中にルートの数を赤で書き込みました。
次に３番を調べます。ここは、直接行くか、あるいは２を経由するか。２番から茶色へは２通りの行き方がありますので、直接＋２通り、で３通り。４番は２通りルートがある●と、１通りルートがる●に行けるので、合計で３通り。
この調子で５番、６番を計算します。５番は３通り、２通り、６通りの頂点に行けるので、合計１１通り、６番は３通りと１１通りで、、、と計算を続けます。
このように計算を続けて、最後まで行くと、このようになります。
合計８７通り。意外と沢山あったと思いませんか？ 右から左に、順番にルートの数を求めることで、各●の計算がお隣の合計を取るだけで良くなっている、っていう所がミソです。わかりました？？？
