指定点を通る格子の最短経路はどう数えるか
基本情報技術者試験 平成30年度春期 午前 問2 ／ 基礎理論 › 応用数学
過去問にチャレンジ
図の線上を，点Pから点Rを通って，点Qに至る最短経路は何通りあるか。
- ア
16
- イ
24
- ウ
32
- エ
60
会話形式の解説
講師指定された点Rを通るので、PからRとRからQに分けて考えましょう。
受験者最短経路なら、どちらの区間も右と上に必要な回数だけ進めばよいのですね。
講師はい。PからRは右に2回、上に2回です。この4回をどの順番で進むか数えられますか。
受験者4回のうち右に進む位置を2つ選ぶので、通りです。
講師そのとおりです。では、RからQに必要な移動はどうなりますか。
受験者右に3回、上に2回です。上に進む位置を5回の中から2つ選ぶので、通りです。
講師ここで6通りと10通りをどう使いますか。
受験者足して16通りかと思いましたが、それでは前半と後半をつないだ経路を数えていませんね。
講師はい。PからRの各経路に、RからQの10通りをそれぞれつなげられます。したがって6×10＝60通りです。
受験者24通りや32通りも、前後の経路を一つずつ選んだ結果とは一致しません。60通りを選びます。
講師指定点を通る経路では、まず点の前後で必要な移動を数えます。各区間の移動順を組合せで求め、最後に経路数を掛け合わせましょう。
まとめ
PからRは右2回・上2回なので、移動順は通りです。RからQは右3回・上2回なので、通りです。前半と後半の経路を一つずつ組み合わせるため、6×10＝60通りとなり、正解はエです。
解答・解説
正解はエです
この問題のテーマ
指定された点を通る、格子上の最短経路の数を求める問題です。
解き方の考え方
PからR、RからQに分けて数えます。PからRは右2回・上2回なので、4回の移動のうち右に進む2回の位置を選び、通りです。RからQは右3回・上2回なので、通りです。前半のどの経路にも後半の10通りをつなげられるため、6×10＝60通りとなります。
選択肢ごとの解説
- ×ア 16アの16通りは、2区間の経路数を足した値です。1本の経路には両区間を通る必要があり、それぞれの選び方を組み合わせるので、この値にはなりません。
- ×イ 24イの24通りは、両区間の経路を組み合わせた数と一致しません。PからRの経路を1つ決めても、RからQには10通りの選び方があります。
- ×ウ 32ウの32通りも、両区間の組合せを数えた結果とは一致しません。Rの前後で必要な移動回数を数え、それぞれの経路数を求めると判定できます。
- ○エ 60エの60通りが計算結果と一致します。Rを通る最短経路は、PからRへの経路とRからQへの経路を1つずつ選ぶと一意に決まります。
POINT
- 格子上の最短経路では、必要な右移動と上移動だけを行います。
- 右にa回、上にb回進む経路数は、a＋b回の中から右移動の位置をa個選ぶ組合せで求められます。
- 指定点を通る経路は、その点の前後の経路を1つずつ選んで数えます。