Тип Д23 № 3305 
Оператор присваивания и ветвления. Перебор вариантов, построение дерева. Поиск количества чисел по заданному числу команд
i
У исполнителя Калькулятор две команды:
1. прибавь 2
2. умножь на 3.
Первая из них увеличивает число на экране на 2, вторая — утраивает его. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит не более 4 команд?
Решение. Программа может состоять из 0, 1, 2, 3 или 4 команд; проанализируем эти случаи. Следующие рассуждения удобно записывать в виде дерева.
Не содержит ни одной команды одна программа: она не изменит числа на экране, дав на выходе число 2.
С помощью одной команды из числа 2 можно получить 2 различных числа:
2 + 2 = 4
2 * 3 = 6.
С помощью двух команд можно получить по два числа из 4 и 6:
4 + 2 = 6 .
4 * 3 = 12
6 + 2 = 8
6 * 3 = 18
Число 6 уже есть, поэтому и все числа, которые могут из него получиться нам не интересны, т. к. они все будут повторять уже имеющиеся. Т. е. мы получили 3 числа.
С помощью трёх команд получаются следующие числа:
12 + 2 = 14
12 * 3 = 36
8 + 2 = 10
8 * 3 = 24
18 + 2 = 20
18 * 3 = 54
С помощью четырёх команд из 6 чисел представленных выше, можно получить ещё 12 чисел. Но заметим, что 10 + 2 = 12, а это число у нас уже имеется, значит, осталось 11 чисел.
Всего различных чисел: 1 + 2 + 3 + 6 + 11 = 23.
Ответ: 23.
Ответ: 23
PDF-версии: