Задание 2. Информатика. Апробация 10.03.2023
Миша заполнял таблицу истинности логической функции (F)
$$
(x to neg (y to z)) lor w,
$$
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных (w), (x), (y), (z).
| F | ||||
| 0 | 0 | 0 | ||
| 1 | 0 | |||
| 0 | 1 | 0 |
Определите, какому столбцу таблицы соответствует каждая из переменных (w), (x), (y), (z).
В ответе напишите буквы (w), (x), (y), (z) в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Функция (F) задана выражением ( neg x lor y), зависящим от двух переменных, а фрагмент таблицы имеет следующий вид:
В этом случае первому столбцу соответствует переменная (y), а второму — переменная (x). В ответе следует написать: (yx).
Решение:
Python
from itertools import permutations, product
def F(x, y, z, w):
return (x <= (not y <= z)) or w
for perm in permutations('xyzw'):
for a,b,c,d,e,f,g in product([0,1], repeat=7):
table = [[a,0,b,0,0],
[1,c,d,e,0],
[0,1,f,g,0]]
if table[0] == table[1]:
continue
if all(F(**dict(zip(perm,row))) == row[-1] for row in table):
print(*perm)
Ответ: (yzxw)
What you will learn
- Научитесь решать № 1-23 ЕГЭ самыми эффективными способами
- Изучите Python с нуля
- Научитесь работать в электронных таблицах
- Изучите теоретические основы информатики
About this course
Данный курс – это логически выстроенная и целостная система по подготовке к ЕГЭ по информатике 2023 года:
Тщательно продуманная траектория изучения теоретического материала, основ алгоритмизации, программирования (Python), электронных таблиц позволит комфортно изучить все аспекты информатики, которые проверяются на ЕГЭ.
✅ В курсе сделан упор на системное изучение, понимание основ, а не натаскивание на шаблонное решение задач.
Но в тоже время в курсе разобраны все типы задач № 1-23 ЕГЭ. Для каждого типа задачи приведены все возможные способы решения, в том числе и авторские:
- Теоретическое решение (необходимо для понимания сути)
- Программное на Python (быстрое, и как правило, более простое чем теоретическое)
- С помощью электронных таблиц в Excel (более наглядное, чем программное решение, подойдёт тем, кто не уверен в программировании)
✅ Изучение всех тем происходит по принципу от простого к сложному.
✅ Преподаватели курса обязательно ответят на все вопросы в течение суток. Если будет необходимо, то запишут видео разбор задания, которое вызывает затруднение. Смело задавайте вопросы в комментариях, преподаватели отвечают на них каждый день!
✅ Курс обновляется видео-разборами и новыми задачами для тренировки по мере появления новых типов задач.
Логика курса:
- Сначала теоретические основы – кодирование и измерение информации, системы счисления, теория графов, логика, комбинаторика. Разобрана вся необходимая теория и приведены теоретические решения всех типов задач на эти темы.
- Далее – основы программирования (Python), можно начать изучение даже с нуля. Изучение начинается с базовых алгоритмов, и заканчивается продвинутыми олимпиадными алгоритмами. В курсе очень подробно и доступно объясняется тема «Динамическое программирование» – эффективный алгоритм, который используется для решения многих задач № 1-23 КЕГЭ, необходимый для решения задач второй части КЕГЭ, особенно 27 задачи. Отработка всех алгоритмов происходит на задачах КЕГЭ. Рассматривается программное решение задач, которые были ранее решены теоретически (устно).
- После добавляется изучение электронных таблиц (MS Excel). Изучаются основы и продвинутые возможности MS Excel, закрепление которых происходит на задачах ЕГЭ, многие из которых очень легко решаются в Excel.
- Затем рассматриваются алгоритмы для решения задач. Происходит углубленное изучение программирования и электронных таблиц. Все задачи решаются несколькими самыми эффективными способами.
В курс входят 224 урока, 68 часов видео, 1442 задачи, 61 интерактивная задача.
- Теоретическое решение рассматривается для № 1, 2, 4, 5, 7, 8, 11, 12, 13, 14, 15, 19-21.
- Решение в Excel рассматривается для № 2, 3, 5, 9, 16, 17, 18, 19-21, 23.
- Решение в Python рассматривается для № 2, 5, 6, 8, 9, 12, 14, 15, 16, 17, 19-21, 22, 23.
❗ Возможно, вы уже занимались с нами на наших других курсах. В этот курс вошли некоторые уроки наших курсов. Мы сделали так, что ваши решения будут отображаться и в этом курсе. Вам останется только пройти уроки по закреплению и отработке уже пройденного материала.
❗ Вы можете попробовать с нами учиться бесплатно, достаточно много уроков являются открытыми.
❗ После покупки курса вы можете начать его прохождение в любое время. Доступ к курсу останется у вас навсегда. Оплата производится один раз, не по месяцам.
Тем кто вступит в нашу группу ВК, мы подарим промокод на скидку в 15% на данный курс.
Для получения промокода – напишите нам в сообщения сообщества кодовое слово 123 .
Обратите внимание, что вы можете приобрести два наших курса:
- Информатика ЕГЭ 2023. Путь к 100 баллам. № 1 — 23
- Информатика ЕГЭ 2023. Путь к 100 баллам. № 24 — 27
по ещё большей скидке, купив их вместе:
- ЕГЭ Информатика 2023. Путь к 100 баллам. № 1 — 27
Whom this course is for
Курс подойдёт всем, кому нужна качественная подготовка к ЕГЭ по информатике 2023 года.
Если вы учитесь в 9-10 классе, то данный курс вам тоже подойдёт, так как он постоянно обновляется.
Initial requirements
Курс подходит для учеников с нулевым уровнем знаний, так как теория объясняется с самых азов. А также и для продвинутых учеников, так как курс содержит большое количество нестандартных задач и авторских способов их решения.
Meet the Instructors
How you will learn
Курс состоит из модулей трёх типов:
- 💡 Подробное изучение теории
- ✅ Разбор номера из ЕГЭ
- 🧐 Решение варианта из пройденных задач
Каждый модуль состоит из уроков. А каждый урок из коротких видеоразборов теории и задач, а также задач с автоматической проверкой для закрепления материала.
Структура всех модулей по разбору номера из ЕГЭ:
- Изучение теории: несколько коротких видео с теорией + задачи на закрепление материала.
- Разбор задач: Видео с разбором всех типов задач + задачи для тренировки.
- Рубрика «Как решать задание на ЕГЭ?» от одного из учителей курса, который сдавал ЕГЭ в 2021 году (98 баллов).
- Тренировка: большое количество задач с автопроверкой.
- Мониторинг знаний: решение мини варианта из пройденных заданий.
Course content
Certificate
Stepik certificate
Price
FAQ
Share this course
https://stepik.org/course/104041/promo
Шестнадцатое задание из ЕГЭ по информатике 2022 даётся на рекурсию.
Это задание нужно делать с помощью компьютера.
В программировании рекурсией называется процесс, когда функция вызывает сама себя или, когда две функции попарно вызывают друг друга.
Мы будем писать все программы на языке программирования Python.
Что такое Функция в языке программирования Python ?
Функция – это подпрограмма, результатом работы которой может является определенное значение.
Рассмотрим пример функции, которая суммирует два числа!
def F(x, y): s = x + y return s a = int(input()) b = int(input()) r = F(a, b) print(r)
Здесь функция F, которая суммирует два числа.
В главной части программы запрашиваются два числа с клавиатуры: a и b! Эти два числа передаются в функцию F. В функции эти числа кладутся в локальные переменные x и y. Сумма переменных x и y записывается в переменную s. Переменная s возвращается, как результат работы функции F.
Результат работы функции будет помещён в переменную r (в строке r = F(a, b)) в основной части программы.
Таким образом, в переменной r будет сумма двух переменных a и b.
Функции позволяют сократить программный код для однотипных расчётов.
Тренировочные задачи 16 задания из ЕГЭ по информатике 2023
Задача (Стандартная)
Алгоритм вычисления значения функции F(n), где n – натуральное число,
задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n – чётно,
F(n) = 3 × F(n − 2), если n > 1 и при этом n – нечётно.
Чему равно значение функции F(25)?
Решение:
Напишем программу для решения данной задачи. В начале опишем все правила, которые даны в условии задачи для функции. В основной части программы запустим эту функцию.
# Сама функция def F(n): if n==1: return 1 if n%2==0: return n+F(n-1) if n>1 and n%2!=0: return 3*F(n-2) # Основная часть программы print(F(25))
После запуска рекурсивной функции программа выведет ответ 531441.
Выражение n%2 != 0 (остаток от деления на «2» не равен нулю) обозначает нечётное число. Выражение n%2==0 обозначает чётное число.
Ответ: 531441
Продолжаем тренировку по подготовке к 16 заданию ЕГЭ по информатике 2022.
Задача (Продолжаем подготовку)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(2) = 3
F(n) = F(n–1) * n + F(n–2) * (n – 1) , при n > 2
Чему равно значение функции F(8)? В ответе запишите только натуральное число.
Решение:
# Сама функция def F(n): if n==1: return 1 if n==2: return 3 if n>2: return F(n-1)*n + F(n-2)*(n-1) # Основная часть программы print(F(8))
Ответ получается 148329.
Ответ: 148329
Закрепляющий пример на рекурсию 16 задания из ЕГЭ по информатике 2022.
Задача(Две функции)
Алгоритм вычисления значения функций F(n) и G(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 0, если n <= 2,
F(n) = G(n — 2), если n > 2
G(n) = 0, n <= 1,
G(n) = F(n — 1) + n, если n > 1
Чему равно значение функции F(8)? В ответе запишите только натуральное число.
Решение:
# Сами функции def F(n): if n<=2: return 0 if n>2: return G(n-2) def G(n): if n<=1: return 0 if n>1: return F(n-1)+n # Основная часть программы print(F(8))
Получается ответ 9.
Ответ: 9
Задача (Количество значений)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2*n*n*n + 1, при n > 25
F(n) = F(n+2) + 2*F(n+3), при n ≤ 25
Определите количество натуральных значений n из отрезка [1; 1000], для которых значение F(n) кратно 11.
Решение:
# Сама функция def F(n): if n>25: return 2*n*n*n + 1 if n<=25: return F(n+2) + 2*F(n+3) k=0 # Перебираем диапазон for i in range(1, 1001): if F(i)%11==0: k=k+1 print(k)
В начале формируем функцию F. Затем перебираем числа из диапазона от 1 до 1000. Каждое число подставляем в функцию F. Если значение функции F делится на 11, то мы зачитываем такое значение i.
В ответе получается 91.
Ответ: 91
Задача (Используем глобальную переменную)
Решение:
При решении этой задачи можно применить глобальную переменную.
def F(n): global s s=s+1 if n>=1: s=s+1 F(n-1) F(n-2) s=s+1 s=0 F(35) print(s)
Здесь внутри функции заводим глобальную переменную s, которая будет подсчитывать количество напечатанных звёздочек. Теперь эту переменную видно при любом вызове функции, и при каждом вызове функции она будет одна и та же переменная. Вместо печати звёздочек пишем конструкцию s=s+1.
В основной части программы перед первым запуском функции переменной s присваиваем 0.
Программа может немного медленно работать из-за большой глубины рекурсии, но через минуту выведет число 96631265.
Ответ: 96631265
Новые тенденции
В последнее время мы видим тенденцию в 16 задании из ЕГЭ по информатике 2023, что теперь мало переписать функцию и её запустить. Необходимо подумать, как можно преобразовать то рекурсивное выражение, которое нужно вычислить.
Задача (Новое веяние)
(К. Багдасарян) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2, если n = 1,
F(n) = 2 · F(n – 1), если n > 1.
Чему равно значение выражения F(1900)/21890 ?
Решение:
1 Способ (Аналитическое решение)
Если мы просто перепишем функцию и попытаемся вычислить выражение F(1900)/21890, то получим ошибку RecursionError: maximum recursion depth exceeded. Возникает она из-за слишком большой цепочки вызовов функции.
В подобных задачах нужно попытаться самому упростить выражение, которое пытаемся вычислить. Посмотрим, что из себя представляет функция.
F(1900) = 2*F(1899) = 2*2*F(1898) = … 21900
Тогда
F(1900)/21890 = 21900/21890 = 210 = 1024
Получается 1024.
2 Способ (Через lru_cache)
Чтобы уменьшить цепочку вызовов функции, можно использовать инструмент lru_cache.
from functools import lru_cache @lru_cache(None) def F(n): if n==1: return 2 if n>1: return 2*F(n-1) for i in range(2, 1900): F(i) print(F(1900)/2**1890)
В задаче функция опирается на значение функции от n-1 и т.д. За счёт этого происходят длинные вычисления для каждого числа n.
Использовав инструмент lru_cache, мы пробегаемся в цикле по значениям n в возрастающем порядке, и для каждого значения сохраняем результаты функции. Таким образом, вычисляя очередное значение, программа опирается на уже готовый результат, тем самым цепочка вызовов функции будет маленькой.
Ответ: 1024
Задача(Новое веяние, закрепление)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n ≤ 2;
F(n) = n * F(n-2), если n > 2.
Чему равно значение выражение F(3000)/F(2996) ?
Решение:
1 Способ (Аналитическое решение)
Начнём расписывать F(3000).
F(3000) = 3000*F(2998) = 3000*2998*F(2996)
Получается:
F(3000)/F(2996) = 3000*2998*F(2996)/F(2996) = 3000*2998 = 8994000
2 Способ (Через lru_cache)
from functools import lru_cache @lru_cache(None) def F(n): if n<=2: return 1 if n>2: return n*F(n-2) for i in range(2, 3000): F(i) print(F(3000)/F(2996))
Ответ: 8994000
Задача (Вперёд к победе!)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n=1;
F(n) = 2 при n=2;
F(n) = n*(n-1) + F(n-1) + F(n-2), если n > 2.
Чему равно значение функции F(2023) — F(2021) — 2*F(2020) — F(2019)?
Решение:
1 Способ (Аналитическое решение)
F(2023) = 2023*2022 + F(2022) + F(2021) =
= 2023*2022 + 2022*2021 + F(2021) + F(2020) + F(2021) =
=2023*2022 + 2022*2021 + 2021*2020 + F(2020) + F(2019) + F(2020) + F(2021) =
2023*2022 + 2022*2021 + 2021*2020 + 2*F(2020) + F(2019) + F(2021) =
2023*2022 + 2022*2021 + 2021*2020 + F(2021) + 2*F(2020) + F(2019)
Если подставим полученный результат в выражение, которое нужно найти, то получим:
2023*2022 + 2022*2021 + 2021*2020 = 12259388
2 Способ (Через lru_cache)
from functools import lru_cache @lru_cache(None) def F(n): if n==1: return 1 if n==2: return 2 if n>2: return n*(n-1) + F(n-1) + F(n-2) for i in range(2, 2023): F(i) print(F(2023) - F(2021) -2*F(2020) - F(2019))
Ответ: 12259388
Удачи при решении 16 задания из ЕГЭ по информатике 2022.
А если промежуток намного больше будет? например не [1, 1000], а [1,500 000 000]? пк зависнет просто.. можно кроме как разбивать промежуток много на разных программ решить такую задачу?
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
def F(n):
print(n)
if n > 0:
F(n — 1)
F(n — 3)
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(5)?
А можете показать как это через python решать ?