アルゴリズムとプログラミング
平成30年度 春期 基本情報技術者試験 午前 問2
図の線上を，点 P から点 R を通って，点 Q に至る最短経路は何通りあるか。
横5マス×縦4マスの格子。左下の格子点が P，右上の格子点が Q。R は左から 2 本目の縦線（左端を 0 として x=2）と下から 2 本目の横線（下端を 0 として y=2）の交点。
答えを選ぶ
出典：平成30年度 春期 基本情報技術者試験 午前 問2（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：エ
覚える知識
格子状経路の最短経路数(組合せ)
格子の最短経路数は、右への移動と上への移動の並べ方の組合せ数(nCk)で求め、中継点を通る場合は区間ごとの積になる。
この問題で必要なこと
PからRまでの経路数とRからQまでの経路数をそれぞれ組合せで求め、積の法則で掛け合わせる。P→R は C(4,2)=6、R→Q は C(5,2)=10 で合計60通り。
ひっかけ
R を通る条件を無視して全経路を数える、または足し算してしまう。
この知識の出題：本試験系 1 回・免除試験 5 回（公開問題での観測値）。頻出知識ランキング469位（全1,254件中）。