基本情報技術者 平成27年度秋期午前問2

午前問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通りとなります。
スポンサーリンク







シェアする

  • このエントリーをはてなブックマークに追加

フォローする