平成27年度秋期 応用情報技術者試験 午前 問6
次に示すユークリッドの互除法（方法1，方法2）で，正の整数a，bの最大公約数は，それぞれmとnのどちらの変数に求まるか。ここで，m mod nは，mをnで割った余りを表す。
- ア 方法1：m，方法2：m
- イ 方法1：m，方法2：n
- ウ 方法1：n，方法2：m
- エ 方法1：n，方法2：n
解答・解説を見る
正解：ウ
AI解説
ユークリッドの互除法は「大きい方を、割った余りで置き換える」操作を余りが0になるまで繰り返し、余りが0になったときの除数(割る数)が最大公約数となるアルゴリズムである。設問の擬似コードをトレースすると、方法1では終了時に変数nに、方法2では変数mに最大公約数が残る。よって組合せは「方法1:n、方法2:m」である。 ア: 方法1でmに求まるとしている点が誤り。方法1の更新手順では終了時の最大公約数は変数n側に残る。 イ: 方法1:m、方法2:nはいずれも逆であり誤り。 ウ: 正解。方法1では変数nに、方法2では変数mに最大公約数が求まる。 エ: 方法2でnに求まるとしている点が誤り。方法2の手順では最大公約数はmに残る。 💡 この種の問題は具体値(例:a=12、b=8、最大公約数4)を代入して擬似コードをトレースし、終了時にどの変数に4が入るかを確認するのが最も確実である。
出典：平成27年度 秋期 応用情報技術者試験 午前 問6 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。