计数的步骤的最小数目从米更改数目为n

Question

我在采访，并要求解决这个问题：

由于2号m＆n，我们需要将数字转换m通过以下操作的最低数量n：

• -1 - 减1
• * 2 - 乘以2

对于如：如果m=4和n=6，程序应该输出2。

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

正如我们可以改变m（4）n（6）后2个操作，答案是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.如果2米>Ñ

在这种情况下

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.如果2米<n和4米>Ñ

一些操作（一次乘法和-1一些量）后，我们想从步骤接收结果满足条件1：M <N / 2 + 1（因为我们不得不再次乘）。

我们假设4米> N - > 2 * 2 * M> N - >2米> N / 2。

当我们改变符号的n / 2 = N的时间，我们接收到相同的条件：

2米> NTEMP，所以我们可以得到相同的结论，在步骤1中。

3.如果x * M <N和2 * X * M> N，X-整数

每一个数字m，我们可以在第2步变换等，并得到了相同的结论。

P.S：我知道这不是正式的证明和对不起我的英文:)