平成27年度 秋期 午前 問6
アルゴリズム
ユークリッドの互除法に関する問題
次に示すユークリッドの互除法（方法 1，方法 2）で，正の整数 a，b の最大公約数は，それぞれ m と n のどちらの変数に求まるか。ここで，m mod n は，m を n で割った余りを表す。
〔流れ図〕
方法 1 方法 2
開始 開始
a → m ／ b → n a → m ／ b → n
m mod n → r ループ 2 の上端（条件の記載なし）
ループ 1 の上端 r ＝ 0 m mod n → r
n → m n → m
r → n r → n
m mod n → r ループ 2 の下端 r ＝ 0
ループ 1 の下端 終了
終了
| 方法 1 | 方法 2 | |
|---|---|---|
| ア | m | m |
| イ | m | n |
| ウ | n | m |
| エ | n | n |
- アm m
- イm n
- ウn m
- エn n
答えと解説を見る
✓ これが正解ウn m
解説
抜ける位置が一手ずれるので、答えの残る変数が変わります。
二つの手順はどちらもユークリッドの互除法ですが、流れ図の上で繰返しを抜ける判定を置く位置が違います。同じ数で手を動かすと差がはっきりします。a を 8、b を 6 とすると最大公約数は 2 です。方法 1 は繰返しに入る前に余りを求めるので、8 を 6 で割った余り 2 を得て中へ入り、n の値を m へ、余りを n へ移してから、6 を 2 で割った余り 0 を求めます。ここで判定に当たって抜けるため、m は 6、n は 2 のまま残り、答えは n の側にあります。方法 2 は先に繰返しへ入り、終わりで判定します。余りが 0 になった回もそのまま移す処理を通るので、答えが m へ送られ、n には 0 が残ります。前判定と後判定では、抜けた後の変数の中身が一手ぶんずれるというのが、この設問の軸です。a を 12、b を 18 と入れ替えても、置き場所の結論は変わりません。
ほかの選択肢はなぜ違うのか
- アm m：二つを同じものと見なし、どちらも同じ変数に答えが残ると決めた形です。判定を置く位置が違う以上、抜けた時点で値を移し終えているかどうかが変わるので、行き先もそろいません。
- イm n：二つの手順の答えの置き場所を、そっくり入れ替えて読んだ形です。余りを求めてから繰返しに入る側と、繰返しの終わりで判定する側を取り違えると、この組合せになります。
- エn n：どちらも同じ変数に残ると決めた形ですが、繰返しの終わりで判定する側は、余りが 0 になった回にも移し替えを通るため、その変数には 0 が残ってしまいます。
出典：平成27年度 秋期 応用情報技術者試験 午前 問6
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）