Посчитайте минимальное количество шагов, чтобы изменить число от m до n

Question

Я был на собеседовании, и меня попросили решить эту проблему:

Учитывая 2 числа m & n, и нам нужно преобразовать число m в n с минимальнымколичество следующих операций:

• -1 - Вычесть 1
• * 2 - Умножить на 2

Например: если m=4 и n=6, программа должна вывести 2.

• 1-я операция: -1 -> 4-1 = 3.

• 2-я операция: *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 очевиден.

1.Если 2m> n

В этом случае

a) если 2 (m-1) = n -> end

b) если 2 (m-1))

После вычитания 1 получим слишком маленькое число.

Мы можем преобразовать неравенство:

2 (м-1) м

Если у нас слишком маленькое число, мы должны умножить на 2, но это было бы неоптимально, потому что мы должны вычесть 2 * (m-1) раз (или2 * (m-2) -1, если n нечетное число), так что это означает, что вычитать 1 не очень хорошая идея.

Суммирование: Для m умножить, а затемвычесть

2.Если 2m n

После некоторых операций (одно умножение и некоторое количество -1) мы хотим получить условие выполнения результата с шага 1 .: m

Мы предположили, что 4m> n -> 2 * 2 * m> n -> 2m> n / 2.

Когда мы меняем обозначение n / 2= ntemp, мы получаем то же условие:

2m> ntemp, поэтому мы можем получить те же выводы, что и на шаге 1.

3.Если x * m n, x-iteger

Каждое число m можно преобразовать аналогично шагу 2. и получить те же выводы.

PS: я знаю, что это не формальное доказательство, и извините за мой английский :) 1048 *