Простой способ решения задачи C3
Создание: 28.03.2013

В последние два года в ЕГЭ по информатике появился новый класс задач. В C3 появились задачи требующие составлении рекурсивной функции. Вместе с тем, эти задачи очень просто решаются другим способом.

Текст задачи из демонстрационной версии ЕГЭ за 2012 год

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

1. прибавь 1,
2. умножь на 3.

Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 29? Ответ обоснуйте.

Решение:

Эта задача «про граф»!

  • Возьмите листок бумаги и напишите все числа от 1 до 29.
  • Соедините числа стрелками последовательно, ведь из каждого предыдущего с помощью операции +1 можно получить следующее.
  • Соедините стрелками числа, которые можно утроить и результат не превышает 29. (на рисунке - зеленые стрелки).
  • Подсчитайте количество переходов по графу.

 
Граф задачи C3 2012 года

Ответ: 23 возможных путей. 23 возможные программы исполнителя.

Комментарии к вычислениям:

  • Так у числа 3 мы поставим двойку, так как в этот узел графа можно перейти либо из двойки либо из единицы.
  • У четверки остается двойка, так как в этот узел можно прийти только из тройки.
  • У шестерки узел получит вес 3, так как в этот узел можно прийти либо из пятерки (2) либо из двойки (1).
  • и т.д.

Вместе с рисованием чисел на решение задачи C3 уйдет 5 минут! Неплохо?

Комментарии к ответу:

так как человек проверяющий задачу не обязан читать этот материал знать этот способ решения в вашем письменном ответе нужно использовать следующие ключевые слова-маркеры, показывающие, что вы «в теме»:

строим граф возможных путей преобразования числа 1 в число 29

  • граф является исчерпывающим
  • подсчитываем количество переходов (вес каждого узла графа)
  • финальное число – общее количество программ.

P.S.

Подготовка к экзамену не заучивание решений прошлых лет, это увлекательная подготовка к своему «звездному часу» где вы сможете продемонстрировать гибкость ума, и знания, которые получали в школе последние годы