アルゴリズム (全82問中25問目)

No.25

関数gcd(m,n)が次のように定義されている。m=135,n=35のとき,gcd(m,n) は何回呼ばれるか。ここで,最初のgcd(135,35)の呼出しも,1回に数えるものとする。また,m,n (m>n≧0)は整数とし,m mod nはmをnで割った余りを返すものとする。
08.gif/image-size:336×79

分類

テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム

正解

解説

この再帰関数は拡張されたユークリッドの互除法を用いて整数m,nの最大公約数(Greatest Common Divisor:gcd)を求めるものです。
  1. gcd(135, 35) //n>0
  2. gcd(35, 135 mod 35) //n=30
  3. gcd(30, 35 mod 30) //n=5
  4. gcd(5, 30 mod 5)=30 //n=0
4回の呼び出しで最大公約数である5を得られることがわかります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop