Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера: 1. Прибавить 1. 2. Прибавить 2. 3. Умножить на 2. Первая команда увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на

6 ноября 2025
Программирование

Условие:

Исполнитель преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

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 – логический признак: было ...