図のような道がある街で、AからBへ行く最短経路の数、そのうちCを通るものの数、そしてCを通りDを通らないものの数をそれぞれ求める問題です。
2025/7/2
1. 問題の内容
図のような道がある街で、AからBへ行く最短経路の数、そのうちCを通るものの数、そしてCを通りDを通らないものの数をそれぞれ求める問題です。
2. 解き方の手順
まず、AからBへ行く最短経路の数を求めます。これは右に4回、下に3回移動するので、全部で7回の移動のうち、右への移動を4回選ぶ組み合わせの数になります。
次に、AからBへ行く最短経路のうち、Cを通るものの数を求めます。これはAからCへ行く最短経路の数と、CからBへ行く最短経路の数を掛け合わせることで求められます。AからCへは右に1回、下に1回移動するので、2回の移動のうち右への移動を1回選ぶ組み合わせの数です。CからBへは右に3回、下に2回移動するので、5回の移動のうち右への移動を3回選ぶ組み合わせの数になります。
最後に、AからBへ行く最短経路のうち、Cを通りDを通らないものの数を求めます。これは、Cを通りBへ行く経路から、CとDを両方通る経路の数を引くことで求められます。AからCへの経路数はすでに計算済みです。CからDへは右に1回、下に1回移動します。DからBへは右に2回、下に1回移動します。
計算:
* AからBへの最短経路数:
* AからCへの最短経路数:
* CからBへの最短経路数:
* AからBへの最短経路でCを通るものの数:
* CからDへの最短経路数:
* DからBへの最短経路数:
* AからBへの最短経路でCとDを両方通るものの数:
* AからBへの最短経路でCを通りDを通らないものの数:
3. 最終的な答え
* AからBへ行く最短経路は35通り
* そのうち、Cを通るものは20通り
* また、AからBへ行く最短経路のうち、Cを通りDを通らないものは8通り