修了試験 2025-12-14実施分 基本情報技術者試験 問4

解説

正解は4です。 格子状の道を、右と上だけに進む最短経路の数を数える問題です。 図の格子は横5マス、縦4マスで、Pは左下の角、Qは右上の角にあります。 Rは、Pから右へ2マス、上へ2マス進んだ交点にあります。 必ずRを通るので、PからRまでの経路数とRからQまでの経路数を掛け合わせます。 【計算】 PからRへは、右2回と上2回の計4回の移動の並べ方を数えます。 4回のうち右に進む2回を選ぶので、4C2＝6通りです。 RからQへは、右に3回、上に2回の計5回移動します。 5回のうち上に進む2回を選ぶので、5C2＝10通りです。 Rを通る最短経路は、6×10＝60通りです。 【選択肢別解説】 1：× 16通りは、Rを通る最短経路の数として少なすぎます。 PからRが6通り、RからQが10通りなので、掛け合わせると60通りです。 2：× 24通りは、区間ごとの経路数を正しく掛け合わせた値ではありません。 RからQは右3回と上2回の移動なので、10通りあります。 3：× 32通りも、正しい計算からは得られない値です。 最短経路の数は、区間ごとの組合せの数の積で求めます。 4：○ PからRが6通り、RからQが10通りなので、積の法則により60通りになります。 【ポイント】 右にm回、上にn回進む最短経路の数は、(m＋n)Cmで求めます。 途中の点を必ず通る場合は、区間ごとの経路数を掛け合わせます。