修了試験 2013-01-27実施分 基本情報技術者試験 問3

解説

正解は4です。 図は横5マス、縦4マスの碁盤目で、点Pは左下の角、点Qは右上の角にあります。 点RはPから右に2目盛、上に2目盛の交点にあります。 最短経路は右と上だけに進む経路なので、組合せの数で数えられます。 P〜RとR〜Qの経路数を掛け合わせれば、Rを通る最短経路の数になります。 【計算】 PからRまでは右に2回、上に2回の合計4回進みます。 4回のうちどの2回を右にするかを選ぶので、4C2＝6通りです。 RからQまでは右に3回、上に2回の合計5回進みます。 5回のうちどの2回を上にするかを選ぶので、5C2＝10通りです。 Rを通る最短経路は、6×10＝60通りです。 【選択肢別解説】 1：× 16通りは計算結果の60通りと一致しません。 2：× 24通りは計算結果の60通りと一致しません。 3：× 32通りは計算結果の60通りと一致しません。 4：○ P〜Rの6通りとR〜Qの10通りを掛けた60通りです。 【ポイント】 右にm回、上にn回進む最短経路は、(m＋n)Cm通りです。 途中の点を必ず通る場合は、その点で区切って経路数を掛け算します。