算法题一道,欢迎讨论

cjaizss

想错了

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

wzcsoft

代码就不写了，本人就说一说思路。
把所有数换成2进制，偶数就不用说了，除2一条路，关键是奇数

1111111这个数大家觉得+1好还是-1好？？  显然是+1 因为+1后变成了10000000，我们一路除以2就Ok，这是最快的，因为除2就是向右移，就是在以最快的速度接近1

10011111这个数是+1好还是-1好？还是+1。因为+1 -1 都不改变总的位数，而+1就成了1010000,相当于把5个1只用了1步就变成了1个1，这样多爽

100001这种情况-1，原因很显然

但是要注意临界情况10011 +1  -1是一样的，原因是用了一步把两个1变成了1个1（10100），所以+1 -1没区别，但这时候并不影响我们的结果

但是11这种情况接不一样了，这个时候应该-1  原因是+1没有了优势，同时怎加了位数长度。这个时候会影响结果，这是真正的临界情况             --wzcsoft

wzcsoft

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

11这个临界你LP就错了，哈哈

jazy333

牛人就是多啊

shan_ghost

先考虑2的幂的情况。显然，2^n至少需要n次右移操作。

任何整数，最终都可归结为一系列2的幂相加；如1100B = 0 × 2^0 + 0 × 2^1 + 1 × 2^2 + 1 × 2^3

如果仅允许右移和自减（减一）操作，那么显然1100B至少需要右移3次、减1一次，共4次操作。
即：使用右移消低位0，使用减一消低位1，共需二进数字长度减一次移位，还需要除了最前面的1外，数字中一共含有的1的个数次自减操作。

这个可以叫做判断规则1。




考虑自增（加一）操作：现在，游戏变成了如何用最少的步骤消除二进制数字中的连续几个1。


例如，1100B可以在右移2次后，通过加一得到100，再右移2次得到1，共需5次操作。

这会比右移二次后自减多一次操作，原因是加一导致移位次数增加一次。


但，对11100B或1001100B来说，右移两次后加一、然后继续移位和单纯的右移+自减方式需要的操作次数一样多。

所以，有：
1、对于数字低位的连续m个1，使用加一可把它们变成高一位的一个1，因此总体上只需两次操作即可消除（单纯的减一、移位再减一则在总体上需要1的个数次操作）
   进而，有：
      1.1 只要m大于2，使用自增可以得到正的收益。
      1.2 m等于2时收支相抵，使用自增或自减均可。
      1.3 m小于2只能用自减
2、对于数字首位的连续m个1，使用加一同样可以把它们变成高一位的一个1，但相比低位的情况将导致额外增加一次右移操作。
   所以，当m>3时才有正的收益；m=3收支相抵；m<3只能用自减。
3、只要m达到非负收益范围，那么不管这个连续1的序列有多长，都可以用两次额外操作消除（自增，然后在这个序列之前一位上应用自减）



比如，对7，有：

7写成二进制，是 111B；因为111在首位，因此自增或自减均可。

自增，则成为1000B；3次右移后就等于1，共需4次操作。
自减，成为110B，右移，得11B,再自减、右移，得1，同样需要4次操作。

用上面的判定规则，就是：
1、111B是从开头就有连续3个1，属于非负收益范围，因此需要额外2次操作。
2、111B一共3个二进制位，因此需要3-1=2次移位操作。

所以，111B至少需要4次操作。


算法：

从最高位开始扫描二进制数字。
若最高位开始有连续两个1，记需要一次额外操作；连续3个1或更多，都需要额外两次操作。
while(未扫描到最低位)
{
        在剩下的数字中，发现1就记需要一次额外操作；连续2个1或更多，记需要额外2次操作，直到遇到0或结束为止。
}
假设前面扫描中记录的额外操作次数记为x，二进制数字有效位数为y，则返回至少需要x+y-1次扫描。


当然，从低位扫描也可以，没有原则上的不同。



有了算法，我们可以玩个复杂点的：
424367，转换为二进制是：1100111100110101111B

因为这个数字最前两位是11，需要额外一次操作消除第二个1。

然后，从前往后数，它的第5到第8位是连续4个1，需要两次操作才能消除；11到12位两次；14位需一次操作；最后4个1需要两次操作。

于是，为了消除首位后面的这些1，共需8次操作；这个数字共19个有效二进制位，需要19-1=18次移位操作。

答案是：至少需要26次操作。


这个算法只需1次扫描，无任何实际运算。复杂度为O(ln(N))

[ 本帖最后由 shan_ghost 于 2008-9-2 15:28 编辑 ]

cjaizss

1. 
   
2. int get2(int n)
   
3. {
   
4.         int ret=0;
   
5.         int t;
   
6.         while(n!=1) {
   
7.                 if(n&1) {
   
8.                         if((n&3)!=3 || (n&15)==3) {
   
9.                                 n--;
   
10.                         } else {
    
11.                                 n++;
    
12.                         }
    
13.                 } else {
    
14.                         n/=2;
    
15.                 }
    
16.                 ret++;
    
17.         }
    
18.         return ret;
    
19. }
    

复制代码

尚未证明，但是测100w以下没有任何问题

因为构造了一个递归算法（这个应该没问题）:

1. 
   
2. int get(int n,int s)
   
3. {
   
4.         int step=0;
   
5.         int b=n;
   
6.         if(b==1)
   
7.                 return s;
   
8.         if(b%2)
   
9.         {
   
10.                 step=get(b+1,s+1);
    
11.                 int st=get(b-1,s+1);
    
12.                 if(step>st) {
    
13.                         step=st;
    
14.                         //printf("**n+1=%d\n",b+1);
    
15.                 } else {
    
16.                         //printf("**n-1=%d\n",b-1);
    
17. 
    
18.                 }
    
19.         }
    
20.         else
    
21.         {
    
22.                 b=b/2;
    
23.                 step=get(b,s+1);
    
24.                 //printf("**n/2=%d\n",b);
    
25.         }
    
26.         return step;
    
27. }
    
28. 
    

复制代码

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

xiaozhu2007

原帖由 cjaizss 于 2008-9-2 16:33 发表

int get2(int n)
{
        int ret=0;
        int t;
        while(n!=1) {
                if(n&1) {
                        if((n&3)!=3 || (n&15)==3) {
                                n- ...

你是如何知道100w以下没有任何问题？有测试用例吗？

xiaozhu2007

原帖由 shan_ghost 于 2008-9-2 15:21 发表
先考虑2的幂的情况。显然，2^n至少需要n次右移操作。

任何整数，最终都可归结为一系列2的幂相加；如1100B = 0 × 2^0 + 0 × 2^1 + 1 × 2^2 + 1 × 2^3

如果仅允许右移和自减（减一）操作，那么显然1100 ...

看明白了！强人一个啊！
这个思路是正确的！

[ 本帖最后由 xiaozhu2007 于 2008-9-3 00:24 编辑 ]

cjaizss

原帖由 xiaozhu2007 于 2008-9-2 23:48 发表

你是如何知道100w以下没有任何问题？有测试用例吗？

我写了一个程序,可以算所有的32位有符号整数中的所有正数.
明天去看运行的结果
至于证明嘛,我想我应该可以给出来。