次に示すユークリッド互助法(方法1、方法2)で、正の整数a 、b の最大公約数は、それぞれm とn のどちらの変数に求まるか。
ここで、m mod n はm をn で割った余りを表す。
| 方法1 | 方法2 | |
| ア | m | m |
| イ | m | n |
| ウ | n | m |
| エ | n | n |
答え ウ
【解説】
ユークリッドの互除法では、変数m とn でm mod n =0となったときの、n が最大公約数になる。
問題の流れ図(フローチャート)ではr =m mod n なので、r =0を計算したときのn が最大公約数になり、方法1の場合は、n であり、方法2の場合は、r =m mod n の計算のあとでr =0のチェックをする前にn →m を行っているのでm が最大公約数になる。(ウ)
【キーワード】
・ユークリッドの互除法
戻る
一覧へ
次へ