本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成24年度 春期 応用情報技術者試験問題と解説

問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 で割った余りを返すものとする。

〔関数の定義〕
 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

問7 目次 問9