Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1.
2. Прибавить 2.
3. Умножить на 2.
Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 2.
Программа для исполнителя — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 1 в число 9 и при этом не содержат двух команд умножения подряд?
Нам дано, что имеется исполнитель, который может выполнять три команды: 1. Прибавить 1 (обозначим A) – прибавляет 1 к числу. 2. Прибавить 2 (обозначим B) – прибавляет 2 к числу. 3. Умножить на 2 (обозначим C) – умножает число на 2.
Задача: найти количество программ (последовательностей команд), которые преобразуют исходное число 1 в число 9 при условии, что ни в какой программе не встречаются две команды умножения (C) подряд.
Чтобы решить задачу, удобно ввести понятие состояний. Пусть каждое состояние определяется парой (n, L), где n – текущее число на экране, а L – логический признак: было ...
Не нашел нужную задачу?