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