基本情報技術者 2015年秋期午前（科目A）問02

問題文

図の線上を、点Pから点Rを通って、点Qに至る最短経路は何通りあるか。

🖊️ 解答を隠して解いてみる

選択肢

ア：16

イ：24

ウ：32

エ：60（正解）

🔒 解説は解答すると表示されます

格子経路の組合せ【午前解説】

正解の理由

図の格子は横5マス×縦4マスです。左下の点 P を

(0, 0)

、右上の点 Q を

(5, 4)

とすると、点 R は P から右に2マス、上に2マスの交点

(2, 2)

にあります。

P → R：右に2回、上に2回の計4回の移動。通り数は $(2 4) = 6$
R → Q：右に3回、上に2回の計5回の移動。通り数は $(2 5) = 10$

R を通る最短経路は「P → R の最短経路」と「R → Q の最短経路」をつないだものなので、通り数は積で

6 \times 10 = 60

です。したがって正解はエです。

解法ステップ

座標を決める：P を $(0, 0)$ 、右を $x$ 、上を $y$ の正の向きとする。Q は $(5, 4)$ 、R は $(2, 2)$ 。
区間ごとの移動回数を求める：P → R は右2・上2、R → Q は右3・上2。
組合せで通り数を求める： $(2 4) = 6$ 、 $(2 5) = 10$ 。
積をとる： $6 \times 10 = 60$ 。

（組合せの公式は

(k n) = \frac{n !}{k ! ( n - k )!}

）

選択肢別の誤答解説

ア: 16
区間の通り数を足したり（ $6 + 10 = 16$ ）すると出る値です。区間に分けたときは積をとります。
イ: 24
R の位置や移動回数を取り違えると出る値です。例えば R → Q を右3・上1（ $(1 4) = 4$ ）と数えると $6 \times 4 = 24$ になります。
ウ: 32
2のべき乗のように、組合せではなく分岐の数を掛け合わせると出やすい値です。
エ: 60（正解）
P → R の6通りと R → Q の10通りの積です。

よくある誤解

線の本数とマス数を混同する。横5マスなら縦線は6本、縦4マスなら横線は5本です。
区間の通り数を足してしまう。P → R のどの経路にも R → Q のどの経路をつなげられるので、積になります。

補足コラム

格子上で右に $a$ 回、上に $b$ 回動く最短経路の数は $(a a + b)$ です。
点 R を通る最短経路の数は「P → R の最短経路数」×「R → Q の最短経路数」です。

from math import comb
print(comb(4, 2) * comb(5, 2))  # 60

FAQ

Q1. R を通らない経路も数える場合は？
A1. P → Q の最短経路は右5・上4の

(4 9) = 126

通りです。

Q2. 格子の途中に通れない線がある場合は？
A2. 交点ごとに「左から来る通り数＋下から来る通り数」を書き込んでいく方法（加算法）で数えます。

関連キーワード: 最短経路、組合せ、二項係数、格子経路、積の法則

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！