基本情報技術者平成30年春期 午前問2

午前問2

図の線上を,点Pから点Rを通って,点Qに至る最短経路は何通りあるか。
02.gif/image-size:255×115
  • [この問題の出題歴]
  • 基本情報技術者 H20秋期 問7
  • 基本情報技術者 H27秋期 問2
  • ソフトウェア開発技術者 H20秋期 問5

分類

テクノロジ系 » 基礎理論 » 応用数学

正解

解説

点Pから点Rに至る最短経路の長さは4で、列挙してみると、
  • ↑↑→→
  • ↑→↑→
  • ↑→→↑
  • →→↑↑
  • →↑→↑
  • →↑↑→
の6通りになりますが、どの経路も「上方向に2回,右方向に2回」の移動を行うことは同じです。

4回行われる移動のうち上2回の位置が決まると自動的に右2回の位置も決定することから、経路の組合せ数は、4つの中から2つを選ぶ組合せ数と同様の計算で求めることができることになります。

つまり点Pから点Rに至る経路数は、組合せの公式を用いて次のように求められます。

 4C2=(4×3)/2=6(通り)

同様に点Rから点Qに至る最短経路数は、

 5C3=(5×4×3)/(3×2)=10(通り)

最終的に求める点Pから点Rを通って,点Qに至る最短経路ですが、点Pから点Rに至る6通りのそれぞれに対して、点Rから点Qに至る10通りが存在するので、

 6×10=60(通り)

正解は60通りになります。
組合せ数の公式
n個の中からr個を選ぶ組合せ数 nCr は、「n!/(r!(n-r)!)」で求められる。
© 2010-2021 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop