算法题一道,欢迎讨论

cjaizss

原帖由 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 ...

这个证明存在跳跃性思维，所以不是严格的数学证明。
再者，1100B只需要4次操作
   1100B
(1)110B
(2)11B
(3)10B
(4)1B

dragonfly0427

7%2=1,
7＋1,
8/2=4,
4/2=2,
2/2=1,

ok,4(=(7+1)/2)

8%2==0,
8/2=4,
4/2=2
2/2=1;

3.

xiaozhu2007

原帖由 cjaizss 于 2008-9-3 01:10 发表

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

高手加油阿！
这种题要是面试的时候问我我还不死翘翘了！

cjaizss

原帖由 xiaozhu2007 于 2008-9-3 11:15 发表

高手加油阿！
这种题要是面试的时候问我我还不死翘翘了！

证明的话，有个东西还没有想通。
至于我验证的结果，已经运行了18:44:40这么长时间，还没算完

qq0001213

int  f(long n)
{
      if(n<=0)
                return   -1;//  error
    if(n<16)
    {
      switch(  n)
            {
                   case 1:   return 0;
                    case 2: return  1;
                   .......................
                   case  16:  return 4 //以上手工计算   其实计算到case 4即可；      

            }
     }

     if(n%2==0)
            {
             return  f(n/2)+1;
            }

     if(  f(n-1)<f(n+1)   )
            return  f(n-1)+1;
       return  f(n+1);   

}

水青虬

此贴一语中的

qq0001213

本身就是一个递归模式， 用归纳法就可以证明了。

cjaizss

原帖由 qq0001213 于 2008-9-3 15:04 发表
本身就是一个递归模式， 用归纳法就可以证明了。

既然是一个算法题，那么就不只是解出正确结果就行了。

qq0001213

我想大家考虑的可能过于复杂了。

对于数值 N  计算步骤 f(N);
我们可以先计算出f(1)-----f(15);//
假设我们计算出f(15) ----f(  N -1  );  
如果N是偶数  F(N)=f( N/2 ) + 1;//  因为 N/2< N-1   f(N/2)已经计算出来确定了   所以F(N)值也就确定了；
如果N是奇数  有两种可能  F(N)=f(  （N+1）/2   ) + 1 或者 F(N)=f(  （ N-1） /2 ) + 1;   （N-1）/2< N-1和 （N+1）/2< N-1
  f（N+1）/2    和 f(  （ N-1） /2 )值确定了 F(N)的值也就确定了；// F(N)取f(  （N+1）/2   ) + 1 和 f(  （ N-1） /2 ) + 1两者中较小的就可以了;


这样F（N）的值也就可以确定了

bood

原帖由 qq0001213 于 2008-9-3 15:42 发表
我想大家考虑的可能过于复杂了。

对于数值 N  计算步骤 f(N);
我们可以先计算出f(1)-----f(15);//
假设我们计算出f(15) ----f(  N -1  );  
如果N是偶数  F(N)=f( N/2 ) + 1;//  因为 N/2< N-1   f(N/2)已 ...

恩，算法是对的，但是效率没有前面的高