Лена оптимизирует вычислительную машину, которая преобразует одно число в другое. У машины есть две команды: 1. Умножить на 2 2. Уменьшить на 1 На вход поступает целое число x. Задача – преобразовать его в y. Для оптимизации необходимо, чтобы количество выполненных команд при преобразовании было минимальным. Реализуйте алгоритм вычисления минимального количества команд, которые переводят число x в число y. В качестве ответа укажите минимальное количество операций для x = 10, y = 100

Для решения данной задачи можно воспользоваться алгоритмом поиска в ширину (BFS).

1. Создадим очередь, в которую будем помещать пары чисел (число, количество операций).
2. Добавим в очередь пару (10, 0), обозначающую начальное число и количество операций.
3. Пока очередь не пуста, будем извлекать из неё пару (число, количество операций) и выполнять две операции: умножение на 2 и уменьшение на 1.
4. Если результат умножения или уменьшения равен искомому числу y, то вернем количество операций.
5. Если результат не равен y и не превышает его, добавим в очередь новую пару (результат, количество операций + 1).
6. Повторяем шаги 3-5.

Применяя данный алгоритм к x = 10, y = 100, получим, что минимальное количество операций для преобразования числа 10 в число 100 равно 7.