На нашем сайте вы можете смотреть сериалы онлайн, узнать дату выхода новых серий. Все сериалы в HD качестве смотреть онлайн, сериалы онлайн бесплатно и без регистрации.
Добро пожаловать! Если вы хотите успешно сдать ЕГЭ – то вы попали куда надо. Для полноценной подготовки к экзамену egedb.ru предлагает вам: прохождение тестов ЕГЭ по многим предметам с последующим анализом результатов, прорешивание задач определенного типа или на определенные темы, познакомится с процедурой проведения ЕГЭ и многое другое!
Бесплатные развлекательные тесты помогут вам проверить уровень интеллекта, узнать больше о себе, своем характере, а также окружающих и том, что они о вас думают!Здесь вы можете пройти всевозможные тесты на любой вкус! Бесплатные тесты без обмана и смс
Хотите узнать больше о бланках, предоставляемых на экзамене и потренироваться в их заполнении? Всё просто! Наш сайт предлагает потренироваться на электронных копиях блаков – такие тренировки безусловно принесут свои плоды и помогут не допустить ошибок при заполнении.
Вам нужна статистика вашей подготовки на сайте? Войдите в личный кабинет при помощи своей учетной записи в социальной сети «В Контакте» и получите такую возможность. Или может быть вы хотите помочь развитию сайта? При повышенной активности на сайте вы можете быть повышены до уровня модератора и добавлять свои задания на сайт!


Главная

Тесты

Русский язык
Математика
Информатика
Физика
Биология
География
Обществознание
История

Задачи

Русский язык
Математика
Информатика
Физика
Биология
География
Обществознание
История

Как решить

Полезности

Статьи

Новости

Гостевая

Ссылки

Поиск

Вход

Задание C3 ЕГЭ 2012 по информатике - Бесплатная подготовка к ЕГЭ egedb.ru

Задание C3 по предмету Информатика (№42)

Информатика 2012 год

Поиск выигрышной стратегии

C3

У исполнителя Утроитель две команды, которым присвоены номера:
1. прибавь 1,
2. умножь на 3.

Первая из них увеличивает число на экране на 1, вторая – утраивает его. Программа для Утроителя – это последовательность команд. Сколько есть программ, которые число 1 преобразуют в число 29? Ответ обоснуйте.
За правильный ответ 3 балл(ов)
Правильный ответ:
Обозначим R(n) – количество программ, которые преобразуют число 1 в число n. Обозначим t(n) наибольшее кратное трем, не превосходящее n. Обе команды исполнителя увеличивают исходное число, поэтому общее количество команд в программе не может превосходить 28.
Верны следующие соотношения:
1. Если n не делится на 3, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) – прибавлением единиц.
2. Пусть n делится на 3. Тогда R(n) = R(n/3)+R(n-1)= R(n/3)+R(n-3) (если n>3). При n=3 R(n) = 2 (два способа: прибавлением двух единиц или однократным умножением на 3).
Поэтому достаточно постепенно вычислить значения R(n) для всех чисел, кратных трем и не превосходящих 29: сначала вычисляем R(1), затем R(3), R(6) и т.д.
Имеем:
R(2)=1
R(3) = 2 = R(4)=R(5)
R(6) = R(2)+R(3) =1+2 = 3 = R(7)=R(8)
R(9) = R(3)+R(6) =2+3 =5 = R(10)=R(11)
R(12) = R(4)+R(9) = 2+5 = 7 = R(13)=R(14)
R(15) = R(5)+R(12) =2+7 =9 = R(16)=R(17)
R(18) = R(6)+R(15) = 3+9 = 12 = R(19)=R(20)
R(21) = R(7)+R(18) = 3+12 = 15 = R(22)=R(23)
R(24) = R(8)+R(21) = 3+ 15 = 18 = R(25)=R(26)
R(27) = R(9)+R(24) = 5 + 18 = 23 = R(28)=R(29)
Ответ: 23
Показать ответ

Ещё задания

Комментарии

Назад