算法题一道,欢迎讨论

qq0001213

如果想要高的效率  用循环和数组就可以了  可以把F（N）的值用数组存储起来直接查就行了。大部分计算就可以省了

bood

原帖由 qq0001213 于 2008-9-3 16:23 发表
如果想要高的效率  用循环和数组就可以了  可以把F（N）的值用数组存储起来直接查就行了。大部分计算就可以省了

前面的不一样么-_-
但是前面的比你少算很多阿
比如f(19)，你需要计算f(20/2)和f(18/2)，前面的算法只需要计算f(20/2)即可

jhkwei

想来想去，只有化成二进制，加一减一，看谁能得到更多的0,0越多消化的迅速越快!

4tar

随便写了个解法：http://blog.chinaunix.net/u/11350/showart_1163470.html

shan_ghost

int f(int64 n)
{
    assert(n>=1);

    int res=0; //记录结果

    while (n!=1)
    {
         if (n&1 == 0) //末位为0直接右移
         {
              n/=2;
              res++; //一次操作
         }
         else if (n&7 == 7)
         {
              //末3位为1加一（因为序列内部的11收支平衡；序列头部的111收支平衡；更长的序列正收益更大）
              n++;
              //直接消尾部3个0
              n/=8;
              res+=4; //一次自增3次右移
         }
         else
         {
              //末3位不全为1则减一（序列内部的11收支平衡，加一减一均可）
              n--;
              n/=2;
              res+=2; //一次自减一次右移
          }
    }
    return res;
}


对于int64所能表示的最大整数(如果次高位加1不溢出的话)，此算法最多需要63次循环；算法复杂度最大O(ln(N))。

关于收益方面的分析证明见我在第四页的回帖；这个实现是尾部向前搜索且做了实际计算的，和分析不太一样；分析中至少需要扫描全部位，这个实现遇见3个以上的连续1可以直接处理3位。


更“优化”的版本可以这样写：
if (n&7 == 7)
{
    if (n&15 == 15)
    {
         if (n&31==31)
         {
             if(n&63=63)
             ......
         }
             n++;
             n>>4;
             res+=5;
             continue;
    }
    n++;
    n>>3;
    res+=4;
    continue;
}

不过，这个做法虽然确实可以减少循环次数，但并不一定能实际减少所需的指令数以及执行时间，也不能降低算法复杂度。

[ 本帖最后由 shan_ghost 于 2008-9-4 10:01 编辑 ]

shan_ghost

修正一下： 最后的那个“优化”，算法的“平均复杂度”还是有所降低的；但最大复杂度不变。

cjaizss

原帖由 shan_ghost 于 2008-9-4 09:56 发表
int f(int64 n)
{
    assert(n>=1);

    int res=0; //记录结果

    while (n!=1)
    {
         if (n&1 == 0) //末位为0直接右移
         {
              n/=2;
              res++; //一次 ...

在把代码贴出来之前，我觉得你至少应该编译一遍，运行一遍。
而你，却没有这么去做。
另外，我对你代码做了一点小的修改后（你本来的代码写错了，会是一个死循环，所以我认为你根本没编译验证过），算出来的59的次数是9,其实应该是8。
今天晚上回去，我把我的算法的证明贴出来吧

[ 本帖最后由 cjaizss 于 2008-9-4 10:24 编辑 ]

ring8595

我觉得这个题目可以用移位
除二 其实就是向右移位～
判断奇数和偶数 直接用第一位判断～
那么现在就是找最高位的1就可以了～

最高位的1其实就可以用 2 4 8 16 32 64 128 256 ~~~~这类来比较 就出来了～

shan_ghost

原帖由 cjaizss 于 2008-9-4 10:21 发表

在把代码贴出来之前，我觉得你至少应该编译一遍，运行一遍。
而你，却没有这么去做。
另外，我对你代码做了一点小的修改后（你本来的代码写错了，会是一个死循环，所以我认为你根本没编译验证过），算出来的 ...

随手写的。。除了浏览器外，没有经过其他介质。


死循环是溢出/绕回吧？这个我知道。说明原理而已，没有考虑边界情况。



前面确实有一点没有考虑到： 59 = 111011B，加一后变成111100B，这可以抵消头部111序列的一次加1。

所以，之前的分析中应该增加这样一条： 非序列首部的11加一减一收支平衡，但应该优先加一，因为有可能抵消更前面连续1序列的一次加一操作。

或者，这样考虑：凡....11011...这样的序列，需要额外3次操作（而不是原来估计的四次）；而00101100这样的序列收支平衡（亦即：和前面的分析一样，需要3次操作）。
其中，上面序列中的.代表0或1。


这样的话，应加一个记录，识别首部为11这种情况——此时要为计算次数减1：
int f(int64 n)
{
    assert(n>=1);

    int res=0; //记录结果
   int isFirstSeqLengthLess3=0; //首部是11吗？

   while (n!=1)
    {
         isFirstSeqLengthLess3=0; //首部不是11或还未找到首部

         if (n&1 == 0) //末位为0直接右移
         {
              n/=2;
              res++; //一次操作
         }
         else if (n&3 == 3)
         {
              //末2位为1加一（因为序列内部的11收支平衡，但加一可能抵消下一序列的加一操作；更长的序列收益更大）
         n++;
              //直接消尾部2个0
              n/=4;
              res+=3; //一次自增2次右移
         isFirstSeqLengthLess3=1; //若此次执行过后while退出，则首部肯定是11序列
      }
         else
         {
              //末2位为01则减一
         n--;
              n/=4;
              res+=3; //一次自减2次右移
      }
    }
    res-=isFirstSeqLengthLess3;
    return res;
}


当然，仍然没有编译运行过……




另，这和你的思路其实是一样的：1个1只能自减；2个1可加可减，但若前面是10，则加至少可以收支平衡（是110则有盈余）。

我是因为一直不甘心O(ln(n))的效率（且有之前的分析引导），代码过早优化了；在你的代码的//1处加上两次右移，则我们的代码等价。

int get2(int n)
{
        int ret=0;
        int t;
        while(n!=1) {
                if(n&1) { //若末位为1
                        if((n&3)!=3 || (n&15)==3) { //若末2位是01或0011则自减消末位1
                                n--;
                        } else { //否则（末位是1011或1111）自加消末位1
                                n++;
                                //1 这里可以直接n/=4消掉末2个0，少两次循环；当然，res要+2了
                        }
                } else {  //末位为0则右移
                        n/=2;
                }
                ret++;
        }
        return ret;
}

嗯，当然，本人很懒，仍然没有运行过上面这段代码……

[ 本帖最后由 shan_ghost 于 2008-9-4 13:05 编辑 ]

cjaizss

原帖由 shan_ghost 于 2008-9-4 13:03 发表


随手写的。。除了浏览器外，没有经过其他介质。


死循环是溢出/绕回吧？这个我知道。说明原理而已，没有考虑边界情况。



前面确实有一点没有考虑到： 59 = 111011B，加一后变成111100B，这可以抵 ...

可是我的代码我已经经过了测试，但是在还没证明之前，我还不敢说我的算法是对的
死循环在于你的代码中搞错了运算符的优先级

[ 本帖最后由 cjaizss 于 2008-9-4 13:09 编辑 ]