算法Day33 不会算数的小明

不会算数的小明

Description

现在有一个数字startValue，小明不会算数，只会以下两种操作：
双倍（Double）：将数字乘2；
递减（Decrement）：将数字减1。
给定两个整数startValue和target。返回显示数字target所需的最小操作数。

Input

输入两个整数startValue和target，startValue和target之间用“ ”隔开，且1≤startValue, target≤10^9

Output

输出startValue得到数字target所需的最小操作数。

Sample

代码

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

            int a = in.nextInt();

            int b = in.nextInt();

            System.out.println(brokenCalc(a,b));

    }
    public static int brokenCalc(int X, int Y) {
        int ans = 0;
        while(Y > X) {
            ans++;
            if (Y%2 == 1) Y++;
            else Y /= 2;
        }
        return ans + X - Y; // 我们还需要执行 X - Y 次加法操作以得到 X
    }

}

思路

假设Y = X*2-1,那么X =(Y+1)*2
x>y有不断减即可，x<y则奇数偶数判断再累加