Дано:
у исполнителя Кузнечик две команды:

1. прибавь 3;

2. вычти 2.

Первая из них увеличивает число на экране на 3, вторая — уменьшает его на 2 (отрицательные числа допускаются). Программа для Кузнечика — это последовательность команд.

Вопрос:
cколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд?

Первое, что нужно заметить в условии - допустимые команды Кузнечика. Их всего две (прибавь 3, вычти 2), следовательно, "напрашивается" применение специализированной структуры данных - бинарное дерево (или официальное название - двоичное дерево поиска).

Второе, на что стоит обратить внимание - количество команд, которые должен выполнить Кузнечик по заданному алгоритму. Их всего 5 штук.

Следовательно, не так уж длительно осуществить "полный перебор", то есть перебрать всевозможные вариации получения различных чисел из числа 1. В архихудшем случае, потребуется перебрать максимально 32 варианта, так как 2⁵ = 32.

Алгоритм – последовательность действий, приводящая к решению поставленной задачи за разумное время.

Конститутивные свойства алгоритма:

• дискретность – последовательность шагов выполнения;

• детерминированность – алгоритм должен быть определенным;

• понятность – алгоритм должен быть понятен исполнителю (как правило, исполнителем выступает компилятор или интерпретатор);

• завершаемость – алгоритм должен завершиться за разумное время;

• массовость – алгоритм должен корректно работать при различных входных данных;

• результативность – алгоритм должен финализироваться конкретным результатом.

Исполнитель алгоритма – автомат (как правило, рассматривается персональный компьютер) или человек, способный выполнять определенный набор действий. Как правило, в роли конкретного исполнителя выступают следующие существа: Робот, Инвентор, Делитель, Сумматор, Дробитель, Утроитель, Вычитатель, Модулятор, Калькулятор и т. п.

Для решения поставленной задачи рассмотрим формирование бинарного дерева, у которого в каждом узле записано целое число. Это число соответствует промежуточному значению текущей итерации.

• левая ветвь дерева отвечает за операцию: прибавь 3;

• правая ветвь дерева отвечает за операцию: вычти 2.

Начинаем процесс формирования двоичного дерева и получения различных чисел из числа 1:

Кузнечик выполняет команду под номером 1:

Как видно из рисунка, образовалось два уникальных числа: 4, -1

Кузнечик выполняет команду под номером 2:

Как видно из рисунка, образовалось 4 числа, причем 1 из них имеет дубликат, следовательно,
остается 4 - 1 = 3 уникальных числа: 7, 2, -3

Кузнечик выполняет команду под номером 3:

Как видно из рисунка, образовалось 6 чисел, причем 2 из них имеют дубликаты, следовательно,
остается 6 - 2 = 4 уникальных числа: 10, 5, 0, -5

Кузнечик выполняет команду под номером 4:

Как видно из рисунка, образовалось 8 чисел, причем 3 из них имеют дубликаты, следовательно,
остается 8 - 3 = 5 уникальных чисел: 13, 8, 3, -2, -7

Кузнечик выполняет команду под номером 5 (завершающая команда):

Как видно из рисунка, образовалось 10 чисел, причем 4 из них имеют дубликаты, следовательно,
остается 10 - 4 = 6 уникальных чисел: 16, 11, 6, 1, -4, -9

1. выбираем методику решения, используя бинарное дерево;

2. для каждой команды Кузнечика формируем новый уровень дерева и исключаем дубликатные числа.