本文へスキップ

技術士試験(情報工学部門)・情報技術者試験。ファーストマクロ。


Since 2016.4.19

平成22年度 技術士第一次試験問題【専門科目】

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)

if ( x == 1 || y >= 25 ) return y; により、
f(1, 9) = 9

W−1 目次 W−3