平成27年度 秋期 応用情報技術者試験 午前 問6

ユークリッドの互除法は，「mをnで割った余りrを求め，nをmに，rをnに移す」ことを余りが0になるまで繰り返す方法です。余りが0になったときの割る数が最大公約数です。

• 方法1 ループの前に r ← m mod n を求め，r＝0 になったらループを終了します（前判定）。ループ内では n→m，r→n，m mod n→r の順に処理します。r＝0 になったとき，その余りを求めたときの割る数はnに入っているので，最大公約数は n に求まります。 例：a＝12，b＝8 → r＝4 → m＝8，n＝4，r＝0 → 終了。n＝4 が最大公約数です。

• 方法2 ループ内で m mod n→r，n→m，r→n の順に処理し，r＝0 で終了します（後判定）。余りが0になった時点で，割る数だったnの値はmに移され，nには余りの0が入ります。したがって最大公約数は m に求まります。 例：a＝12，b＝8 → r＝4，m＝8，n＝4 → r＝0，m＝4，n＝0 → 終了。m＝4 が最大公約数です。

• ア: 方法1 m，方法2 m
  誤り。方法1ではmには最後に割られる数が残り，最大公約数ではありません。

• イ: 方法1 m，方法2 n
  誤り。方法2ではnには余り0が入ります。

• ウ: 方法1 n，方法2 m
  正しい。上記のとおりです。

• エ: 方法1 n，方法2 n
  誤り。方法2の終了時のnは0です。

答え

ウ: 方法1 n，方法2 m