修了試験 2020-12-13実施分 基本情報技術者試験 問9

解説

正解は2です。 関数F(x,y)は、yが0になるまで「F(y, x mod y)」と自分自身を呼び出す再帰関数です。 これはユークリッドの互除法そのもので、xとyの最大公約数を求めます。 定義に従って1ステップずつ値をたどります。 【計算】 F(231,15)では、231 mod 15を求めます。 231＝15×15＋6なので、余りは6で、F(15,6)になります。 15 mod 6は、15＝6×2＋3なので3で、F(6,3)になります。 6 mod 3は0なので、F(3,0)になります。 y＝0なので、F(3,0)＝3です。 【選択肢別解説】 1：× 2は231と15の公約数ではありません。 231は奇数なので、2では割り切れません。 2：○ 互除法をたどるとF(3,0)＝3となります。 231＝3×77、15＝3×5で、3は231と15の最大公約数です。 3：× 5は15の約数ですが、231は5で割り切れません。 231の一の位は1なので、5の倍数ではありません。 4：× 7は231の約数（231＝7×33）ですが、15は7で割り切れません。 【ポイント】 「F(y, x mod y)を繰り返し、y＝0でxを返す」形の関数は、ユークリッドの互除法による最大公約数の計算です。 再帰関数の問題は、引数の変化を1行ずつ書き出すと確実に解けます。