More than 5 years have passed since last update.

【基本情報技術者試験対策】最短経路の問題の解き方

Posted at 2019-04-07

問題

次の３ステップで解ける

1.点Pから点Rに至る経路数を求める
2.点Rから点Qに至る経路数を求める

4回行われる移動のうち上2回の位置が決まると自動的に右2回の位置も決定することから、組合せの公式を用いて次のように求められる。

4C2＝(4×3)／2＝6(通り)

4回行われる移動のうち上3回の位置が決まると自動的に右2回の位置も決定することから、組合せの公式を用いて次のように求められる。

5C3＝(5×4×3)／(3×2)＝10(通り)

右への移動をベースに考えた時でも、求めらえる答えは同じ。

5C2＝(5×4)／2＝10(通り)

6 × 10 = 60(通り)