Раздел B • Категория B13 (демонстрационный вариант-2012)

 
 
 

Условие задачи

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

  1. прибавь 3;

  2. вычти 2.

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

 

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

 

Методические указания

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

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

Следовательно, не так уж длительно осуществить "полный перебор", то есть перебрать всевозможные вариации получения различных чисел из числа 1. В архихудшем случае, потребуется перебрать максимально 32 варианта, так как 25 = 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 с помощью программы и которое содержит ровно 5 команд составляет 6.

Резюме

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

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

 

Ответ:

6

 
Рейтинг:
 
Проголосовало: 1
Количество просмотров: 1074
 
 
 

Раздел B • Категория B13 (демонстрационный вариант-2012)

 

Комментарии

Для комментирования или зарегистрируйтесь
 
 
© 2011-2019 ООО "СтадиМен". Все права сохранены.
Перепечатка и использование материалов с данного сайта, разрешена только по согласию с владельцем.
Владелец оставляет за собой право воспользоваться 146 статьей УК РФ при нарушении авторских и смежных прав.
 
 
 
 
Авторизация на сайте
 
 
 
Обнаружили
ошибку на сайте?