テクノロジ系
春期
応用情報技術者 2012年 春期 問8
8 / 80
関数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(n，m mod n) （n＞0のとき）
正解と解説
表示する
正解 ウ
4
ユークリッドの互除法。gcd(135,35)→gcd(35,30)→gcd(30,5)→gcd(5,0)。呼び出しは4回（最初の呼出しを含む）で、n=0になった時点で終了します。よって正解はウ(4回)です。