必ず受かる情報処理技術者試験

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験,基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 高度共通 午前1
  3. 平成24年度春季問題一覧
  4. 平成24年度春季問題3-解答・解説-分析

平成24年度春季問題

問題3

関数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(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

解答:ウ

<解説>

トレースすると次のようになる。

  1. gcd(135, 35) //n>0
  2. gcd(35, 135 mod 35) //n=30
  3. gcd(30, 35 mod 30) //n=5
  4. gcd(5, 30 mod 5)=30 //n=0

4回の呼び出しで最大公約数である5を得られることがわかります