腾讯2018——数字转换机

朴灿烈づ我的快乐病毒、 2022-02-24 14:16 297阅读 0赞

【题目】  
小Q从牛博士那里获得了一个数字转换机，这台数字转换机必须同时输入两个正数a和b，并且这台数字转换机有一个红色的按钮和一个蓝色的按钮：  
当按下了红色按钮，两个数字同时加1。  
当按下了蓝色按钮，两个数字同时乘2。  
小Q现在手中有四个整数a，b，A，B，他希望将输入的两个整数a和b变成A，B（a对应A，b对应B）。  
因为牛博士允许小Q使用数字转换机的时间有限，所以小Q希望按动按钮的次数越少越好。请你帮帮小Q吧

输入描述:输入包括一行，一行中有四个正整数a，b，A，B，（1≤a，b，A，B≤10^9）。  
输出描述:如果小Q可以完成转换，输出最少需要按动按钮的次数，否则输出-1。

示例  
输入 100 1000 202 2002  
输出 2

【思路】  
从乘法入手，求出A/a ，为A 是a的倍数。（rem = 202/100 = 2）  
如果rem >1 需要乘以一次2 所以num++；并rem/2,直到rem不大于1 (num为乘2的次数  
令n = 2的num次方  
m为A 与 a*n 的差值 ，即为个位相差的数字  
如果m>0则需要改动，  
如果是奇数，需要加一次1，num++；  
如果不是奇数，m/2 循环直到不大于0；  
再看b，如果B-b*n-m == 0，说明可以完成转换  
如果不等于0 ，说明完不成转换

【实现】

import java.util.Scanner;
    public class tengxun2a {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		int a = sc.nextInt();
    		int b = sc.nextInt();
    		int A = sc.nextInt();
    		int B = sc.nextInt();
    		int num = changeNum(a,b,A,B);
    		System.out.println(num);
    	}
    	
    	
    	public static int changeNum(int a,int b,int A,int B){//100 1000 202 2002
    		int num = 0, rem = A/a;//num = 0,rem = 2
            while(rem > 1){//rem>1
                num++;//num = 1
                rem >>= 1;//右移一位  *2,rem = 2/2=1
            }
            int n = (int)Math.pow(2,num);//n = 2*1 = 2
            int m = rem = A - a*n; // m = rem = 202 - 100*2 = 2
            while(rem > 0){//rem = 2>0
                if((rem & 1) == 1) num++;//是奇数 num++
                rem >>= 1;//rem/2   = 1 ，0
            }
            if(B-b*n-m == 0) return num;
            return -1;
    	}
    }