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

 
 
 

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

Дано:
у исполнителя Утроитель две команды, которым присвоены номера:

  1. прибавь 1;

  2. умножь на 3.

Первая из них увеличивает число на экране на 1, вторая ─ утраивает его.

 

Вопрос:
запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд, указывая лишь номера команд.

(Например, 21211 ─ это программа

  • умножь на 3;

  • прибавь 1;

  • умножь на 3;

  • прибавь 1;

  • прибавь 1.

которая преобразует число 1 в 14).

 

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

Первое, на что стоит обратить внимание - то, что обе команды увеличивают текущее число. Следовательно, наиболее оптимально решать поставленную задачу методом от обратного, то есть преобразовывать число 22 в число 1, используя разрешенные команды исполнителя.

Почему можно выбирать подобный метод решения ("спускаться" от конечного числа к начальному числу)?

Потому что, гораздо удобнее двигаться по однозначно правильному маршруту не перебирая заведомо ложные варианты. Для движения по правильному маршруту поможет следующее тривиальное правило:

  • если преобразуемое число кратно 3 (делится на 3 без остатка), то делим это число на 3;

  • если преобразуемое число не кратно 3 (делится на 3 с остатком), то вычитаем 1.

Вы спросите, а откуда взялись операции "деление на 3" и "вычитание 1"? Все дело в том, что преобразование числа производится от конечного значения к начальному значению, следовательно, и взять нужно операции-антагонисты по отношению к исходным операциям.

 

Решение

Для получения из числа 22 число 1 воспользуемся процессинговой таблицей, состоящей из 4 колонок;

N командыЧисло"Деление на 3" или "Вычитание 1"Результат
122"Вычитание 1", так как 22 не кратно 322 - 1 = 21
221"Деление на 3", так как 21 кратно 321 / 3 = 7
37"Вычитание 1", так как 7 не кратно 37 - 1 = 6
46"Деление на 3", так как 6 кратно 36 / 3 = 2
52"Вычитание 1", так как 2 не кратно 32 - 1 = 1

Как видно из заполненной процессинговой таблицы:

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

  2. число 1 получено, не дольше, чем за 5 команд (в данном случае, потребовалось ровно 5 команд).

 

По условию задачи требуется выписать порядок команд получения числа 22 из числа 1. Но мы получили обратную ситуацию: преобразовали число 22 в число 1, следовательно, нужно проводить анализ записей процессинговой таблицы от последней к первой. Причем, конвертируем команды в допустимые, то есть:

  • если в процессинговой таблице стоит команда "Вычитание 1", то ей соответствует команда "Прибавь 1" под номером 1;

  • если в процессинговой таблице стоит команда "Деление на 3", то ей соответствует команда "Умножь на 3" под номером 2;

Анализируя таблицу от последней записи к первой получаем последовательность команд:

Прибавь 1   |   Умножь на 3   |   Прибавь 1   |   Умножь на 3   |   Прибавь 1

       1         |            2           |          1         |             2          |          1

Последовательность команда: 12121

 

Вывод:

порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд, имеет вид: 12121

Резюме

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

  2. анализируем процессинговую таблицу от конца к началу, меняя команды на противоположные.

 

Ответ:

12121

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

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

 

Комментарии

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