平成24年 春期 応用情報技術者 午前 問8

関数gcd(m , n )が次のように定義されている。
m = 135、n = 35のとき、gcd(m , n )は何回呼ばれるか。
ここで、最初のgcd(135, 35)の呼出しも、1回に数えるものとする。
また、m n (m > n ≥ 0)は整数とし、m mod n m n で割った余りを返すものとする。

[関数の定義]

 ア  2  イ  3  ウ  4  エ  5


答え ウ


解説
gcd(135, 35)はn = 35なので、関数の定義の下の行の式「gcd(n , m mod n )」が呼ばれ、135 mod 35 = 30なので、これはgcd(35, 30)になる。(2回目)
gcd(35, 30)はn = 30なので、関数の定義の下の行の式「gcd(n , m mod n )」が呼ばれ、35 mod 30 = 5なので、これはgcd(30, 5)になる。(3回目)
gcd(30, 5)はn = 5なので、関数の定義の下の行の式「gcd(n , m mod n )」が呼ばれ、30 mod 5 = 0なので、これはgcd(5, 0)になる。(4回目)
gcd(5, 0)はn = 0なので、関数の定義の上の行になり、m である5が関数の結果として返る。
したがって、gcd(m , n )が呼ばれる回数は4回(ウ)である。
なお、この関数の結果の5は135と35の最大公約数になっています。


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

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

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

戻る 一覧へ 次へ