平成27年 秋期 基本情報技術者 午前 問2

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

 ア  16  イ  24  ウ  32  エ  60


答え エ


解説
パスカルの三角形を用いて点Pから点R、点Rから点Qの最短経路の数を求めると。

60通り(エ)になります。


キーワード
・最短経路探索

キーワードの解説
  • 最短経路探索
    地点Sから地点Gへの移動距離を最も小さくする経路を探す方法です。
    問題の2次元正方格子上の場合は、各交差点からの移動は縦・横の移動しかなく(図の線の上しか移動できない。)、各交差点間の移動距離は1である。

もっと、「最短経路探索」について調べてみよう。

戻る 一覧へ 次へ