VladHub18 / Task EGE 23.py
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 )) |
| #Исполнитель U18 преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера: |
| #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 )) |
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Разбор задания №22 ЕГЭ-2019 по информатике и ИКТ
Демоверсия КИМ ЕГЭ-2019 по информатике не претерпела никаких изменений по своей структуре по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный (хочется на это рассчитывать) план подготовки к экзамену обучающегося.
Мы рассмотрим решение предлагаемого проекта (на момент написания статьи – пока еще проекта) КИМ ЕГЭ по информатике.
Часть 1
Ответами к заданиям 1–23 являются число, последовательность букв или цифр, которые следует записать в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной клеточке в соответствии с приведёнными в бланке образцами.
Задание 22
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
- Прибавить 2
- Умножить на 2
- Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3.
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 22 и при этом траектория вычислений программы содержит число 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Решение
Для начала решим задачу просто, без учета дополнительного условия «содержит число 11»:
Программа короткая, а также она не дает в своей траектории вычисления значения 11. И тут стоит разбить задачу на две небольшие задачи: определить число путей от 2 до 11 и от 11 до 22. Итоговый результат, очевидно, будет соответствовать произведению этих двух значений. Построение сложных схем с деревьями – нерациональная трата времени на экзамене. Чисел в нашем диапазоне не так много, поэтому предлагаю рассмотреть следующий алгоритм:
Выпишем все числа от стартового и до последнего включительно. Под первым напишем 1. Двигаясь слева направо, рассмотрим число способов попадания в текущую позицию, используя данные нам команды.
Сразу можно убрать очевидные позиции, не влияющие на решение: 3 можно зачеркнуть – понятно, что в нее нельзя попасть из стартовой позиции, используя одну из доступных нам команд; 10 – через нее мы не можем никак попасть в нашу промежуточную, а главное, обязательную позицию 11.
В 4 мы можем попасть двумя путями-командами: х2 и +2, т.е. через 4 проходят 2 пути. Напишем это значение под 4. В 5 можно попасть единственным способом: +3. Напишем под 5 значение 1. В 6 можно попасть единственным путем – через 4. А под ней у нас указано значение 2. Соответственно, именно по этим двум путям, проходя 4, мы попадем из 2 в 6. Пишем под 6 значение 2. В 7 можно попасть из двух предыдущих позиций, используя имеющиеся у нас команды, и для получения числа путей, которые нам доступны для попадания в 7, мы сложим числа, которые указывали под этими предыдущими позициями. Т.е. в 7 мы попадаем 2 (из-под 4) + 1 (из-под 5) = 3 путями. Действуя по этой схеме и далее, получаем:
Перейдем в правую половину от условного центра – 11. Только теперь при расчете будем учитывать только те пути, которые проходят через этот центр.
Двигаясь и далее слева направо, мы получаем искомый результат – 100.
Ответ: 100.
Заместитель генерального директора по ИКТ АНОО «Дом знаний», преподаватель по программированию Яндекс.Лицея (ДГУНХ, Махачкала), учитель высшей категории, финалист Всероссийского конкурса «Учитель года России 2010»
Количество программ, ведущих из одного числа в другое
Исполнитель МЕГАТРОН преобразует число, записанное на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавь 1,
2. Прибавь 2.
Первая из них увеличивает число на экране на 1, вторая — увеличивает его на 2.
Программа для МЕГАТРОНа — это последовательность команд.
Сколько есть программ, которые преобразует число 1 в число 9?
Количество программ, которые преобразуют число 1 в число \(n,\) обозначим \(R(n).\) Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, \(R(1) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда \(R(2) = 1.\) Число “3” можем получить из чисел 1 и 2 — \(R(3) = R(1) + R(2) = 2.\) Число “4” получаем из 2 и 3 — \(R(4) = R(2) + R(3) = 3.\) Можем заметить, что количество программ для получения числа n находится по формуле — \(R(n) = R(n-2) + R(n-1).\) Составим таблицу по данной формуле:
\[\begin
Исполнитель Калькулятор преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 2,
2. Умножь на 3.
Первая из них увеличивает число на экране на 2, вторая — увеличивает его в 3 раза.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 42?
Количество программ, которые преобразуют число 2 в число \(n,\) обозначим \(R(n).\) Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, \(R(2) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на три, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-2).\)
Если число на три делится, то вариантов последней команды два: прибавь 2 и умножь на 3, тогда \(R(n) = R(n-2) + R(n:3).\) Заполним таблицу по данной формуле:
\[\begin
Исполнитель ХЛЕБУШЕК преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавь 1,
2. Прибавь 2,
3. Прибавь 3.
Первая из них увеличивает число на экране на 1, вторая — увеличивает его на 2, третья — увеличивает его на 3.
Программа для ХЛЕБУШКа — это последовательность команд.
Сколько есть программ, которые преобразуют число 1 в число 14?
Количество программ, которые преобразуют число 1 в число n, обозначим \(R(n).\) Число 1 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 1. Значит, \(R(1) = 1.\) Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Число “2” может быть получено только из числа “1” командой под номером 1. Отсюда \(R(2) = 1.\) Число “3” можем получить из чисел 1 и 2 — \(R(3) = R(1) + R(2) = 2.\) Число “4” получаем из 1, 2 и 3 — \(R(4) = R(1) + R(2) + R(3) = 6.\) Заметим, что количество программ для получения числа n находится по формуле — \(R(n) = R(n-3) + R(n-2) + R(n-1).\) Составим таблицу по данной формуле:
\[\begin
Исполнитель Прибавлялка имеет две команды, которым присвоены номера:
1. Прибавь 1,
2. Увеличь старшую цифру числа на 1.
Первая из них увеличивает число на экране на 1, вторая увеличивает на 1 старшую (левую) цифру числа, например число 63 с помощью такой команды превратится в число 73. Если старшая цифра числа равна 9, то вторая команда оставляет это число неизменным.
Программа для Прибавлялки — это последовательность команд.
Сколько есть программ, которые число 31 преобразуют в число 53?
Обе команды увеличивают исходное число. Старшая цифра — 3, следовательно, использовать команду 2 более двух раз бессмысленно.
Выпишем программы, в которых команда 2 используется два раза: 1122, 2211, 1212, 2121, 2112, 1221. Итого 6 программ.
Выпишем программы, в которых команда 2 используется один раз. Использовав эту команду в первой позиции, мы получим из числа 31 число 41, следовательно, после этого необходимо будет дописать ещё 12 команд 1 чтобы получить число 53. Таким образом, получаем программы: \(211\dots1,\) \(121\dots1,\) и. т. д. Итого имеем 13 программ (двойка побывала в каждой позиции).
Существует лишь одна программа, в которой команда 2 не используется: \(111\dots1.\)
Таким образом получаем \(6 + 13 + 1 = 20.\)
Исполнитель М.Е.М.249 преобразует целое число, записанное на экране.
У исполнителя две команды, которым присвоены номера:
преобразует целое число, записанное на экране.
1. Прибавить 1,
2. Прибавить 2,
3. Прибавить предыдущее.
Первая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.).
Программа для исполнителя М.Е.М.249 – это последовательность команд.
Сколько существует программ, которые число 1 преобразуют в число 10?
Обозначим число программ, преобразующих число 2 в число n как \(R(n).\) Тогда число \(n\) может быть получено либо прибавлением к \(n-1,\) либо к \(n-2,\) либо из некоторого числа \(х\) увеличением на \(x-1,\) так что \(n = x + x — 1,\) откуда \(x = \frac
Тогда для четных чисел \(R(n) = R(n-1) + R(n-2),\) а для нечетных — \(R(n) = R(n-1) + R(n-2) + R(\frac
\[\begin
Исполнитель УВЕЛИЧИТЕЛЬ9000 преобразует целое число, записанное на экране.
У исполнителя три команды. Каждой команде присвоен номер:
1. Прибавить 1,
2. Прибавить 2,
3. Умножить на 4
Первая из них увеличивает число на экране на 1, второе — увеличивает его на 2, третья — увеличивает его в 4 раза.
Программа для УВЕЛИЧИТЕЛЯ9000 — это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 17?
Количество программ, которые преобразуют число 2 в число n, обозначим R(n). Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, R(2) = 1. Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на 4, то оно может быть получено командами 1 и 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-1) + R(n-2)\) .
Если число делится на 4, то вариантов последней команды три: прибавить 1, прибавить 2 и умножить на 4, тогда \(R(n) = R(n-1) + R(n-2) + R(n:4)\) . Заполним таблицу по данной формуле:
\[\begin
Исполнитель ЕЩЕНКО преобразует целое число, записанное на экране.
У исполнителя две команды, которым присвоены номера:
1. Прибавь 2,
2. Умножь на 10.
Первая из них увеличивает число на экране на 2, второе — увеличивает его в 10 раз.
Программа для Калькулятора — это последовательность команд.
Сколько есть программ, которые преобразуют число 2 в число 40?
Количество программ, которые преобразуют число 2 в число n, обозначим \(R(n)\) . Число 2 у нас уже есть, значит, его можно получить с помощью “пустой” программы. Любая непустая программа увеличит исходное число, т.е. даст число, больше 2. Значит, \(R(2) = 1\) . Для каждого следующего числа рассмотрим, из какого числа оно может быть получено за одну команду исполнителя. Если число не делится на десять, то оно может быть получено только из предыдущего с помощью команды прибавь 2. Значит, количество искомых программ для такого числа равно количеству программ для предыдущего возможного числа: \(R(n) = R(n-2)\) .
Если число делится на 10, то вариантов последней команды два: прибавь 2 и умножь на 10, тогда \(R(n) = R(n-2) + R(n:10)\) . Заполним таблицу по данной формуле:
\[\begin