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

Question

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

Given 2 numbers m & n and we need to convert a number m to n with minimum number of the following operations:

-1 - Subtract 1

*2 - Multiply by 2

For e.g. : if m=4 and n=6, the program should output 2.

1st operation : -1 -> 4-1 = 3.

2nd operation : *2 -> 3 * 2 =6.

As we can Change m (4) to n (6) after 2 operations, the answer is 2.

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

Answer 1

这是我在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) < n

减 1 后数字太小了。

我们可以改变不平等：

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

如果我们的数字太小，我们必须乘以 2，但这不是最优的，因为我们必须减去 2*(m-1) 次（或 2*(m-2)-1如果 n 是奇数），那么这意味着减去 1 不是个好主意。

总结：对于 m < n/2 + 1 -> 相乘然后相减

2。如果 2m < n 和 4m > 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 且 2*x*m > n，则 x-iteger

我们可以像步骤 2 那样对每个数字 m 进行变换，并得到相同的结论。

P.S.: 我知道这不是正式证明，对不起我的英语:)

Answer 2

你可以试试这个：

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))

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

Count the minimum number of steps to change a number from m to n

language-agnostic

algorithm