平成25年度 技術士第一次試験問題【専門科目】
【16】情報工学部門
V−3
x を n 乗するべき乗関数 power(x, n)をC言語で実装したい。
べき乗を分解して、O(n)の計算量をO(log2(n))まで削減する実装として
空欄     に入る最も適切なものはどれか。
ただし、n は0以上の整数とする。

 double power(double x, int n) {
  if (n == 0) return 1;
     
 }

 @ int i;
   double rv = x;
   for (i = 1; i < n; i += 1) rv *= x;
   return rv;
 A if n % 2 == 0: return power(x * x, n / 2)
   return x * power(x, n - 1)
 B if n % 2 == 0: return power(x * x, n / 2);
   return x * power(x, n - 1);
 C if (n == 1) return x;
   return x * power(x, n - 1);
 D if (n == 1) return x;
   return x * power(x, n / 2);




【正解】 B
計算量は コンピュータが処理する速さの目安のこと。

n = 8のとき 8回
ぐらい計算するのなら 計算量は O(n)である。

n = 8のとき 3回( =log28 )
ぐらい、n = 16のとき 4回( =log216 )ぐらい計算
するのなら、計算量は O(log2n)である。

選択肢それぞれについて、n = 8の時に何回計算するかを調べる。

@ for (i = 1; i < 8; i += 1) だから8回ループする。
 1回目 x = x * x
 2回目 x = x2 * x2 = x4
 3回目 x = x4 * x4 = x8
 4回目 x = x8 * x80 = x16
 ・・・
 8回目 x = x256
 で、x の n 乗が計算できない。
A Bと同じアルゴリズムだが、構文エラーである。
B power(x, 8) = power(x*x, 4) = power(
x*x*x*x, 2)
 = power(x*x*x,*x * x*x*x*x, 1) =
power(x8, 1)
 = x8 * power( x8, 0) = x8
* 1
 となり、return の時に計算する数が4回となるので、正しい。
C power(x, 8) = x * power(x, 7) = x*x * power(x, 6)
 = x*x*x * power(x, 5) = ・・・ = x*x*x*x*x*x*x *
power(x, 1)
 = x*x*x*x*x*x*x *
x
 で、return の時に計算する数が8回となり、計算量は O(n)である。
D power(x, 8) = x * power(x, 4) = x * (x *
power(x, 2))
 = x * (x * (
x * power(x, 1)))= x * (x * (x * x)) 
 で、x の n 乗が計算できない。


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



V−2 目次 V−4
ファーストマクロ TOPページ