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Файловая система
  • Устройство компьютера
  • ПО компьютера

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

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

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

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

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

задача B13 ЕГЭ по информатике 2013 граф до получения числа 11

После выполнения 4-х команд получаем число 11.

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

Определим P(11):

задача B13 ЕГЭ по информатике 2013 определяем P(11)

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

22*2>23, поэтому к 23 ведет только 1 решение.

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

Зная P(11), можно определить P(10):

задача B13 ЕГЭ по информатике 2013 определяем P(10)

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

20*2>23, поэтому к 23 ведет только 1 решение.

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

Зная P(10) можно определить P(8):

задача A3 ЕГЭ по информатике 2013 определяем P(8)

P(10)=3 решения.

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

16*2>23, поэтому к 23 ведет только 1 решение.

Получили, P(8)=3+1+1=5.

Зная P(8) можно определить P(6):

Задача B13 ЕГЭ по информатике 2013 определяем P(6)

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

14*2>23, поэтому к 23 ведет только 1 решение.

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

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

Зная P(6) можно определить P(5):

Задача B13 ЕГЭ по информатике 2013 определяем P(5)

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

P(10)=3 решения.

Получили, P(5)=7+3=10.

Теперь можно определить P(3):

Задача B13 ЕГЭ по информатике 2013 определяем P(3)

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

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

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

P(3)=10+5+7=22.

Получили 22 программы.

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

P(n)=1 при n>11.

P(11)=P(12)+P(22)=2 программы.

P(10)=P(11)+P(20)=2+1=3 программы.

P(8)=P(9)+P(16)=P(10)+P(18)+P(16)=3+1+1=5 программ.

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

P(5)=P(6)+P(10)=7+3=10 программ.

P(3)=P(4)+P(6)=P(5)+P(8)+P(6)=10+5+7=22 программы.

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

 

Rambler's Top100

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