平成21年度 春期 問72
アルゴリズムとプログラミング
アルゴリズムに関する問題
図 1 のように二つの正の数値 A1，A2 を読み取り，二つの数値 B1，B2 を出力するボックスがある。B1 には A2 と同じ数値を出力し，B2 には A1 を A2 で割った余りを出力する。図 2 のようにこのボックスを 2 個つないだ場合，A1＝15，A2＝6 のとき後方のボックスの B1 に出力される数値は幾らか。
〔図1〕
A1 ──→┌─────────────────────┐──→ B1
│ A2 → B1 │
A2 ──→│ A1／A2 の余り → B2 │──→ B2
└─────────────────────┘
〔図2〕
15 ──→┌────────┐──→┌────────┐──→ B1
│ 前方 │ │ 後方 │
6 ──→└────────┘──→└────────┘──→ B2
前方の B1 が後方の A1 に，前方の B2 が後方の A2 につながる。- ア0
- イ3
- ウ6
- エ15
答えと解説を見る
✓ これが正解イ3
解説
箱の問いは、一段ずつ手で回して値を書き出していきます。
この箱は、二つ目の数をそのまま上の出口へ送り出します。下の出口へは、一つ目を二つ目で割った余りを出す決まりでした。前の箱に十五と六を入れると、上の出口には六が出ます。十五を六で割った余りは三で、それが下の出口へ出ます。その二つが、そのまま後ろの箱の入り口へつながります。後ろの箱には六と三が入るので、上の出口には三が出ます。問われているのは後ろの上の出口なので、三を挙げた肢が当たります。零を挙げた肢は、後ろの下の出口に出る値でした。六を三で割れば割り切れるので、余りは零になります。六を挙げた肢は、前の箱の上の出口に出た値です。この箱を繰り返すと最大公約数が求まり、アルゴリズムの型になります。割り切れて余りが零になったとき、直前の数が答えになります。十五と六なら、その最大公約数は三でした。
ほかの選択肢はなぜ違うのか
- ア0：零を挙げています。確かにどこかに現れる値でした。ところが出てくるのは、後ろの箱の下の出口です。六を三で割ると、ちょうど割り切れます。問われているのは、上の出口のほうでした。下の出口を問われたなら、これが答えです。
- ウ6：六を挙げています。これも途中に現れた値でした。前の箱の上の出口から出てきた数にあたります。それが後ろの箱の一つ目の入り口へ入りました。後ろの上の出口には、別の値が出てきます。前の箱を問われたなら、これが答えです。
- エ15：十五を挙げています。最初に入れた値でした。箱をひとつも通っていない数にあたります。前の箱の時点で、既に六と三へ変わっています。後ろの出口に、そのまま出ることはありません。入れた数を問われたなら、これが答えです。
この問題の用語
- アルゴリズム問題を解くための、決まった手順や考え方そのものです。同じ問題でも手順によって、処理にかかる時間や必要な記憶量が変わります。
出典：平成21年度 春期 ITパスポート試験 問72（改変：原典の図表をテキストに書き起こした）
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）