ITパスポート試験 ITパスポート 2010年 (平成22年 秋期) 問72: 図1のA1地点からC2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、図2のように数えることによって3通りあることが分かる。A1地点から、C2地点を経
←
ITパスポート 2010年 (平成22年 秋期)
Q 7272 / 88
図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からその地点までの最短経路の数を表す。
この問の正解率:56.66%(593件)
解説
ITパスポート 2010年 (平成22年 秋期) 問72「図1のA1地点からC2地点へ行くとき、通過する地点が最も少なくてすむ最短経路は、…」の正解と解説です。ITパスポート試験の「テクノロジ系」分野の過去問で、これまでの受験者の正答率は約57%です。
正解
イ. 9
正答率 56.7%（593人中 336人が正解）
問題の解説
最短経路の場合分け問題.A1からC2は3通りと与えられている.C2からD4への最短経路数を計算し、A1→C2→D4の総数=A1→C2(3通り)×C2→D4(?通り)で求める.C2からD4は右に1区画・上に2区画移動で、組合せC(3,1)=3通り.合計3×3=9通り.混同注意として、合計問題は両区間の積を取る原則「経由点までの数×経由点からの数」を覚える.正解はイ.
選択肢ごとの解説
- ア6通りはA1→C2(3通り)+C2→D4(3通り)と誤って加算した値.経路の組合せは順次的な経路選択であり、積で計算するのが正しいため誤答.
- イ正解.A1→C2が3通り、C2→D4が3通り(右1上2の組合せ).3×3=9通りが正答.経由点問題は両区間の経路数を掛ける.
- ウ12通りは中間経路数の誤算.正しくはC2→D4=C(3,1)=3通り、A1→C2=3通り、計9通り.12は数え過ぎ.
- エ20通りはA1→D4の総経路数(C(6,3)=20)に近い値だが、C2経由の条件を満たさない総経路数で誤り.C2必須経由を考慮していない.
ITパスポート試験 の iOS アプリ版
アプリ版なら、よりスムーズに動作し、
スワイプで問題遷移ができます。
