平成30年度春期　基本情報処理試験　午前問2解説

当サイトでは、IPA主催の基本情報処理試験のうち主に計算問題について解説を行います。計算問題以外については基本的に覚えれば解けますので、頑張って覚えてください。

解説が必要な問題があれば、問い合わせよりご連絡ください。

問２の内容

図の線上を、点Ｐから点Ｒを通って、点Ｑに至る最短経路は何通りあるか。

ア　16
イ　24
ウ　32
エ　60

IPA情報処理推進機構より転載

答えはクリックすることで表示されますが、わからない場合はこのページを読んで理解してください。

経路数を求める問題ですので、一本一本確認していっても答えは見つかります。
しかし、漏れたりしますし、何より時間がかかります。

これは確率計算の問題に置き換えることができます。置き換えることができれば、
あっという間に正解に近づきます。

確率計算

どのように確率計算に置き換えるか。再度図を再度確認しましょう。
点Ｐから点Ｒに至る最短経路は、点Ｐを起点として

• 右右上上
• 右上右上
• 右上上右
• 上上右右
• 上右上右
• 上右右上

の6通りがあります。

これをどうやって確率計算で求めるかということになります。
4つのうち右が2回任意の場所に現れるということです。（右ではなくて上でも大丈夫です。）

つまり、確率計算でいうと　_nC_rに当てはめることができます。
この場合は、₄C₂ということです。

_nC_rの計算方法は後述します。

同様に点Ｒから点Ｑに至る最短経路は、
点Ｒを起点とすると、以下の計算で求めることができます。

• ₅C₂ （5つのうち上は2回現れる）
• ₅C₃ （5つのうち右は3回現れる）

_nC_rの計算方法

これは単なる計算方法ですので覚えてください。次式で計算できます。

例えば、₄C₂ は
(4×3)/(2×1)で計算できます。したがって₄C₂=6となります。

回答解説

この問題は経路の問題ですが、確率計算_nC_rに気づくことができればあっという間ですね。

点Ｐから点Ｒに至る最短経路は
₄C₂=6通りです。
点Ｒから点Ｑに至る最短経路は
₅C₂=10通りです。(₅C₃でも同じです。)

したがって6通り×10通りが点Ｐから点Ｒを通って、点Ｑに至る最短経路数となります。

正解は、「エ　60」ですね。