関数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(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

解答：ウ

＜解説＞

トレースすると次のようになる。

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を得られることがわかります

分類

1. 高度共通　午前1
2. テクノロジ系
3. 基礎理論
4. アルゴリズムとプログラミング
5. その他の言語