Сколько есть программ которые число 2 преобразуют в число 22

Содержание

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

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

#1. прибавь 1

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

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

#Сколько есть программ, которые число 1 преобразуют в число 18?

def numProg ( start , x ):

if start == x : # если цель достигнута, то

return 1 # завершить функцию, посчитав цепочку (программу)

if start > x : # если перелет, то

return 0 # завершить функцию, не считая цепочку

if start < x : #продолжаем строить дерево

return numProg ( start + 1 , x ) + numProg ( start * 2 , x ) + numProg ( start * 3 , x )

print ( numProg ( 1 , 18 ) )

#Исполнитель М17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

#1. Прибавить 1

#2. Прибавить 2

#3. Умножить на 3

#Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и

#при этом траектория вычислений содержит числа 8 и 10?

def numProg ( start , x ):

if start == x :

return 1

if start > x :

return 0

if start < x :

return numProg ( start + 1 , x ) + numProg ( start + 2 , x ) + numProg ( start * 3 , x )

print ( numProg ( 2 , 8 ) * numProg ( 8 , 10 ) * numProg ( 10 , 12 )) #Если траектория содержит точки,

#то можно представить как метод интервалов с пуcтыми точками

#Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

#1. Прибавить 1

#2. Умножить на 2

#Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и

#при этом траектория вычислений содержит число 14 и не содержит числа 25?

def numProg ( start , x ):

if start == x :

return 1

if start == 25 or start > x : #Если x=25 или перелет, то завершить функцию, не считая цепочку

return 0

if start < x :

return numProg ( start + 1 , x ) + numProg ( start * 2 , x )

print ( numProg ( 2 , 14 ) * numProg ( 14 , 29 ))

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

#1. Прибавить 1

#2. Умножить на 2

#Сколько существует программ, преобразующих число 4 в число 24, предпоследней командой которых является команда «1»?

def numProg ( start , x ):

if start == x :

return 1

if start > x :

return 0

if start < x :

return numProg ( start + 1 , x ) + numProg ( start * 2 , x )

print ( numProg ( 4 , 11 ) + numProg ( 4 , 22 ))

#1)Итак, мы знаем предпоследнюю команду – 1, при этом последняя команда может быть любая – 1 или 2,

#выходит, что нужно получить количество всех программ вида «*11» и «*12», где звёздочка обозначает любые команды

#2)Если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число 24 – 1 – 1 = 22;

#поэтому нужно найти число программ для преобразования 4 в 22

#3)Теперь рассматриваем случай, когда программа заканчивается на «12», это значит, что до выполнения цепочки «12»

#у нас было число (24/ 2) – 1 = 11; поэтому нужно найти число программ для преобразования 4 в 11

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

#1. прибавь 1

#2. увеличь число десятков на 1

#Например: при помощи команды 2 число 23 преобразуется в 33. Если перед выполнением команды 2 вторая с конца цифра равна 9, она не изменяется.

#Сколько есть программ, которые число 11 преобразуют в число 27?

def numProg ( start , finish ):

if start == finish :

return 1

if start > finish :

return 0

if start < finish :

return numProg ( start + 1 , finish ) + numProg ( start + 10 , finish )

print ( numProg ( 11 , 27 ))

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

#1. прибавь 1

#2. увеличь каждый разряд числа на 1

#Например, число 23 с помощью команды 2 превратится в 34, а 29 в 39 (так как младший разряд нельзя увеличить).

#Если перед выполнением команды 2 какая-либо цифра равна 9, она не изменяется. Сколько есть программ,

#которые число 25 преобразуют в число 51?

def com2 ( n ):

if n % 10 == 9 :

n += 10

return n

else :

n += 11

return n

def numProg ( start , finish ):

if start == finish :

return 1

if start > finish :

return 0

if start < finish :

return numProg ( start + 1 , finish ) + numProg ( com2 ( start ), finish )

print ( numProg ( 25 , 51 ))

#Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

#1. Вычесть 1

#2. Вычесть 3

#3. Разделить нацело на 3

#При выполнении команды 3 выполняется деление нацело (остаток отбрасывается).

#Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ,

#которые исходное число 22 преобразуют в число 2?

def numProg ( start , finish ):

if start == finish :

return 1

if start < finish :

return 0

if start > finish :

return numProg ( start — 1 , finish ) + numProg ( start — 3 , finish ) + numProg ( start // 3 , finish )

print ( numProg ( 22 , 2 ))

#1. Вычесть 1

#2. Вычесть 3

#3. Взять остаток от деления на 4

#Команда 3 выполняется только для чисел, больших, чем 4.

#Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ,

#которые исходное число 22 преобразуют в число 2?

def com3 ( n ):

if n > 4 :

n %= 4

return n

else :

return 0

def numProg ( start , finish ):

if start == finish :

return 1

if start < finish :

return 0

if start > finish :

return numProg ( start — 1 , finish ) + numProg ( start — 3 , finish ) + numProg ( com3 ( start ), finish )

print ( numProg ( 22 , 2 ))

Разбор задания №22 ЕГЭ-2019 по информатике и ИКТ

Предлагаем вашему вниманию разбор задания №22 ЕГЭ 2019 года по информатике и ИКТ. Этот материал содержит пояснения и подробный алгоритм решения, а также рекомендации по использованию справочников и пособий, которые могут понадобиться при подготовке к ЕГЭ.

26 марта 2019
Поделитесь в соц.сетях

ЕГЭ-2020. Информатика. Тематические тренировочные задания

Пособие содержит задания, максимально приближенные к реальным, используемым на ЕГЭ, но распределенные по темам в порядке их изучения в 10-11-х классах старшей школы. Работая с книгой, можно последовательно отработать каждую тему, устранить пробелы в знаниях, а также систематизировать изучаемый материал. Такая структура книги поможет эффективнее подготовиться к ЕГЭ.

Демоверсия КИМ ЕГЭ-2019 по информатике не претерпела никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.

ЕГЭ 2019 по информатике задание 22

Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2
3. Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3. Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 22 и при этом траектория вычислений программы содержит число 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.

Данный пример взят из демоверсии 2019 по информатике на сайте http://fipi.ru

РЕШЕНИЕ

Данная задача относится к динамическому программированию.

Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение

Для начала рассмотрим пример проще: