Новое устройство, разработанное группой учащихся школы No 200, преобразует число используя, две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Программа для данного устройства это последовательность команд. Сколько существует программ, для которых при исходном числе 3 результатом является число 25 и при этом траектория вычислений не содержит числа 5?
Посчитаем количество программ (последовательностей команд «+1» и «×2»), которые преобразуют число 3 в число 25, при этом ни в каком промежуточном результате не встречается число
5.
Заметим, что обе команды увеличивают число (команда «+1» прибавляет 1, а команда «×2» умножает на 2), значит все промежуточные числа будут строго возрастать. При этом, если операция приводит к числу 5, такая программа не подходит.
Найдем все возможные пути от 3 до 25, рассматривая только те переходы, которые не генерируют число
5.
Начнем с 3. Для каждого числа бу...
Внутри — полный разбор, аргументация, алгоритм решения, частые ошибки и как отвечать на каверзные вопросы препода, если спросит
Попробуй решить по шагам
Попробуй один шаг и продолжи в режиме обучения или посмотри готовое решение
Не нашел нужную задачу?