トップ過去問一覧応用情報技術者 平成20年・秋 > 問5
問5

図の線上を、点Pから点Rを通って、点Qに至る最短経路は何通りあるか。

○正解
×不正解

16

24

32

60

解説

[ 点P~点R ]

最短経路の距離は4です。その移動パターンとしては、縦縦横横、縦横縦横、縦横横縦…などがあります。最短経路の数を求めるということは、これらのパターンがいくつあるか求めることと同じです。

 

パターン数は、組合せの考え方で計算できます。最短距離4であるため、4回の移動があります。4回の移動(移動1、移動2、移動3、移動4)のうち、横へ移動するのを2つ取り出す組合せを計算します。すなわち4C2 = (4・3)/(2・1) = 6になります。

 

[ 点R~点Q ]

上記と同様に、5回の移動(移動1、移動2、移動3、移動4、移動5)のうち、横へ移動するものを3つ取り出す組合せを計算します。すなわち5C3 = (5・4・3)/(3・2・1) = 10になります。

 

[ 点P~点Q ]

全体としては、点P~点Rの6通りのそれぞれに対して、点R~点Qの10通りがあるので、6×10=60通りです。

 

※解説では横への移動を取り出す組合せを計算しましたが、縦への移動を取り出す組合せを計算してもOKです。その場合の計算式は、4C2 × 5C2= 6 × 10 = 60 となります。

無料学習システムはこちら
→間違えた問題を繰り返し学習
→分野別学習
→模擬試験モード
デモサイト
無料ユーザ登録

問題文や解説文の内容の正確性については、できるかぎりチェックをしていますが、間違いがある可能性があります。 十分ご注意の上、参考までにご利用ください。