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