计算将数字从m更改为n的最小步骤数。

Question

我在面试时被要求解决这个问题：

给定两个数字，m & n，我们需要将一个数字m转换为n，其中包含以下操作的最小数目：

• -1 -减去1
• *2 -乘2

例如:如果是m=4和n=6，程序应该输出2。

• 第一次手术：-1 -> 4-1 = 3。
• 第二次手术：*2 -> 3 * 2 =6。

由于我们可以在2次操作后将m (4)更改为n (6)，所以答案是2。

现在我不知道面试官对我的期望是什么，我也不知道什么是合适的解决办法。

Answer 1

你可以试试这个：

def convert(m, n): 

    if(m == n): 
        return 0

    # only way is to do 
    # -1(m - n): times 
    if(m > n): 
        return m - n 

    # not possible 
    if(m <= 0 and n > 0): 
        return -1

    # n is greater and n is odd 
    if(n % 2 == 1): 

        # perform '-1' on m 
        #(or +1 on n): 
        return 1 + convert(m, n + 1) 

    # n is even 
    else: 

        # perform '*2' on m 
        #(or n/2 on n): 
        return 1 + convert(m, n / 2) 

# Driver code 
m = 3
n = 11
print("Minimum number of operations :", 
                          convert(m, n)) 

Answer 2

这是我的java解决方案。

public class Main {

public static void main(String[] args) {
    int m = 3;
    int n = 36;
    int counter = 0;
    float ntemp;

    if (m > n) {
        counter = m - n;
        System.out.println("result: " + counter);
        return;
    }

    while (m != n) {
        ntemp = n;
        while (m < ntemp) {
            ntemp = ntemp / 2;
        }
        if (m < ntemp + 1) {
            m = m * 2;
            System.out.println("*2");
        } else {
            m = m - 1;
            System.out.println("-1");
        }
        counter++;
    }
    System.out.println("result: " + counter);
}
}

解释：

下面我只考虑m< n的情况，因为给定的m >= n的情况很明显。

1.如果2m > n

在这种情况下

( a)若2(m-1) =n个->端

b)如果2(m-1)

减去1后，我们的数字太小了。

我们可以改变不平等：

2(m-1) m < n/2 + 1

如果我们的数目太小，我们必须乘以2，但这不是最优的，因为我们必须减去2*(m-1)乘以(如果n个奇数，则减去2*(m-2)-1 )，所以这意味着减法1不是个好主意。

总结:对于m< n/2 +1，->乘后减去

2.如果2m n

经过一些运算(一个乘法和一定数量的-1)，我们希望从步骤1.：M< n/2 +1获得满足条件的结果(因为我们必须再次乘以)。

我们假设4m >n -> 2×2*m>n-> 2m > n/2。

当我们更改表示法n/2 = ntemp时，我们得到了相同的条件：

2m > ntemp，因此我们可以得到与步骤1相同的结论。

3.如果x*m n，x-iteger

每一个数m，我们都可以像第2步一样变换，得到同样的结论。

P.S.：我知道这不是正式的证明，很抱歉我的英语:)