雁過無(wú)痕

    Trilogy公司的筆試題:

如果n為偶數(shù)，則將它除以2，如果n為奇數(shù)，則將它加1或者減1。問對(duì)于一個(gè)給定的n，怎樣才能用最少的步驟將它變到1。
    例如：n=11： ①　++n -> 12　② n/2 -> 6 ③ n/2 -> 3   ④ --n -> 2  ⑤ n/2 -> 1  共需5步。

最簡(jiǎn)單的方法就是用DP。設(shè)f(n)為所用的最少步驟。根據(jù)定義可得：

若n為偶數(shù)， f(n)=f(n/2) + 1;

若n為奇數(shù)， 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

利用上述遞推公式，可以直接從數(shù)字1開始算到n，用一個(gè)數(shù)組保存前 n/2+1個(gè)數(shù)所用的最少步驟，但這時(shí)間和空間復(fù)雜度均為O(n)，其實(shí)利用上面的遞推公式，可以實(shí)現(xiàn)時(shí)間復(fù)雜度為0(lg n)。觀察上面的遞推公式，可以發(fā)現(xiàn)，要計(jì)算n，只要計(jì)算n/2和n/2+1，如要計(jì)算59，只要計(jì)算：

59 -> 29,30 -> 14,15 -> 7,8 -> 3,4 -> 1,2。

代碼如下：

int num2one_dp(unsigned n)
{
  unsigned tmp=n, flag=1, ret=0, next=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)解法，對(duì)n先處理高位的0和1，下面的O(lg n)解法則恰恰相反，先處理n的低位的0和1。

將n（n>1）轉(zhuǎn)為二進(jìn)制數(shù)表示

（下面的“加1”、“減1”操作均特指對(duì)奇數(shù)采取的操作，操作次數(shù)包括對(duì)偶數(shù)的操作次數(shù)。）

⑴ 如果n僅由m個(gè)連續(xù)的1組成（即n=2^m-1， m>=2），

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

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

       顯然，僅當(dāng)m=2（即n=3）時(shí)，“減1”所用的操作次數(shù)才比“加1”少。

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

（x可以為空串或任意01序列，0_m表示連續(xù)m個(gè)0，1_k表示連續(xù)k個(gè)1)

   ① “加1”操作：  k+1 次操作后得到x10_m-11如果，接著用“減1”操作（注意，這不這一定最優(yōu)解法），總共k+3次操作可得x10_m-1。

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

   顯然，僅當(dāng)k=1時(shí)，“減1”所用的操作次數(shù)才可能比“加1”少。

   可以證明，對(duì)x10_m1，“減1”所用的操作次數(shù)一定不會(huì)比“加1”的多。

   （當(dāng)k=1時(shí)，對(duì)x10_m1，假設(shè)先進(jìn)行一次“加1”操作最終所用的步驟數(shù)較少。“加1”操作后，在將x10_m1轉(zhuǎn)為x11前，若用到“減1”操作，則可以直接對(duì)x10_m1進(jìn)行 “減1”操作，所有步驟更少，因而后面都是采用“加1”操作。

     對(duì)x10_m1（可表示為y01_t0_m1，y允許是空串），

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

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

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

由于對(duì)m>=1，恒有m+t+3 <= 2*m+t+2，因而對(duì)x10_m1

“減1”操作能保證得到最優(yōu)解。）

⑶ 總之，僅當(dāng)n=3或n二進(jìn)制表示的最低2位是01時(shí)，才用“減1”操作

代碼：

int num2one(unsigned n)
{
  if (n==0) return -1;
  int count=0;
  while (1) {
    while ((n&1)==0) { n >>= 1u; ++count; }
    if (n<=3) {
      // n只能為1或3，n為3時(shí)，還要進(jìn)行兩步操作
      count += n - 1;
      break;
    }
    if ((n&3)==1)  --n;
    else ++n;
    ++count;
  }
  return count;
}