修了試験 2018-12-09実施分 基本情報技術者試験 問5

解説

正解は2です。 再帰的に定義された関数を、定義に従って計算する問題です。 この関数はユークリッドの互除法で、xとyの最大公約数を求めます。 【計算】 F(231,15)はy＝15＞0なので、F(15, 231 mod 15)を求めます。 231＝15×15＋6なので、231 mod 15＝6で、F(15,6)になります。 15＝6×2＋3なので、15 mod 6＝3で、F(6,3)になります。 6＝3×2＋0なので、6 mod 3＝0で、F(3,0)になります。 y＝0なので、F(3,0)＝3です。 【選択肢別解説】 1：× 231は奇数なので2では割り切れず、2は最大公約数になりません。 計算を進めると結果は3です。 2：○ 上の計算のとおり、F(231,15)＝F(15,6)＝F(6,3)＝F(3,0)＝3です。 231＝3×7×11、15＝3×5なので、最大公約数3とも一致します。 3：× 5は15の約数ですが、231は5で割り切れません。 したがって答えにはなりません。 4：× 7は231の約数ですが、15は7で割り切れません。 したがって答えにはなりません。 【ポイント】 「F(y, x mod y)を繰り返し、yが0になったときのxを返す」形は、ユークリッドの互除法の定番です。 再帰の問題は、引数の変化を1段ずつ書き出すと確実に解けます。