平成22年度秋期 ITパスポート 問72 解説
図1のA₁地点からC₂地点へ行くとき，通過する地点が最も少なくてすむ最短経路は，図2のように数えることによって3通りあることが分かる。A₁地点から，C₂地点を経由して，D₄地点へ行く最短経路は何通りあるか。
- ア6
- イ9
- ウ12
- エ20
答えを見る
正解 イ9
要点経由地がある経路数は各区間の経路数の積
解説
A₁→C₂が3通り，C₂→D₄が3通りなので，3 × 3 = 9通りです。
- A₁→C₂：図2のとおり3通り
- C₂→D₄：上に1区画，右に2区画進む。3回の移動のうちどこで上に進むかを選ぶので 3C1 = 3通り（C₂→C₃→C₄→D₄，C₂→C₃→D₃→D₄，C₂→D₂→D₃→D₄）
- 合計：3 × 3 = 9通り
区間ごとの数を足すのではなく掛けることに注意します（足すと6でア）。