再帰関数と mod を使った最大公約数の問題を解く
今回は、基本情報技術者試験でよく出る 再帰関数 の問題です。
問題文だけを見ると難しそうですが、実はこの関数は有名な ユークリッドの互除法 です。
つまり、やっていることは
2つの整数の最大公約数を求める処理
です。
問題
整数 x, y（x ≧ y ≧ 0）に対して、次のように定義された関数 F(x, y) がある。
F(231, 15) の値は幾らか。
ここで、x mod y は x を y で割った余りである。
F(x, y) =
x （y = 0 のとき）
F(y, x mod y) （y > 0 のとき）選択肢
ア 2
イ 3
ウ 5
エ 7まず、この関数が何をしているか
この関数 F(x, y) は、次のルールで動きます。
y が 0 なら、x を答えとして返す
y が 0 でなければ、F(y, x mod y) をもう一度計算するポイントは、次の部分です。
F(y, x mod y)これは、次のように値を入れ替えながら計算します。
新しい x = 今の y
新しい y = 今の x を 今の y で割った余りつまり、割り算の余りを使って、数字をどんどん小さくしていきます。
mod とは何か
x mod y は、x を y で割ったときの 余り です。
例えば、
231 mod 15は、
231 ÷ 15 = 15 余り 6なので、
231 mod 15 = 6です。
実際に F(231, 15) を計算する
最初は、次の状態です。
F(231, 15)このとき y は 15 です。
y = 150ではないので、次の式を使います。
F(x, y) = F(y, x mod y)つまり、
F(231, 15)
= F(15, 231 mod 15)231 mod 15 を計算します。
231 ÷ 15 = 15 余り 6したがって、
F(231, 15)
= F(15, 6)2回目の計算
次は、
F(15, 6)です。
y は 6 です。
y = 60ではないので、また同じルールを使います。
F(15, 6)
= F(6, 15 mod 6)15 mod 6 を計算します。
15 ÷ 6 = 2 余り 3したがって、
F(15, 6)
= F(6, 3)3回目の計算
次は、
F(6, 3)です。
y は 3 です。
y = 3まだ0ではありません。
F(6, 3)
= F(3, 6 mod 3)6 mod 3 を計算します。
6 ÷ 3 = 2 余り 0したがって、
F(6, 3)
= F(3, 0)y が 0 になったら終了
最後に、
F(3, 0)になりました。
このとき y は 0 です。
問題文の定義では、
y = 0 のとき、F(x, y) = xなので、
F(3, 0) = 3となります。
計算の流れをまとめる
全体の流れは、次のようになります。
F(231, 15)
= F(15, 231 mod 15)
= F(15, 6)
= F(6, 15 mod 6)
= F(6, 3)
= F(3, 6 mod 3)
= F(3, 0)
= 3したがって、答えは
3です。
正解は、
イ 3です。
この問題の正体は「ユークリッドの互除法」
この関数は、2つの整数の 最大公約数 を求める処理です。
最大公約数とは、2つの数をどちらも割り切れる数のうち、最大のものです。
231 と 15 について考えると、
231 = 3 × 77
15 = 3 × 5どちらも 3 で割れます。
そして、この2つの最大公約数は 3 です。
つまり、
F(231, 15) = 3という結果になります。
初心者がつまずきやすいポイント
この問題で難しく感じる原因は、関数が自分自身を呼び出していることです。
F(y, x mod y)このように、自分自身をもう一度呼び出す関数を 再帰関数 といいます。
ただし、この問題では難しく考えすぎなくて大丈夫です。
次のように、表にして追いかけると分かりやすくなります。
現在の F(x, y) x mod y 次に呼び出す関数
------------------------------------------------
F(231, 15) 231 mod 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) 終了 答えは 3再帰の問題では、
今の x は何か
今の y は何か
x mod y は何か
次の F はどうなるかを1行ずつ書くのがコツです。
覚え方
この問題は、次のように覚えるとよいです。
F(x, y) = F(y, x mod y)これは、
大きい数と小さい数を使って、
余りを出し、
小さい数と余りでまた同じことをするという処理です。
そして、余りが0になったとき、残っている数が最大公約数です。
今回でいえば、
231 ÷ 15 の余りは 6
15 ÷ 6 の余りは 3
6 ÷ 3 の余りは 0余りが0になったときの割る数が 3 なので、答えは 3 です。
まとめ
問題3-7の関数 F(x, y) は、再帰を使って最大公約数を求める関数です。
今回の計算は、次のようになります。
F(231, 15)
→ F(15, 6)
→ F(6, 3)
→ F(3, 0)
→ 3したがって、正解は
イ 3です。
このタイプの問題では、頭の中だけで考えず、必ず表にして
x
y
x mod y
次の Fを順番に追いかけることが大切です。