修了試験 2017-01-22実施分 基本情報技術者試験 問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通りです。 全体は6×10＝60通りです。 【選択肢別解説】 1：× 16通りは、6×10＝60通りと一致しません。 2：× 24通りも、PからRまでの6通りとRからQまでの10通りの積になっていません。 3：× 32通りも誤りです。 正しくは6×10＝60通りです。 4：○ PからRまでの6通りとRからQまでの10通りを掛け合わせた60通りと一致します。 【ポイント】 横m、縦nの最短経路数は、(m＋n)C(m)で求められます。 途中の点を必ず通る場合は、区間ごとの経路数の積になります。