ITパスポート試験 過去問解説
最短経路とは？ITパスポート試験 2010年 (平成22年 秋期) 問72を解説
ITパスポート試験 2010年 (平成22年 秋期) 問72は、最短経路に関する理解を問う問題です。検索から入っても、問題文、選択肢、正解、解説、各選択肢がなぜ違うかをこのページだけで確認できます。
問題文
図1のA1地点からC2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、図2のように数えることによって3通りあることが分かる。A1地点から、C2地点を経由して、D4地点へ行く最短経路は何通りあるか。 図1: 4×4のグリッド上にA1(左下)、D4(右上)などの地点が配置されている。 図2: A1(1)→B1(1)、A1→A2(1)、B1→C1(1)、B1→B2(2)、A2→B2、C1→C2(3)、B2→C2。 ( )内数字は、A1からその地点までの最短経路の数を表す。
この問題の出題ポイント
- 最短経路の定義だけでなく、問題文中の条件がどの選択肢に当てはまるかを確認する。
- テクノロジ系分野では、用語の目的・主体・責任範囲の違いが選択肢で問われやすい。
- 関連タグ: 応用数学、場合の数、最短経路、計算問題、図表問題。
選択肢
- ア6
- イ9正解
- ウ12
- エ20
正解
イ: 9
解説
最短経路は、右か上にだけ進む道順である。A1からC2までは図2のとおり3通り、C2からD4までは右に1、上に2進む道順で、同様に数えると3通りある。経由地点を通る道順の数は前半と後半の積になるので、通りである。
なぜ他の選択肢が違うのか
ア
前半の3通りと後半の3通りを足した値で、掛け合わせるべきところを足している。
イ（正解）
正しい。A1からC2までの3通りそれぞれに、C2からD4までの3通りが組み合わさるので、通りになる。
ウ
後半を4通りと数えたときの値()で、C2からD4までの最短経路は実際には3通りである。
エ
C2を経由する条件を考えず、A1からD4までの全最短経路を数えた値()である。
解き方の整理
最短経路の問題では、選択肢のキーワードだけで判断せず、問題文が示す条件と正解選択肢の説明が一致しているかを見ます。誤答選択肢は、似た用語を混ぜる、主体を入れ替える、目的や範囲を広げすぎる、という形で作られることが多いため、選択肢別解説まで確認しておくと復習効率が上がります。
関連問題
前後の問題
2010年 (平成22年 秋期) の関連する問題
復習を続ける
間違えた問題、苦手タグ、模試履歴を保存して復習する導線を用意しています。広告なしPro、弱点分析、復習リマインダーは段階的に提供予定です。