Сколько существует программ для которых при исходном числе 3

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

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

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

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

1. итак, мы знаем предпоследнюю команду – 1, при этом последняя команда может быть любая – 1 или 2
2. выходит, что нужно получить количество всех программ вида «*11» и «*12», где звёздочка обозначает любые команды
3. если программа заканчивается на «11», то до выполнения цепочки «11» у нас было число

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

1. для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числаNиз начального числа 1, то .
2. теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N
3. число Nмогло быть получено одной из двух операций:

• увеличением на 1 числа N-1;
• умножением на 2 числа N/2 (только для N, которые делятся на 2, и таких, что N/2 4);

для нечётных чисел для чётных чисел, таких, что N/24

1. составляем таблицу:
   

   N	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
   	1	1	1	1	2	2	3	3	4	4	5	5	7	7	9	9	12	12	15

2. теперь рассматриваем случай, когда программа заканчивается на «12», это значит, что до выполнения цепочки «12» у нас было число (24/ 2) – 1 = 11; поэтому нужнонайти число программ для преобразования 4 в 11, берём его из таблицы:3
3. ответ к задаче – сумма двух значений, выделенных жёлтым маркером: 15 + 3 = 18, поскольку мы рассмотрели все варианты программ, в которых предпоследняя команда – 1
4. Ответ: 18.

Летний курс | Задание 23 | ЕГЭ-2023 по информатике

КЕГЭ по информатике 2022. Задание № 23. Поляков. Сколько существует программ? Python. Часть № 2.

Ещё пример задания:

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

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17. Решение:

1. заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
2. для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числаNиз начального числа 1, то .
3. теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N
4. число Nмогло быть получено одной из двух операций:

• увеличением на 1 числа N-1;
• умножением на 2 числа N/2 (только для N, которые делятся на 2);

для нечётных чисел для чётных чисел

1. поскольку траектория должна проходить через число 10, сначала выясняем, сколькими способами можно получить 10 из 1, а затем будем считать, сколько есть способов получить 21 из 10
2. заполняем таблицу от 1 до 10 по полученным формулам:
   

   N	1	2	3	4	5	6	7	8	9	10
   	1	2	2	4	4	6	6	10	10	14

3. второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10, только левую часть таблицы (от 1 до 10) мы уже не рассматриваем:
   

   N	10	11	12	13	14	15	16	17	18	19	20	21
   	14	14	14	14	14	14	14	14	14	14	28	28

4. Ответ: 28.

Источник: studfile.net

Решаем 23 задание ЕГЭ по информатике через рекурсию, самый простой алгоритм

Привет! Сегодня научу тебя решать 23 задание КЕГЭ на Python. Алгоритм несложный, но требуется понимать, что такое рекурсия и как она работает.

