アルゴリズムとプログラミング
基本情報技術者試験 科目A免除 修了試験 20130127 実施分 問3
図の線上を，点 P から点 R を通って，点 Q に至る最短経路は何通りあるか。
格子状の道路図。横 5 マス×縦 4 マスの長方形格子。左下の格子点が P，右上の格子点が Q。R は P から右へ 2 本目・上へ 2 本目の格子点（下から 3 行目の線上，左から 3 本目の縦線上）にある。
答えを選ぶ
出典：基本情報技術者試験 科目A免除 修了試験 20130127 実施分 問3（問題文は IPA の公開問題。解説は当サイト作成）
解説に誤りを見つけたら、解説の誤りを報告してください。
答えと解説を見る
正解：エ
覚える知識
格子状経路の最短経路数(組合せ)
格子状の最短経路数は、右と上の移動の並べ方として組合せ nCk で数え、経由点がある場合は区間ごとの積をとる。
この問題で必要なこと
P から R までは右 2・上 2 で C(4,2)=6 通り。R から Q までは右 3・上 2 で C(5,2)=10 通りなので、積は 60 通りである。
ひっかけ
P から Q への全経路 C(9,4)=126 や、区間の和を答えにしてしまう誤り。
この知識の出題：本試験系 1 回・免除試験 5 回（公開問題での観測値）。頻出知識ランキング469位（全1,254件中）。