再帰的関数 ２進数の１の個数

質問

f(x)=if x=0 then 0

else if divisible(x,2) then f(x/2) else f(x/2)+1

divisibleは２で割り切れる、x/2は整除です。２で割ったときの整数値

この式が、xを２進数であらわしたときの１の数を表す、というのですが、
式に数値を入れてみても、１の数にならず困っています。

ご指導いただけましたら幸いです。
よろしくお願い申し上げます。

回答No.2

Picosoft · ベストアンサー

こんにちは。

No.1の方への補足を拝見しますと、
f(x/2)+1ではなく(x/2)+1という計算をしてしまっているようです。

f(7)=3+1ではなく、f(7)=f(3)+1と計算すべきです。

f(7)=f(3)+1
↓　f(3)=f(1)+1
↓　↓　f(1)=f(0)+1
↓　↓　↓　f(0)=0
↓　↓　f(1)=0+1=1
↓　f(3)=1+1=2
f(7)=2+1=3

お礼

ご回答ありがとうございます。

とても分かりやすく理解できました。

問題のf( )= と =が付けられるのも不思議です。

情報の世界は不思議なことが多いですね。

回答No.1

asuncion

＞式に数値を入れてみても、１の数にならず困っています。

どんな数値を入れたときにお困りですか？

補足

ご回答ありがとうございます。

例えば、ｘに７を入れますと２で割りきれませんので、３＋１＝４になります。

しかし、７の２進数は、１１１ですから３です。

４にしてしまう私のミスを教えていただけますでしょうか？

よろしくお願い申し上げます。