問題プレビューID: 129b110c応用情報技術者試験 2012年(平成24年度)春期 午前

問 8
応用情報技術者試験 2012年(平成24年度)春期 午前

関数 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)\gcd(m, n) = \begin{cases} m & (n = 0) \\ \gcd(n, m \bmod n) & (n > 0) \end{cases}
解説

正解は「ウ」です。

定義に従って再帰呼出しを順に追います。

  • gcd(135, 35):135 mod 35 = 30 なので gcd(35, 30) を呼び出す(1 回目)。
  • gcd(35, 30):35 mod 30 = 5 なので gcd(30, 5) を呼び出す(2 回目)。
  • gcd(30, 5):30 mod 5 = 0 なので gcd(5, 0) を呼び出す(3 回目)。
  • gcd(5, 0):n = 0 なので m = 5 を返す(4 回目)。

呼出しは合計 4 回です。

  • ア: 2 回ではありません。
  • イ: 3 回ではありません。
  • エ: 5 回ではありません。

関連問題

本文が同じ・似ている問題を表示しています