問題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>0
- gcd(35, 135 mod 35) //n=30
- gcd(30, 35 mod 30) //n=5
- gcd(5, 30 mod 5)＝30 //n=0
4回の呼び出しで最大公約数である5を得られることがわかります