平成23年度 秋期 問64
基礎理論
アルゴリズムに関する問題
1 〜 4 の番号をもつ四つの状態がある。四つの状態は図のようにつながれており，時計回りや反時計回りに状態を遷移することができる。現在，状態 1 にいて，次の手順を 2 回実施した後はどの状態にいるか。
〔図〕四つの状態が輪になって並んでいる（位置と向きを書き起こしたもの）
┌───┐
┌────│ 1 │────┐
│ └───┘ │
┌───┐ ┌───┐
│ 4 │ │ 2 │
└───┘ └───┘
│ ┌───┐ │
└────│ 3 │────┘
└───┘
時計回り … 1 → 2 → 3 → 4 → 1
反時計回り … 1 → 4 → 3 → 2 → 1
〔手順〕
今いる状態の番号を 11 倍し，それを 3 で割った余りによって次の処理を行う。
・余りが 0 の場合：時計回りに一つ次の状態に遷移する。
・余りが 1 の場合：反時計回りに一つ次の状態に遷移する。
・余りが 2 の場合：時計回りに二つ次の状態に遷移する。- ア1
- イ2
- ウ3
- エ4
答えと解説を見る
✓ これが正解エ4
解説
十一倍して三で割った余りで動くので、二回目で四に着きます。
手順は、番号を十一倍して三で割った余りで決まります。余りが零なら時計回りに一つ、一なら反時計回りに一つ動きました。余りが二のときだけ、時計回りに二つ進みます。初めは一に居るので、十一倍して十一になりました。十一を三で割ると、余りは二です。だから時計回りに二つ動いて、三へ移りました。次に立つのは三なので、十一倍すると三十三です。これを三で割った余りは、零になりました。だから一つ進んで、四へ移ります。つまり四を挙げた肢が当たりました。一を挙げた肢は、二回とも動かなかった形になります。二を挙げた肢のほうは、初めに一つだけ動いた形でした。三を挙げた肢が示すのは、一回目で止めた形です。余りだけを見れば足ります。一回ずつ順に当てます。アルゴリズムのとおりに、一回ずつ当てていけば決まりました。
ほかの選択肢はなぜ違うのか
- ア1：一を挙げた肢が、こちらのほうです。出発した場所から、動かなかった形になります。二回とも同じ数に戻れば、確かにここでした。ところが一回目で余りは二になります。二つ動きました。戻ってはきません。一回目の余りは二です。二つ先へ動きます。
- イ2：二を挙げた肢が、こちらに当たります。初めに時計回りへ一つだけ動いた形でした。余りが零なら、確かにここへ来ます。けれども一回目の余りは二でした。一つ多く動きます。数え方が違いました。一回目に二つ動きます。ここで外れました。
- ウ3：三を挙げた肢が、こちらに当たります。一回目を終えた場所そのものになります。途中で止めれば、確かにここでした。ところが手順は二回まわします。もう一つ先へ動きました。回数が足りません。二回目まで進める形でした。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：平成23年度 秋期 ITパスポート試験 問64（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）