Тип 23 № 27248 
Оператор присваивания и ветвления. Перебор вариантов, построение дерева. Количество программ с обязательным этапом
i
Исполнитель РазДва преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1.
2. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя РазДва — это последовательность команд. Укажите наименьшее натуральное число, которое нельзя получить из исходного числа 1, выполнив программу исполнителя РазДва, содержащую не более пяти команд.
Решение. Из числа 1 одной командой можно получить только число 2. Двумя командами можно получить либо число 3, либо число 4. Тремя командами можно получить числа 4, 5, 6, 8. Четырьмя командами можно получить числа 5, 6, 7, 8, 9, 10, 12 и 16. Наконец, пятью командами можно получить числа 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 20, 24, 32.
Заметим, что наименьшее число, которого нет среди полученных ранее чисел, — 15. Таким образом, ответ — 15.
Ответ: 15.
Приведём другое решение на языке Python.
def f(x, h):
if h == 5:
a.add(x)
else:
f(x + 1, h + 1)
f(x * 2, h + 1)
a = set()
f(1, 0)
print(a)
В полученном множестве отсутствует число 15, оно и будет являться ответом.
Приведём решение Сергея Фефелова на языке Python.
def f(x, y, n):
if x > y or n < 0:
return 0
if x == y:
return 1
return f(x + 1, y, n - 1) + f(x * 2, y, n - 1)
for i in range(2, 100):
if f(1, i, 5) == 0:
print(i)
break
Приведём решение Сергея Корчажкина на языке Python.
def f(x, h=0):
if h <= 5:
a.add(x)
if h == 5:
a.add(x)
return
f(x + 1, h + 1)
f(x * 2, h + 1)
a = set()
f(1)
print(sorted(a))
Ответ: 15
