平成23年度 特別 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム関数 f(x, y) が次のように定義されているとき，f(775, 527) の値は幾らか。ここで，x mod y は x を y で割った余りを返す。 f(x, y)：if y＝0 then return x else return f(y, x mod y)
出典：平成23年度 特別 基本情報技術者試験 午前 問6
- ア0
- イ31
- ウ248
- エ527
正解：イ
解説
この関数はユークリッドの互除法でgcd（最大公約数）を求めるものです。f(775,527): 775 mod 527=248 → f(527,248): 527 mod 248=31 → f(248,31): 248 mod 31=0（31×8=248）→ f(31,0)はy=0なので31を返します。したがってf(775,527)=31です。
選択肢ごとの解説
- ア誤り。0になるのはx mod y=0の時点のxの値ではなく，その次の呼出しでy=0になったときのxの値（31）が最終的な戻り値です。
- イ正しい。ユークリッドの互除法により775と527の最大公約数は31と求まります。
- ウ誤り。775 mod 527の計算結果である248を最終値と誤認した場合の値です。再帰はここで終わらず，さらにf(527,248)へと続きます。
- エ誤り。初期値yの527を最終結果と誤認していますが，再帰呼出しによって値は更新されていきます。