関数 gcd(m, n) が次のように定義されている。m＝135、n＝35のとき、gcd(m, n) は何回呼ばれるか。ここで、最初の gcd(135,
35) の呼出しも、1回に数えるものとする。
また、m 、n (m ＞ n ≧ 0) は整数とし、m mod n は m を n で割った余りを返すものとする。
〔関数の定義〕
gcd(m, n) = m (n ＝ 0のとき)
gcd(m, n) = gcd(n, m mod n) (n ＞ 0のとき)
ア 2 イ 3 ウ 4 エ 5
ウ
ユークリッドの互除法のアルゴリズムである。
gcd(135, 35) ・・・1回
= gcd(35,135 mod 35) = gcd(35,30) ・・・2回
= gcd(30,35 mod 30) = gcd(30,5) ・・・3回
= gcd(5,30 mod 5) = gcd(5,0) ・・・4回
= 5
| 問２ | 目次 | 問４ |