修了試験 2011-07-02実施分 基本情報技術者試験 問6

解説

正解は2です。 F(x,y)は、yが0になるまでF(y, x mod y)を繰り返し呼び出す再帰関数です。 これはユークリッドの互除法そのもので、xとyの最大公約数を返します。 【計算】 F(231,15)では、231÷15＝15余り6なので、F(15,6)を呼び出します。 F(15,6)では、15÷6＝2余り3なので、F(6,3)を呼び出します。 F(6,3)では、6÷3＝2余り0なので、F(3,0)を呼び出します。 F(3,0)はy＝0なので、xの値3を返します。 【選択肢別解説】 1：× 2は231の約数ではありません。 231は奇数なので、2で割り切れません。 2：○ 上の計算のとおり、最後に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が答えです。