平成22年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
W−2
次のC言語のプログラムに関して説明した記述の、  ア  イ  に入る語句
として最も適切な組合せを、@〜Dの中から選べ。
# 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
 A 末尾再帰であるが分割統治ではない   9
 B 末尾再帰ではないが分割統治である   8
 C 末尾再帰ではないが分割統治である   9
 D 末尾再帰でありかつ分割統治でもある  8



【正解】 A

末尾再帰は、再帰関数において、関数の最後のステップで
自分自身を再呼び出すこと。
分割統治法は、ある問題をいくつかの部分に分け、その各部分を再帰的に解き、
最終的に全体の問題を解くというアルゴリズムであり、
クイックソートやマージソートは分割統治を適用したアルゴリズムである。

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)
=
9


EXCELのマクロのご相談なら ファーストマクロ 



W−1 目次 W−3
ファーストマクロ TOPページ