Исполнитель Вычислитель получает на вход целое число и может выполнять над ним следующие действия: 1. Прибавь 1 прибавляет к числу на экране 1
2. Умножь на 2 - увеличивает число на экране в 2 раза
3. Умножь на 3 -Увеличивает число на экране в 3 раза
За какое минимальное количество действий исполнитель Вычислитель может получить из числа число ?
В данной задаче, каждое число представляется узлом графа, а возможные действия — ребрами. Наша задача состоит в поиске кратчайшего пути от числа "x" до числа "y" в этом графе.
Пусть "x" - это исходное число, а "y" - число, которое мы хотим получить.
Для решения этой задачи, мы можем использовать алгоритм поиска в ширину со следующими шагами:
1. Создаем очередь для сохранения чисел, которые мы еще не исследовали.
Начинаем с добавления исходного числа "x" в очередь. Также создаем словарь для отслеживания минимального количества действий для каждого числа.
2. Инициализируем минимальное количество действий для числа "x" как 0.
3. Пока очередь не пуста, выполняем следующие действия:
- Извлекаем первое число из очереди.
- Проверяем, равно ли оно числу "y".
Если да, то мы нашли кратчайший путь и можем завершить алгоритм.
- Для каждого возможного действия (прибавление 1, умножение на 2 или умножение на 3) выполняем следующие действия:
- Вычисляем новое число, полученное в результате действия.
- Проверяем, было ли это число уже посещено (есть ли оно в словаре минимального количества действий).
Если нет, то добавляем число в очередь и устанавливаем минимальное количество действий для него, равным текущему количеству действий плюс 1.
4. Если мы дойдем до конца очереди, и не найдем число "y", то оно недостижимо.
5. По завершении алгоритма, минимальное количество действий для получения числа "y" будет содержаться в словаре минимального количества действий для этого числа.
Вот пример кода на Python, который реализует описанный алгоритм:
```python
from collections import deque
def minimum_actions(x, y):
queue = deque()
queue.append(x)
actions = {x: 0}
while queue:
num = queue.popleft()
if num == y:
return actions[num]
for operation in [1, 2, 3]:
if operation == 1:
new_num = num + 1
elif operation == 2:
new_num = num * 2
else:
new_num = num * 3
if new_num not in actions:
actions[new_num] = actions[num] + 1
queue.append(new_num)
return -1 # Если не удалось достичь числа "y"
# Пример использования
x = 5
y = 50
result = minimum_actions(x, y)
print(f"Минимальное количество действий для получения числа {y} из числа {x}: {result}")
```
В данном примере, мы вызываем функцию `minimum_actions` с числами "x" и "y" в качестве аргументов и сохраняем результат в переменную `result`. Затем мы выводим этот результат на экран, чтобы узнать минимальное количество действий для получения числа "y" из числа "x".
Например, если мы запустим пример выше с числами "x = 5" и "y = 50", то результат будет равен 22, что означает, что минимальное количество действий для получения числа 50 из числа 5 составляет 22.