Как найти минимальное количество операций?

Question

[Андрей]

В математике не силён, дана такая задача:
даны x, y.

Как из числа x получить число y, используя только операции (x * 2) и (x - 1), затратив при этом наименьшее число попыток?

Можно реализовать простую логику в лоб, если x меньше то умножаем, если больше, то вычитаем. Но есть кейсы, где такое не пройдет, например x = 5, y = 8.
Здесь минимум операций это 2: x - 1, x * 2, тогда как примитивный алогоритм сделал бы три попытки: x * 2, x -1, x - 1.

Answer 1

[Алексей 〒.]

Алгоритм:

int convert(x, y) {
    if (x == y)  {
        return 0;
    }
    
    // невозможно преобразовать
    if (x <= 0 && y > 0) {
        return -1;
    }

    // x больше y
    if (x > y) 
        return x - y;

    if (y % 2 == 1) {   // y нечётное число
       return 1 + convert(x, y + 1); // выполняем 'x - 1' 
    } else {    // y чётное
        return 1 + convert(m, n/2); // выполняем 'x * 2'
    }
}

Источник