算法题一道,欢迎讨论

huachong

哎，还是我老婆聪明
f(n)=1+f(n/2+n%2)

xiaozhu2007

不要结果要思路!

bood

y=z=1 x=0得时候还是应该+1
进位可能对高位有帮助，考虑111011就知道了

补充：但是对11而言还是应该-1

[ 本帖最后由 bood 于 2008-9-2 10:26 编辑 ]

bood

思路就是搞清楚末尾有几个1得时候才值得+1，不然就是浪费操作
不过目前结论都有小问题……（包括我刚发的）

bood

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

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

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

修改一下：
x=0, y=z=1的时候+1（此时必须n>3，否则-1）
这样应该没问题了

结论就是：
n%2=0，则f(n)=f(n/2)+1
(n+1)%4=0 && n>3，则f(n)=f(n+1)+1=f((n+1)/4)+3
其他情况，则f(n)=f(n-1)+1=f((n-1)/2)+2
最后，f(1)=0

emacsnw

原帖由 bood 于 2008-9-1 18:39 发表


修改一下：
x=0, y=z=1的时候+1（此时必须n>3，否则-1）
这样应该没问题了

结论就是：
n%2=0，则f(n)=f(n/2)+1
(n+1)%4=0 && n>3，则f(n)=f(n+1)+1=f((n+1)/4)+3
其他情况，则f(n)=f(n-1)+1=f((n-1 ...

这个应该是正解了，呵呵。

jronald

设这个数为i，作如下循环
int cnt=0;
while (i!=1) {
  cnt += i & 1 + 1;
  i>>1;
}

要优化的话，汇编的移位指令正合适。

[ 本帖最后由 jronald 于 2008-9-2 14:16 编辑 ]

emacsnw

原帖由 jronald 于 2008-9-1 19:48 发表
设这个数为i，作如下循环
int cnt=0;
while (i!=1) {
  if (bit0==1)
    ++cnt;
  i>>1;
  ++cnt
}

要优化的话，汇编的移位指令正合适。

这不是死循环么。

嗯，楼上的改掉了。。。
主要还是要考虑 +1 还是 -1， 楼上的代码不是始终是 -1 么。

jronald

原帖由 emacsnw 于 2008-9-2 11:51 发表


这不是死循环么。

嗯，楼上的改掉了。。。
主要还是要考虑 +1 还是 -1， 楼上的代码不是始终是 -1 么。

正整数，-1就可以啊。

cjaizss

没有一个人严格证明了自己的算法，所以即便步骤对，也不完整。