Trilogy公司的笔试题:用最少的步骤将数N转为1

转自 http://blog.csdn.net/flyinghearts/article/details/5665799

Trilogy公司的笔试题:

 

如果n为偶数，则将它除以2，

如果n为奇数，则将它加1或者减1。

问对于一个给定的n，怎样才能用最少的步骤将它变到1。

 

最简单的方法就是用DP。设f(n)为所用的最少步骤。根据定义可得：

若n为偶数， f(n)=f(n/2) + 1;

若n为奇数， f(n)= min(f(n-1), f(n+1)) +1

                     = min(f((n-1)/2), f((n+1)/2)) +2

或者：

 f(2*k)=f(k)+1 

f(2*k+1)=min(f(k),f(k+1))+2

 

利用上述递推公式，可以直接从数字1开始算到n，用一个数组保存前 n/2+1个数所用的最少步骤，但这时间和空间复杂度均为O(n)，其实利用上面的递推公式，可以实现时间复杂度为0(lg n)。观察上面的递推公式，可以发现，要计算n，只要计算n/2和n/2+1，如要计算59，只要计算： 59 -> 29,30 -> 14,15 -> 7,8 -> 3,4 -> 1,2。

int num2one_dp(unsigned n)
{
  if (n == 0) return 0;
  unsigned ret=0;
  while ((n&1) == 0) { n >>= 1u; ++ret; }
  unsigned tmp=n, flag=1, next=ret+1;
  while (tmp >>= 1) flag<<=1;
  while (flag >>= 1) {
    if (n & flag) {
      if (ret > next) ret = next;
      ret += 2;
      ++next;
    } else {
      if (next > ret) next = ret;
      next += 2;
      ++ret;
    }
  }
  return ret;
}

上面的O(lg n)解法，对n先处理高位的0和1，下面的O(lg n)解法则恰恰相反，先处理n的低位的0和1。

 

将n（n>1）转为二进制数表示

（下面的“加1”、“减1”操作均特指对奇数采取的操作，操作次数包括对偶数的操作次数。）

⑴ 如果n仅由m个连续的1组成（即n=2^m-1， m>=2），

① “加1”操作：  需要 m+1 次操作

② “减1”操作：  需要 2*(m-1) 次操作

       显然，仅当m=2（即n=3）时，“减1”所用的操作次数才比“加1”少。

 

⑵ 如果n可以表示为：x10_m1_k （m>=1, k>=1）

（x可以为空串或任意01序列，0_m表示连续m个0，1_k表示连续k个1)

 

   ① “加1”操作：  k+1 次操作后得到x10_m-11如果，接着用“减1”操作（注意，这不这一定最优解法），总共k+3次操作可得x10_m-1。

   ②“减1”操作：  2*k+1次操作后得到x10_m-1

   显然，仅当k=1时，“减1”所用的操作次数才可能比“加1”少。

   可以证明，对x10_m1，“减1”所用的操作次数一定不会比“加1”的多。

   （当k=1时，对x10_m1，假设先进行一次“加1”操作最终所用的步骤数较少。“加1”操作后，在将x10_m1转为x11前，若用到“减1”操作，则可以直接对x10_m1进行 “减1”操作，所有步骤更少，因而后面都是采用“加1”操作。

     对x10_m1（可表示为y01_t0_m1，y允许是空串），

　“加1”操作   2*m+t+2 次后得到  y1

“减1”操作       m+2 次后得到  y01_t

（再用“加1操作”，m+t+3后也可得到y1）

由于对m>=1，恒有m+t+3 <= 2*m+t+2，因而对x10_m1

“减1”操作能保证得到最优解。）

 

⑶ 总之，仅当n=3或n二进制表示的最低2位是01时，才用“减1”操作。

int num2one(unsigned n)
{
  if (n == 0) return 0;
  int count=0;
  while (1) {
    while ((n&1) == 0) { n >>= 1u; ++count; }
    if (n <= 3) {
      // n只能为1或3，n为3时，还要进行两步操作
      count += n - 1;
      break;
    }
    if ((n&3) == 1)  --n;
    else ++n;
    ++count;
  }
  return count;
}