□投稿者/ らすかる 一般人(41回)-(2014/03/15(Sat) 20:09:26)
 | では
> [x/2]はxを2で割った商を表すので、a_nはNを2^{n-1}で割った商である
これがわからないということですね？
おそらく
Nを2で割って、商の整数部を2で割って、その商の整数部を2で割った商と
Nを2^3で割った商が等しいということが言えるかどうか直感的にわからない
といった意味だと思いますが、この例で言えば
1回目に割った余りは1/2以下なので
余りも含めてもう一度割ると、1回目の余りは半分になって1/4以下となります。
それに2回目の余り（1/2以下）を足しても1未満ですから、
結局「2で割った商をさらに2で割った商」と「2^2で割った商」は
必ず同じになります。
さらにもう1回2で割ると、
最後の余り≦1/2
その前の余りの半分≦1/4
その前の余りの1/4≦1/8
ですから、これをいくら繰り返しても余りの合計が1に達することはありません。
よって「2で割って小数部を切り捨てる」をn回行った結果と
「2^nで割って小数部を切り捨てる」の結果は等しくなります。
他の説明も書いてみます。
「2で割る」が「10で割る」だと、多分直感的にわかりやすいと思います。
例えば N=314159265 だとすると
[N/10]=[31415926.5]=31415926
[[N/10]/10]=[3141592.6]=3141592
[[[N/10]/10]/10]=[314159.2]=314159
[[[[N/10]/10]/10]/10]=[31415.9]=31415
[[[[[N/10]/10]/10]/10]/10]=[3141.5]=3141
[[[[[[N/10]/10]/10]/10]/10]/10]=[314.1]=314
[[[[[[[N/10]/10]/10]/10]/10]/10]/10]=[31.4]=31
[[[[[[[[N/10]/10]/10]/10]/10]/10]/10]/10]=[3.1]=3
つまり「10で割った整数部」というのは「最下位1桁を除いた数」ですから、
8回繰り返せば当然3になります。一方
[N/10^8]=[3.14159265]=3
つまり「10^8で割った整数部」というのは「下位8桁を除いた数」ですから
「10で割った整数部」を8回と結果が同じになります。
2進法で考えれば「2で割った場合」も全く同じように説明できますが、
2進法に慣れていない場合は直感的にはわかりにくいかも知れませんね。
|
|