修了試験 2022-07-24実施分 基本情報技術者試験 問10

解説

正解は2です。 この関数は、ユークリッドの互除法でxとyの最大公約数を求める再帰関数です。 y＞0の間はF(y，x mod y)を呼び出し、y＝0になったときのxが答えになります。 【計算】 F(231，15)では、231 mod 15＝231－15×15＝6なので、F(15，6)を呼び出します。 F(15，6)では、15 mod 6＝3なので、F(6，3)を呼び出します。 F(6，3)では、6 mod 3＝0なので、F(3，0)を呼び出します。 F(3，0)はy＝0なので、xの値である3を返します。 【選択肢別解説】 1：× 231も15も奇数なので、2は共通の約数ではありません。 再帰をたどった結果も3です。 2：○ 再帰をたどると3が返ります。 231＝3×7×11、15＝3×5なので、最大公約数が3であることとも一致します。 3：× 5は15の約数ですが、231は5で割り切れないので答えになりません。 4：× 7は231の約数ですが、15は7で割り切れないので答えになりません。 【ポイント】 「大きい数を小さい数で割った余り」を繰り返し、余りが0になったときの割る数が最大公約数です。 再帰関数の問題は、呼出しを1段ずつ書き出して追跡すると確実です。