Question

На доске написано число 1. За один ход его можно умножить на 7 или прибавить к нему единицу. За какое минимальное количество ходов можно получить число 100076?

Answer 1

1*7^5+83269=100076 .
Поэтому 5+83269=83274 шагов.

Answer 2

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

1. Создаем очередь, в которую будем добавлять числа для обработки. 2. Добавляем число 1 в очередь. 3. Создаем словарь, в котором будем хранить минимальное количество шагов для достижения каждого числа. 4. Устанавливаем значение для числа 1 равным 0 (так как для него не требуется никаких шагов). 5. Запускаем цикл, пока очередь не пуста: - Извлекаем первое число из очереди. - Если это число равно 100076, завершаем цикл. - Вычисляем новые числа, умножая текущее число на 7 и прибавляя к нему 1. - Если новое число еще не было посещено, добавляем его в очередь и устанавливаем значение для него равным значению текущего числа плюс 1. 6. Выводим минимальное количество шагов для достижения числа 100076.

Таким образом, минимальное количество шагов для получения числа 100076 будет равно значению, записанному в словаре для этого числа.