関数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の最大公約数になっています。
【キーワード】
・ユークリッドの互除法
戻る
一覧へ
次へ