Сколько операций необходимо, чтобы получить заданное число n из числа 1, используя калькулятор с тремя операциями

Содержание вопроса: Количество операций для получения заданного числа

Инструкция: Чтобы решить данную задачу, можно использовать алгоритм поиска в ширину (BFS). Начиная с числа 1, мы проверяем все возможные операции (прибавление 1, умножение на 2 и умножение на 3) и записываем результаты в очередь. Затем мы продолжаем выполнять операции на числах из очереди, пока не получим заданное число n.

Мы будем использовать словарь `distances`, чтобы отслеживать наименьшее количество операций для достижения каждого числа. Изначально, все значения устанавливаем на бесконечность, кроме 1, для которого мы устанавливаем значение 0, потому что нам не требуется выполнить никакие операции, чтобы получить 1.

Затем, используя цикл while, мы обрабатываем все числа из очереди и проверяем все возможные операции. Если полученное число меньше или равно n и количество операций для достижения этого числа меньше, чем текущее минимальное количество операций для этого числа, мы обновляем значение в словаре.

После обхода всех возможных чисел и выполнения операций, мы возвращаем наименьшее количество операций, необходимых для получения числа n из числа 1.

Демонстрация:

Входные данные: n = 10

Выходные данные: 3

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

Дополнительное упражнение: Сколько операций необходимо, чтобы получить число 30 из числа 1, используя те же самые операции?