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

 
 
 

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

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

  1. прибавь 1;

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

Первая из них увеличивает число на экране на 1, вторая – утраивает его.
Программа для Утроителя – это последовательность команд.

 

Вывод:
сколько есть программ, которые число 1 преобразуют в число 29?
*Ответ обоснуйте.

 

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

Одним из свойств заданий категории С3 является то, что нельзя "научиться" решать подобные задачи, то есть не существует как таковой общепризнанной методики решения подобных упражнений.
Необходимо включать логическое мышление, оперативно "подбирать" алгоритмы, правильно использовать аналитико-математический аппарат, грамотно использовать индуктивный и дедуктивный метод мышления и, разумеется, нередко помогает нестандартный взгляд на проблематику, то есть иногда требуется проявить смекалку (что само по себе не тривиально, учтите это).

*примечание: мое субъективное мнение - очень немного существует людей, обладающих "развитой" смекалкой и нестандартным мышлением. Иногда, данные навыки развиваются при решении олимпиадных задач и задач повышенного уровня сложности (как видите, именно на олимпиадах даются задачи на смекалку и нестандартное мышление, неспроста это!).

 

Теоретические сведения

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

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

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

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

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

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

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

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

Довольно часто, при решении упражнений из категории C3, приходится прибегать к индуктивному и дедуктивному методу решения.

Индуктивный метод – метод мышления, при котором общее положение выводится из частных утверждений и логических переходов.
Дедуктивный метод – метод мышления, при котором частное выводится из общих положений, используя логические переходы.

 

Решение

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

  1. прибавь 1;

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

то максимально возможное количество команда в программе не может превосходить 28. Это тот случай, когда текущее число постоянно увеличивается ровно на 1 (если к единице прибавить 28 раз единицу, то образуется число равное 29).

 

Воспользуемся индуктивным методом и рассмотрим упрощенный частный случай. Допустим нужно детерминировать количество программ, преобразующих число 1 в число 7 (число 7 меньше числа 29 чуть больше, чем в 4-ре раза).

Отобразим решение в виде двоичного дерева:

  • левая ветвь - прибавь 1 (I команда исполнителя);

  • правая ветвь - умножь на 3 (II команда исполнителя).

Промежуточный итог: преобразовать число 1 в число 7 можно тремя различными программами.

 

Как видно из вышеприведенного графического примера (когда получали из числа 1 число 7), потребовалось произвести немало вычислительных манипуляций, а ведь нам по условию задачи требуется из 1 получить гораздо большее число, а именно 29, следовательно, строить бинарное дерево в данном случае нецелесообразно. Нужен принципиально другой подход!

Число 1.
Исходное число.

Число 2.
Это число можно получить единственным способом, если добавить к единице число один. Также отметим, что число 2-а не кратно трем.

Число 3.
Это число уже можно получить двумя различными способами:

  • добавить к числу 2 единицу;

  • умножить на три число 1.

Также отметим, что число 3-и является кратным трем.

 

Сейчас необходимо попытаться обобщить вышесказанные словесные выкладки математическим правилом.

Пусть

  • i     - текущее рассматриваемое число;

  • a[i] - количество различных программ для получения числа i.

Как мы выяснили ранее, если значение i не кратно трем, то:
a[i] = a[i - 1], то есть, количество различных программ для получения числа не кратного трем, равно количеству различных программ для получения предыдущего значения.

Если значение i кратно трем, то:
,

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

 

Если вы смогли вывести подобные закономерности, то на 90% уже справились с задачей, так как дело осталось за малым, а именно, распространить (воспользоваться индуктивным методом) данные закономерности на все программы получения из числа 1 числа 29.

Детерминируем количество программ, преобразующих число 1 в число 29.
Стартовой точкой является условие:
i = 1 и a[1] = 1 (a[2] = a[1] = 1).

Когда i = 3, имеем следующее состояние:

 

Посмотрим на развитие таблицы, когда i достигло значения равное 15.

 

Итоговый вариант процессинговой таблицы имеет вид:

 

Вывод:

как видно из построенной таблицы существует ровно 23 различных программы, преобразующих число 1 в число 29, то есть:

a[29] = 23.

Резюме

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

  2. смоделировать алгоритм на элементарном варианте и попытаться вывести математические закономерности;

  3. используя ранее выведенные законы получить результат.

 

Ответ:

23

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

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

 

Комментарии

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