У исполнителя Калькулятор две команды:
1. прибавь 1.
2. умножь на 2.
Первая из них увеличивает число на экране на 1, вторая – увеличивает его в 2 раза.
Программа для Калькулятора – это последовательность команд.
Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 4 команды?
*Следующее рассуждение удобно записывать в виде дерева.
С помощью одной команды из числа 2 можно получить два различных числа:
2 + 1 = 3,
2 * 2 = 4.
С помощью двух команд можно получить четыре числа:
3 + 1 = 4,
3 * 2 = 6,
4 + 1 = 5,
4 * 2 = 8.
С помощью трёх команд получаются следующие восемь различных чисел:
4 + 1 = 5,
4 * 2 = 8,
5 + 1 = 6,
5 * 2 = 10,
8 + 1 = 9,
8 * 2 = 16,
6 + 1 = 7,
6 * 2 = 12.
С помощью четырёх команд из 8 чисел, получившихся выше, получится 16 чисел. Но заметим, что
5 * 2 = 10 и 9 + 1 = 10, поэтому различных из них будет 15 чисел.
Ответ: 15.