アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20170122 実施分 問4
図の線上を，点Pから点Rを通って，点Qに至る最短経路は何通りあるか。
格子状の図。横5マス×縦4マス（横線5本，縦線6本）。左下の格子点がP，右上の格子点がQ。Rは，Pから右へ2・上へ2の格子点（左から3番目の縦線上，下から3番目の横線上）に黒丸で示されている。
- ア 16
- イ 24
- ウ 32
- エ 60
出典：基本情報技術者試験 科目A免除 修了試験 20170122 実施分 問4
答えと解説を見る
正解：エ
覚える知識
格子状経路の最短経路数(組合せ)
格子上の最短経路数は、右と上の移動回数の並べ方である組合せ C(r+u, u) で求まる。
この問題で必要なこと
PからRまでは右2・上2でC(4,2)=6通り、RからQまでは右3・上2でC(5,2)=10通り。積で60通りとなる。
ひっかけ
Rを通る条件を無視して全体の経路数を数えると別の値になる。
この知識の出題：本試験系 1 回・免除試験 5 回（公開問題での観測値）