平成30年度 春期 基本情報技術者試験 午前 問2

解説

格子状の経路上の最短経路数は，各交点までの経路数を，その左隣と下隣の交点までの経路数の和として順に求めていくと計算できます。PからQへの経路は途中で必ずRを通るので，PからRまでの経路数と，RからQまでの経路数を掛け合わせれば求められます。図より，PからRへは右に2，上に2進むので4C2＝6通り，RからQへは右に3，上に2進むので5C2＝10通りとなり，合計6×10＝60通りです。

選択肢ごとの解説

• ア誤り。60通りが正しく，16通りはPR間・RQ間いずれかの経路数を求め違えた場合に生じる値です。
• イ誤り。24通りは，PからRまでの経路数を実際より少なく数えた場合などに生じる値で，正しい60通りとは異なります。
• ウ誤り。32通りは，掛け算ではなく経路数を単純に足し合わせるなど，計算方法を誤った場合に生じる値です。
• エ正しい。PからRまでの最短経路が4C2＝6通り，RからQまでの最短経路が5C2＝10通りあり，Rを必ず通るので6×10＝60通りが求める経路数です。