午前問2
図の線上を、点Pから点Rを通って、点Qに至る最短経路は何通りあるか。
| 16 | |
| 24 | |
| 32 | |
| 60 |
『情報処理過去問.com』からiPhoneアプリがリリースされました！！
正解
- エ
解説
点Pから点Rに至る最短経路の長さは4で6通りがあります。
↑↑→→
↑→↑→
↑→→↑
→→↑↑
→↑→↑
→↑↑→
点Rから点Qに至る最短経路の長さは5で10通りがあります。
↑↑→→→
↑→↑→→
↑→→↑→
↑→→→↑
→↑↑→→
→↑→↑→
→↑→→↑
→→↑↑→
→→↑→↑
→→→↑↑
最短経路の組み合わせは
点Pから点R×点Rから点Qとなるので
6通り×10通り=60通り
となります。
組合せ数の公式で求める方法
設問は『組合せ数の公式』でも求めることができます。
n個の中からr個を選ぶ組合せ数 nCr は、「n!／(r!(n-r)!)」です。
点Pから点Rに至る最短経路の組み合わせは上に2回、右に2回移動する4つの組み合わせから2つをとる組み合わせなので
n!/r!(n-r)!
=4!/2!(4-2)!
=4!/2!×2!
=(4×3×2×1)/((2×1)×(2×1))
=6
次に点Rから点Qに至る最短経路の組み合わせは上に2回、右に3回移動する5つの組み合わせから2つをとる組み合わせなので
n!/r!(n-r)!
=5!/2!(5-2)!
=5!/2!×3!
=(5×4×3×2×1)/((2×1)×(3×2×1))
=10
点Pから点R×点Rから点Qとなるので
6×10=60
60通りとなります。
↑↑→→
↑→↑→
↑→→↑
→→↑↑
→↑→↑
→↑↑→
点Rから点Qに至る最短経路の長さは5で10通りがあります。
↑↑→→→
↑→↑→→
↑→→↑→
↑→→→↑
→↑↑→→
→↑→↑→
→↑→→↑
→→↑↑→
→→↑→↑
→→→↑↑
最短経路の組み合わせは
点Pから点R×点Rから点Qとなるので
6通り×10通り=60通り
となります。
組合せ数の公式で求める方法
設問は『組合せ数の公式』でも求めることができます。
n個の中からr個を選ぶ組合せ数 nCr は、「n!／(r!(n-r)!)」です。
点Pから点Rに至る最短経路の組み合わせは上に2回、右に2回移動する4つの組み合わせから2つをとる組み合わせなので
n!/r!(n-r)!
=4!/2!(4-2)!
=4!/2!×2!
=(4×3×2×1)/((2×1)×(2×1))
=6
次に点Rから点Qに至る最短経路の組み合わせは上に2回、右に3回移動する5つの組み合わせから2つをとる組み合わせなので
n!/r!(n-r)!
=5!/2!(5-2)!
=5!/2!×3!
=(5×4×3×2×1)/((2×1)×(3×2×1))
=10
点Pから点R×点Rから点Qとなるので
6×10=60
60通りとなります。