HOME»情報セキュリティスペシャリスト平成24年春期»午前Ⅰ 問3
情報セキュリティスペシャリスト平成24年春期 午前Ⅰ 問3
問3
関数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
- [出典]
- 応用情報技術者
平成24年春期 問8と同題
分類
テクノロジ系 » アルゴリズムとプログラミング » アルゴリズム
正解
ウ
解説
この再帰関数は拡張されたユークリッドの互除法を用いて整数m，nの最大公約数(Greatest Common Divisor:gcd)を求めるものです。
- gcd(135, 35) //n>0
- gcd(35, 135 mod 35) //n=30
- gcd(30, 35 mod 30) //n=5
- gcd(5, 30 mod 5)＝30 //n=0