CommonLisp Scheme Part13 - 暇つぶし2ch

CommonLisp Scheme Part13 at TECH

618:デフォルトの名無しさん
05/07/23 10:34:49
求める関数を pow2(x,n), s(x,n)=log_x pow2(x,n) とおくと、pow2 漸化式は次のようになる。

s(0,x)=0
s(2n,x)=2*s(n,x)
s(2n+1,x)=2*s(n,x)+1

ここまで見ると何となく s(n,x)=n になりそうな事が見えて来るが、
帰納法を使わず直観的に考えてみる。
s(n,x)の",x"を以後省略することとし、
nの2進表記を b_n...b_1b_0 とすると

s(b_n...b_1b_0)
=2*s(b_n...b_1)+b_0
=4*s(b_n...b_2)+2*b_1+b_0
...
=2^n*b_n+...+2*b_1+b_0

すなわち s(n)=n となる。
よって pow2(x,n)=x^n である。
故に>>614

次ページ

続きを表示

1を表示