Задание 22. У исполнителя Утроитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.
Первая из них увеличивает число на экране на 1, вторая утраивает его.
Программа для Утроителя — это последовательность команд. Сколько есть программ, которые число 2 преобразуют в число 31?
Решение.
Первую программу можно составить из сложений числа 1 к числу 2 пока не получится число 31. Теперь подсчитаем число программ, в которых используется одно умножение на 3. Можно сразу 2 умножить на 3, а затем прибавлять 1 до 31. Можно сначала к 2+1, затем умножить на 3, а потом опять прибавлять 1. Максимальное число, которое можно умножить на 3 равно 10, то есть (2+1+1+1+1+1+1+1+1)*3=30. Отсюда видно, что программ с одним умножением на 3 может быть ровно 9.
Далее, подсчитаем программы с двумя умножениями на 3. Они могут быть такими:
- пусть начальное число равно 2, тогда имеем 5 программ:
- пусть начальное число равно 3, тогда получаем 2 программы:
Таким образом, всего имеем 1+9+5+2=17 программ.
Ответ: 17.
Другие задания:
Для наших пользователей доступны следующие материалы: