修了試験 2014-12-21実施分 基本情報技術者試験 問7

解説

正解は2です。 関数F(x,y)は、yが0になるまでF(y, x mod y)を繰り返す再帰関数です。 これはユークリッドの互除法であり、xとyの最大公約数を求めます。 【計算】 F(231,15)では、231 mod 15を求めます。 231＝15×15＋6なので、余りは6であり、F(15,6)になります。 15＝6×2＋3なので、余りは3であり、F(6,3)になります。 6＝3×2＋0なので、余りは0であり、F(3,0)になります。 y＝0なので、F(3,0)＝3です。 したがってF(231,15)＝3です。 【選択肢別解説】 1：× 231は奇数なので2では割り切れません。 2は231と15の公約数ではありません。 2：○ 互除法をたどるとF(3,0)に行き着き、値は3です。 231＝3×77、15＝3×5であり、3が最大公約数です。 3：× 5は15の約数ですが、231は5で割り切れません。 したがって答えになりません。 4：× 7は231の約数ですが、15は7で割り切れません。 したがって答えになりません。 【ポイント】 「F(y, x mod y)を繰り返し、y＝0でxを返す」形はユークリッドの互除法の典型です。 見抜けば、素因数分解で最大公約数を求めて検算できます。