プログラミングの基礎(擬似言語のトレース)
÷ は除算で、整数型の変数(引数を含む)に代入するときは小数点以下を切り捨てる。次の関数 pow を pow(2, 10) として呼び出したとき、pow が呼ばれる回数(最初の呼出しを含む)はどれか。
○整数型: pow(整数型: x, 整数型: n)
if (n = 0)
return 1
endif
整数型: h ← pow(x, n ÷ 2)
if (n mod 2 = 0)
return h × h
endif
return h × h × x- A5
- B10
- C11
答えと解説を見る
正解：A. 5
pow(x, n) は x の n 乗を、n を半分にした pow(x, n ÷ 2) の結果を2乗して求めます(n が奇数なら、さらに x を掛けます)。n は 10、5、2、1、0 と変わり、n = 0 で再帰が止まるので、呼ばれる回数は5回です。戻り値は 2¹⁰ = 1024 です。x × pow(x, n − 1) のように n を1ずつ減らすと、n = 10 から0まで11回呼ばれます。n を半分ずつにすると、呼出しの回数はおよそ log₂ n に比例します。
- A. 正しい。n = 10、5、2、1、0 の5回です。
- B. 指数 n = 10 の値です。n は1ずつではなく半分ずつ減ります。
- C. n を1ずつ減らす再帰(x × pow(x, n − 1))の場合の呼出しの回数です。