infoegehelp.ru

Успешно сдать ЕГЭ по информатике
  • Главная
  • Контакты
  • Карта сайта
  • Помощь сайту
Важно
  • Демо варианты ЕГЭ
  • Учим числа: 2 в степени
  • Биты, байты, килобайты
Решение задач
  • Задачи вне основных разделов информатики
Разделы информатики
  • 2011-12-18-14-33-54Системы счисления
  • 2011-12-18-16-45-20Алгебра логики
  • 2011-12-18-16-55-26Программирование
  • 2011-12-18-16-53-40Кодирование информации
  • 2011-12-18-16-56-19Компьютерные сети и Интернет
  • -excelЭлектронные таблицы (Excel)
  • 2011-12-18-16-57-50Базы данных
  • 2011-12-18-16-58-50Графы
  • 2011-12-18-17-00-15Файловая система
  • Устройство компьютера
  • ПО компьютера

Разбор задачи C3 (демо ЕГЭ 2012)

Время выполнения-30 мин, уровень сложности-высокий

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

Решение:

Нам нужно построить граф, описывающий выполнение команд Утроителя. Строим его до тех пор, пока не получим число 9. 29/3=9 с остатком. Числа больше 9 дают только одну программу, т.к. нельзя применить команду "умножить на 3".

Построим этот граф:

задача C3 ЕГЭ по информатике 2012 вторая команда

После выполнения 2-х команд получаем числа: 3, 6, 4, 9. Определим число программ-решений, для получения из каждого из них числа 29.

Обозначим количество программ-решений для получения из числа n числа 29 как Р(n).

Количество программ-решений для получения из 1-цы числа 29 определяется по формуле: N=P(3)+P(6)+P(4)+P(9).

Выберем из чисел 3, 6, 4, 9 самое большое. Это 9. Определим P(9):

задача C3 ЕГЭ по информатике 2012 определяем P(9)

10*3>29, поэтому к 29 ведет только 1 решение.

27*3>29, поэтому к 29 ведет только 1 решение.

Получили, P(9)=1+1=2.

Остались числа: 3, 6, 4. Наибольшее из них число 6. Определим P(6):

задача C3 ЕГЭ по информатике 2012 определяем P(6)

18*3>29, поэтому к 29 ведет только 1 решение.

21*3>29, поэтому к 29 ведет только 1 решение.

24*3>29, поэтому к 29 ведет только 1 решение.

P(9)=2 решения.

Получили, P(6)=1+1+1+2=5.

Остались числа: 3,4. Наибольшее из них число 4. Определим P(4):

задача C3 ЕГЭ по информатике 2012 определяем P(4)

12*3>29, поэтому к 29 ведет только 1 решение.

15*3>29, поэтому к 29 ведет только 1 решение.

P(6)=5 решений.

Получили, P(4)=1+1+5=7.

Осталось число 3. Определим P(3):

задача C3 ЕГЭ по информатике 2012 определяем P(3)

Получили, P(3)=P(4)+P(9)=7+2=9.

N=P(9)+P(6)+P(4)+P(3)=2+5+7+9=23 программы.

Краткое решение:

P(N)=1 при N>9.

P(9)=P(10)+P(27)=2 программы.

P(6)=P(9)+P(24)+P(21)+P(18)=2+1+1+1=5 программ.

P(4)=P(6)+P(15)+P(12)=5+1+1=7 программ.

P(3)=P(4)+P(9)=7+2=9 программ.

P(1)=P(3)+P(4)+P(6)+P(9)=9+7+5+2=23 программы.

Перейти к С3-2011.

Перейти к С3-2010.

Перейти к С3-2009.

Перейти к другим задачам.

 

Rambler's Top100

© Латыпова В.А., 2012-2020. Все права защищены.
Копирование материалов сайта только с разрешения администрации сайта