問題プレビューID: eebc860bITパスポート試験 2010年(平成22年度)秋期

問 72
ITパスポート試験 2010年(平成22年度)秋期

図 1 の A1 地点から C2 地点へ行くとき,通過する地点が最も少なくてすむ最短経路は,図 2 のように数えることによって 3 通りあることが分かる。A1 地点から,C2 地点を経由して,D4 地点へ行く最短経路は何通りあるか。

D1D2D3D4 ●
C1C2 ●C3C4
B1B2B3B4
A1 ●A2A3A4

図 2 は,A1 から各地点までの最短経路の数を求めたものである(括弧内の数字が経路の数)。

解説

正解は「イ」です。

格子状の経路では,各地点までの最短経路の数は,左隣の地点までの経路数と下隣の地点までの経路数の和になります。

  • A1 から C2 までの最短経路は,右へ 1 回,上へ 2 回進む組合せなので 3 通りです(図 2 のとおり)。
  • C2 から D4 までの最短経路は,右へ 2 回,上へ 1 回進む組合せなので,C2→C3→C4→D4 などの経路を含めて 3 通りです。

A1 から C2 までの 3 通りと,C2 から D4 までの 3 通りを組み合わせるので,3 × 3 = 9 通りとなります。

関連問題

本文が同じ・似ている問題を表示しています