平成27年度 秋期 応用情報技術者試験 午前 問6
テクノロジ／アルゴリズム次に示すユークリッドの互除法（方法1，方法2）で，正の整数 a，b の最大公約数は，それぞれ m と n のどちらの変数に求まるか。ここで，m mod n は，m を n で割った余りを表す。 （注：本サイトでは原問題の表を文字表記に変換しています）
出典：平成27年度 秋期 応用情報技術者試験 午前 問6
- ア方法1はm，方法2はm
- イ方法1はm，方法2はn
- ウ方法1はn，方法2はm
- エ方法1はn，方法2はn
正解：ウ
解説
方法1はループの先頭でr＝0を判定してから更新するため，最後にnに代入された値が最大公約数になります。方法2は本体を実行してからr＝0を判定する形（後判定ループ）のため，最後にmに代入された値が最大公約数になります。実際にa＝12，b＝8で追跡すると，方法1はn＝4，方法2はm＝4で終了し，ともに正しい最大公約数4が得られます。
選択肢ごとの解説
- ア誤り。方法1・方法2ともにmに求まるとすると，方法1の終了時の値の対応が合いません。
- イ誤り。方法1がmに求まるという判定が誤りで，実際は方法1はnに最大公約数が残ります。
- ウ正しい。方法1はループ1の判定後にn→m，r→nと更新するため最終的にnに，方法2は後判定ループでm mod nの結果を保持するため最終的にmに最大公約数が求まります。
- エ誤り。方法2がnに求まるという判定が誤りで，実際は方法2はmに最大公約数が残ります。