【(高卒)国家一般職・平成25年度・No.18】(経路問題の元祖)格子状道路を通る最短経路問題【行政・高卒区分】
平成25年度・国家一般職(高卒区分)No.18の問題です。
経路問題の元祖ともいうべき問題であり、『格子状道路』を通る最短経路の組合せの数が問われています。
経路問題の基礎を固める上で非常に重要な問題ですので、しっかりと理解するようにしてください。
経路を分割して考える(A→B)
問題で問われているのは『A→B→C→D→A』と戻ってくる最短経路の組合せですが、まず最初に『A→B』の組合せを考えてみます。
格子状道路の問題における必須テクニックですが、まず最初にAと直線でつながっている格子点に1を書き、その後は『左と下の数字を足した数』を左下から右上へと順次記入していくことで、最短経路のパターン数を数えることができます。
B→Cの間の最短経路数
『B』から『C』までの最短経路数については、BとCの位置関係がAとBの位置関係と全く同じであることから、10通りであることが分かります。
C→Dの間の最短経路数
AB間と同様の方法で最短経路数を数えてみると4通りであることが分かります。
D→Aの間の最短経路数
同様に8通りと求めることができます。
『A→B→C→D→A』の最短経路の数
上図のとおり、これまでに求めてきた区間ごとの最短経路数を掛け合わせることによって、3200通りと求めることができます。(正解肢4)
コメント