力扣（坏了的计算机）

991. 坏了的计算器

在显示着数字 startValue 的坏计算器上，我们可以执行以下两种操作：

• 双倍（Double）：将显示屏上的数字乘 2；
• 递减（Decrement）：将显示屏上的数字减 1 。

给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。

思路：

暴力做法是分别尝试乘以2和减一找到其中最小的次数，内部是继续不断递归直到等于target才停止。例图会有点像是一个二叉树，每个分支都是乘二或者减一。

简化的做法是反过来找从target进行加一和除以2的操作的情况下变成startvalue的最小次数。

具体做法如下：

当startvalue小于target的时候，偶数则除以2，奇数则加一变成偶数。

当startvalue大于target的时候，因为除以2只能变小，因此只能一直加一直到start value等于target。

这么做会将多种情况化简成一种情况，即奇数加一，偶数除以2。之所以这样更快，是因为对于一个偶数k，要变成另一个数h，假设是先加在除以2，就是（k+w）/2=h，而先除以再加，就是k/2+w/2=h，第一种做法需要w+1次,第二种需要w/2+1次，因此一定是先除以2再加更优。而对于奇数，必须先加才能除以2.

class Solution {
public:int brokenCalc(int startValue, int target) {int n=0;while(startValue<target){if(target%2==1){target++;n++;}target/=2;n++;}return n+startValue-target;}
};