算法题一道,欢迎讨论

bood

nod，/2其实就是移位
记n的二进制位数为f(n)，其中1的个数为g(n)
那么次数就是f(n)+g(n)-2
于是最快的做法就是建索引表了

xiaozhu2007

哎回去了,晚上接着想,做这种题好累啊!

gtkmm

原帖由 bood 于 2008-9-1 17:08 发表
nod，/2其实就是移位
记n的二进制位数为f(n)，其中1的个数为g(n)
那么次数就是f(n)+g(n)-2
于是最快的做法就是建索引表了

比如有个数的二进制是：
111111.......111（总之很多个了，比如100个）
则f(n)+g(n)-2＝198

实际上，先加1，变成：
10000...0000000( 100个0)
除100次2就可以了。
于是需要101次。

并不是你的198次。。。

bood

有道理，我错了，那应该是这样：
记f(n)为n需要的最少次数，则
如果n是偶数，f(n)=f(n/2)+1
如果n是奇数，则考虑n二进制表示的末尾1得个数，至少有3个1的时候+1才不会造成多余的次数，即n+1可以被8整除
因此，如果(n+1) mod 8=0，f(n)=f(n+1)+1=f((n+1)/8 )+4
否则，f(n)=f(n-1)+1=f(n/2)+2

复杂度log(n)

[ 本帖最后由 bood 于 2008-9-1 20:28 编辑 ]

kkndmammoth

n的二进制表示1xxxxxxxx，设为k位。

题目的意思是用加减和移位消除最高位的1以外的所有的1。
若x都是零，显然只需要k-1次。

当x不全为零，下面的算法应该是最少
设最低三位位为xyz
z=0     则下一步操作是移位 （除2）
z=1 且 y=0  则下两步操作是 减1 再 移位
z=1 且 y=1  且 x=0  则下一步 减1 或 加1 都一样
z=1 且 y=1  且 x=1  则下一步加1

bood

原帖由 kkndmammoth 于 2008-9-1 20:21 发表
n的二进制表示1xxxxxxxx，设为k位。

题目的意思是用加减和移位消除最高位的1以外的所有的1。
若x都是零，显然只需要k-1次。

当x不全为零，下面的算法应该是最少
设最低三位位为xyz
z=0     则下一步操 ...

恩，跟我得差不多了，但是其实应该是
x=y=z=1的时候，+1 -1才是一样的
比如7，两种办法得到的结果都是4

shmild

显然要用位移操作最高效

selfrun

位操作，复杂度log(log(n))

xiaozhu2007

原帖由 kkndmammoth 于 2008-9-1 20:21 发表
n的二进制表示1xxxxxxxx，设为k位。

题目的意思是用加减和移位消除最高位的1以外的所有的1。
若x都是零，显然只需要k-1次。

当x不全为零，下面的算法应该是最少
设最低三位位为xyz
z=0     则下一步操 ...

能否解释下为什么要这么算?