2進法について

質問

0以上の整数ｎについて、
ｎが偶数のときf(n)=f(n/2)
ｎが奇数のときf(n)=f{(n-1)/2}+1
このときf(n)はｎを2進法で表したときの１の個数になると思うのですが、証明する方法がわかりません。
帰納法などで証明できないでしょうか

回答No.4

irija_bari · ベストアンサー

>このときf(n)はｎを2進法で表したときの１の個数になると思うのですが、

どこからこの結論が出てきたのかはわかりませんが、正しいです。

>ｎが偶数のときf(n)=f(n/2)

これは、n=2*m（mは0以上の整数）と考えます。
例えば、m=5であれば、mの2進数表記は101であり、2*mの2進数表記は1010です。
2進数表記でmを2倍するということは、最下位桁に0を追加して元の数を1桁繰り上げるということです。
ですから2倍しても1の個数が変化することはありません。

>ｎが偶数のときf(n)=f(n/2)

これも、m（mは0以上の整数）を使ってnを書き換えてやれば証明可能なはずです。
tomochan1017さんご自身でトライしてみてください。

お礼

奇数の場合もうまく証明できました。
ありがとうございます。

回答No.6

noname#47894

No.5です。補足です。
0以上の整数ｎとのことですので、f(1)=1　はいりませんね。
でも、f(0)=0　がいります。

お礼

ありがとうございました。
いろいろな考え方がありますね。

回答No.5

noname#47894

一応、f(1)=1　が必要ですが...
で、
条件から、ｆ（2^k)の場合について、ｆ（2^k)＝１　がいえるので、
n=2^k　の場合は易しいですね。

n=2^k(1)+2^k(2)+．．．．．＋2^k(i)　のときf(n)＝iを証明すればよいので、

n=2^k(1)のとき、f(n)＝1　（これは最初に言った）

n=2^k(1)+2^k(2)+．．．．．＋2^k(i)　のときf(n)＝i　が成立すれば、
n=2^k(1)+2^k(2)+．．．．．＋2^k(i)＋2^k(i+1)　のときf(n)＝i+1　
が成立することを示してみれば？
（添え字の数についての帰納法です）

やってみたわけではないので、アイデアのみ。
このとき、k(i)>k(i+1)≧0を仮定しておくと良いでしょう。
2^k(i)についてくくると、末尾に１が現れますので、それを使ってください。

回答No.3

looker1986

回答してから気付きましたが、n=A_m*2^(m-1)+A_(m-1)*2^(m-2)+...(A_i=0,1)と表わせることを利用するのかも。

回答No.2

hermite

二進数では、整数のとき
偶数　→　10010　（一番右のけたが0）
奇数　→　10011　（一番右のけたが1)
となる。また、二進数を2で割るとは、
10010　→　1001
のように、右に一桁シフトすること。
よって、
1)偶数のとき
　nを二進数に直したときの1の個数をmとおくと、
　　（1がm個）0
　となるので、2で割ると
　　（1がm個）
　となる。よって、f(n) = f(n/2)である。
2)奇数のとき
　nを二進数に直したときの1の個数をmとおくと
　　（1がm個）1
　となるので、n-1は
　　（1がm個）0
　となる。よってこれを2で割ると
　　（1がm個）
　これに1を加える。n=1000101のように、2桁目が0のときはf(n)=100011と　なるので一致するが、n=1001111のようになっているとf(n)=101000と　なって必ずしも一致しない。f{(n-1)*2}+1とかではないんでしょうか？

お礼

ありがとうございました。

回答No.1

looker1986

実際に具体的な値について計算すればよくわかると思いますよ。
やっていることは、
偶数のときは最下位の桁が０ですから、何もせずに２で割ります。
n=6なら110→11
奇数のときは最下位の桁が１ですから、１引いて２で割ります。
n=3なら11→1
このときにfに１足します。f(n)=f{(n-1)/2}　+1←この部分

帰納法での証明ですが、経験者ではないですが参考までに・・・。
桁数がmのときにf(n)がｎを2進法で表したときの１の個数を表すと仮定して、残りの上位m-1桁の１の個数がf(n/2)もしくはf{(n-1)/2}で表わせることを示せばよいのではないでしょうか。

お礼

ありがとうございました。