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

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

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

問2の内容

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

ア 16
イ 24
ウ 32
エ 60

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

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

 

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

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

確率計算

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

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

の6通りがあります。

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

つまり、確率計算でいうと nCrに当てはめることができます。
この場合は、4C2ということです。

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

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

  • 5C2 (5つのうち上は2回現れる)
  • 5C3 (5つのうち右は3回現れる)

nCrの計算方法

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

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

回答解説

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

点Pから点Rに至る最短経路は
4C2=6通りです。
点Rから点Qに至る最短経路は
5C2=10通りです。(5C3でも同じです。)

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

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

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です