50: Count Conversion Operations 证明

uuuouou

令f(n)表示从0经过(a)和(b)两种操作到达n的最少步骤，则由题意我们可以得出：
（1）如果n是奇数，则显然有f(n) = f(n-1)+1，即最后一步必须是操作(b)，这是因为如果最后一步是操作(a)，乘2，我们不可能得到一个奇数
（2）如果n是偶数，则有f(n) = min(f(n/2), f(n-1))+1，由于n-1是奇数，由（1）知f(n-1) = f(n-2)+1，所以
f(n) = min(f(n/2), f(n-2)+1)+1

到底是先减2好呢，还是先除以2好呢，贪心的知觉告诉我们先除好，因为除了之后得到的数更小，通过数学归纳法，我们可以证明知觉是对的：
考虑base的情况，我们有
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 3
可以看到f(4) = min(f(2), f(2)+1)+1 = f(2)+1，所以对于4，最后一步是操作(a)更优，也即f(4) = f(4/2)+1

假设对于n=2k，满足f(n) = f(n/2)+1，即f(2k) = f(k)+1，对于n = 2k+2的情况，通过上面的讨论（2）有
f(2k+2) = min(f(k+1), f(2k)+1)+1
将f(2k) = f(k)+1带入，则有
f(2k+2) = min(f(k+1), f(k)+2)+1,
又因为k+1可由k通过操作(b)达到，所以f(k+1) <= f(k)+1 < f(k)+2，从而
f(2k+2) = f(k+1) + 1

所以对于n为偶数的情况，有f(n) = f(n/2)+1，结合上面的讨论（1）就可以写代码了：

1. class Solution {
   
2. public:
   
3.     int countOperations(int n) {
   
4.     int step = 0;
   
5.     for(; n; ++step){
   
6.         if(n & 1) --n;
   
7.         else n >>= 1;
   
8.     }
   
9.     return step;
   
10.     }
    
11. };

复制代码