Для тех, кто не знаком с рекурсией, рекомендую прочитать о ней, например, на сайте Питонтьютор ( https://pythontutor.ru/lessons/functions/ ).

Поиск количества программ по заданному числу

Условие задачи

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

1. прибавь 2,

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

Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 5 раз.

Программа для Калькулятора — это последовательность команд.

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

Решение

Строка 1. Функция принимает на вход один аргумент: число, с которого начинается отсчет.

Строки 2-5. Точки выхода рекурсии. Если мы достигли цели (число 50), то путь есть (возвращаем 1), а если число стало больше, чем 50, то этот путь не учитываем (возвращаем 0).

Строки 6-7. Продолжение рекурсии. Функция вызывает саму себя с новыми значениями и складывает результат выполнения.

Строка 9. Вызов функции с начальным числом 2.

Количество программ с избегаемым этапом

Условие задачи

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

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.

Программа для исполнителя РазДваТри — это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 3 в число 16 и при этом траектория вычислений не содержит чисел 6 и 12?

Траектория вычислений — это последовательность результатов выполнения всех команд программы. Например, для программы 312 при исходном числе 6 траектория будет состоять из чисел 9, 10, 20.

Решение

Строка 1. Функция принимает на вход один аргумент: число, с которого начинается отсчет.

Строки 2-5. Точки выхода рекурсии. Если мы достигли цели (число 16), то путь есть (возвращаем 1), а если число стало равно 6, 12 или больше, чем 16, то этот путь не учитываем (возвращаем 0).

Строки 6-7. Продолжение рекурсии. Функция вызывает саму себя с новыми значениями и складывает результат выполнения.

Количество программ с обязательным этапом

Условие задачи

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

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

Сколько существует программ, для которых при исходном числе 4 результатом является число 13, и при этом траектория вычислений содержит число 11?

Решение

В задаче с обязательной вершиной необходимо разбить путь 4 -> 13 на два пути: 4 -> 11 и 11 -> 13. Программа выведет два числа: 25 и 2, а ответом к задаче будет являться произведение этих чисел, т.е. число 50.

Поиск количества чисел по заданному числу команд

Условие задачи

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

1. прибавь 2

2. прибавь 3.

Первая из них увеличивает число на экране на 2, вторая — на 3. Сколько различных чисел можно получить из числа 2 с помощью программы, которая содержит ровно 10 команд?

Решение

Строка 1. Заведем список, чтобы складывать в него полученные числа.

Строка 2. Функция принимает на вход два аргумента: n — число, которое будет увеличиваться, k — количество команд.

Строки 3-5. Точка выхода рекурсии. Если команд ровно 10, текущее число добавляем в список, функцию прерываем.

Строки 6-7. Точка выхода рекурсии. Если команд больше 10, функцию прерываем.

Строки 8-9. Продолжаем рекурсию, но на этот раз результаты функций не складываем, а объединяем оператором «или» (OR)

Строка 11. Вызываем функцию с начальным значением 2 и числом команд 0.

Строка 12. Печатаем длину множества чисел списка sp.

Источник: dzen.ru

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

При выполнении команды 3 выполняется деление нацело (остаток отбрасывается). Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ, которые исходное число 22 преобразуют в число 2?

94) (А.Е. Гребенкин, Екатеринбург) Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:

Вычесть 1

Вычесть 3

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

Команда 3 выполняется только для чисел, больших, чем 4. Программа для исполнителя U18 – это последовательность команд. Сколько существует таких программ, которые исходное число 22 преобразуют в число 2?

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

Прибавить 1

Прибавить 3

Сколько существует программ, для которых при исходном числе 2 результатом является число 18 и при этом траектория вычислений содержит число 9 и не содержит число 14?

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

Прибавить 1

Прибавить 3

Сколько существует программ, для которых при исходном числе 2 результатом является число 20 и при этом траектория вычислений содержит число 10 и не содержит число 15?

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

Прибавить 1

Прибавить 3

Сколько существует программ, для которых при исходном числе 3 результатом является число 20 и при этом траектория вычислений содержит число 15 и не содержит число 10?

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

Прибавить 1

Умножить на 2

Умножить на 3

Сколько существует программ, для которых при исходном числе 3 результатом является число 46 и при этом траектория вычислений содержит число 12 и не содержит число 25?

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

Прибавить 1

Умножить на 2

Умножить на 3

Сколько существует программ, для которых при исходном числе 5 результатом является число 52 и при этом траектория вычислений содержит число 15 и не содержит число 29?

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

Прибавить 1

Умножить на 3

Умножить на 4

Сколько существует программ, для которых при исходном числе 2 результатом является число 60 и при этом траектория вычислений содержит число 16 и не содержит число 21?

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

Прибавить 1

Умножить на 3

Умножить на 4

Сколько существует программ, для которых при исходном числе 2 результатом является число 70 и при этом траектория вычислений содержит число 8 и не содержит число 35?

[1] Источники заданий:

1. Демонстрационные варианты ЕГЭ 2012-2016 гг.

2. Тренировочные работы МИОО.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Студопедия рекомендует:

Предмет, задачи и методы социальной психологии Предмет социальной психологии. Основные точки зрения на объект и предмет социальной психологии: социологический.
Понятие и виды исков в римском праве Иск – обращенное в суде требование истца к ответчику. «Иск есть не что иное.
Как определить экскурсию грудной клетки? Величина окружности грудной клетки характеризует развитие и степень ее подвижности.
Анкетный опрос: структура анкеты,виды вопросов Анкетный опрос — такая разновидность метода опроса, при котором общение между социологом (исследователем) и респондентом.
Прибыль предприятия, ее виды. Факторы, влияющие на величину прибыли. Направление использования. Прибыль — одна из основных форм денежных накоплений, со­здаваемых предприятиями различных отраслей экономики.

Источник: studopedia.ru