ITパスポート|データ分析・データ利活用 問18
図1の A1地点から C2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、図2のように数えることによって3通りあることが分かる。A1地点から、C2地点を経由して、D4地点へ行く最短経路は何通りあるか。
(図1)4×4 の碁盤の目。下の行から A1~A4、B1~B4、C1~C4、D1~D4 と並び、右と上にだけ進む。(図2)A1 から B1、A2 にそれぞれ 1 通り、B2 に 2 通り、C1 に 1 通り、C2 に 3 通り。
正解:イ
解説
A1 → C2 の経路の数と、C2 → D4 の経路の数を掛けます。
- A1 → C2
- 3 通り
- C2 → D4
- 上に 1、右に 2 進むので 3 通り
- 合計
- 3 × 3 = 9 通り
- イ 正解。9 通りです。
もう一歩深く
A1 から C2 までの最短経路は 3 通りです。C2 から D4 までは、上に 1 回、右に 2 回進むので、3 回のうちどこで上に進むかを選んで 3 通りです。A1 から C2 を経由して D4 までは、3 × 3 = 9 通りです。経由する地点がある場合は、前半と後半の経路の数を掛け合わせるのがポイントです。
出典:平成22年度秋期 ITパスポート試験 公開問題 問72(読点「,」を「、」に改変)