次のＣ言語のプログラムに関して説明した記述の、 ア 、 イ に入る語句として最も適切な組合せを、①～⑤の中から選べ。
# include <stdio.h>
int f(int x, int y) {
if ( x == 1 || y >= 25 ) return y;
else if ( x % 2 ) return f(3 * x + 1, y + 1);
else return f(x / 2, y + 1);
}
int main(void) {
int k;
k = f(6, 1);
printf("%d\n", k);
return 0;
}
関数 f の定義は ア 。このプログラムを実行して得られる出力は イ となる。
ア イ
① 末尾再帰であるが分割統治ではない 8
② 末尾再帰であるが分割統治ではない 9
③ 末尾再帰ではないが分割統治である 8
④ 末尾再帰ではないが分割統治である 9
⑤ 末尾再帰でありかつ分割統治でもある 8
②
末尾再帰は、再帰関数において、関数の最後のステップで自分自身を再呼び出すことである。
分割統治法は、ある問題をいくつかの部分に分け、その各部分を再帰的に解き、最終的に全体の問題を解くというアルゴリズムであり、クイックソートやマージソートは分割統治を適用したアルゴリズムである。
x % 2 は xを2で割った余りを求める演算であり、余りが0なら偽で f(x / 2, y + 1) を返し、余り1 (すなわち0以外) なら真で、f(3 * x + 1, y + 1) を返す。
f(6, 1) = f(6 / 2, 1 + 1) = f(3, 2)
= f(3 * 3 + 1, 2 + 1) = f(10, 3)
= f(10 / 2, 3 + 1) = f(5, 4)
= f(3 * 5 + 1, 4+ 1) = f(16, 5)
= f(16 / 2, 5 + 1) = f(8, 6)
= f(8 / 2, 6 + 1) = f(4, 7)
= f(4 / 2, 7 + 1) = f(2, 8)
= f(2 / 2, 8 + 1) = f(1, 9)
if ( x == 1 || y >= 25 ) return y; により、
f(1, 9) = 9
| Ⅳ－１ | 目次 | Ⅳ－３ |