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

次に示すユークリッド互助法(方法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 が最大公約数になる。(ウ)


キーワード
・ユークリッドの互除法

キーワードの解説
  • ユークリッドの互除法
    2つの自然数(整数)の最大公約数を求める手法。
    2つの数(自然数、整数)aとb(a ≥ b)について、aのbによる剰余をrとすると、aとbの最大公約数はbとrの最大公約数に等しいという性質が成り立ち、この性質を利用して最大公約数を求める方法。

もっと、「ユークリッドの互除法」について調べてみよう。

戻る 一覧へ 次へ