Как решать 16 задание в егэ по информатике на питоне

Задача 16 — рекурсивная функция

Задача 16 ЕГЭ по информатике посвящена рекурсивным функциям.

Рекурсивные функции — такие функции, которые обращаются к самим себе.

Рассмотрим задачу 16 из демонстрационного варианта ЕГЭ 2022 г. с сайта ФИПИ:

Вообще говоря, данная задача решается на бумаге. Для этого придется составить таблицу, содержащую значения F(1), F(2) и т.д. — до F(26) включительно. Но составлять таблицу из 26 строк вручную несколько трудоемко, да и вероятность ошибиться ненулевая. Гораздо проще составить эту таблицу в excel.

Но, на мой взгляд, ещё проще решать данную задачу программно.

Сначала напишем рекурсивную функцию на Питоне:

def F(n):
if n==1: return 1
if n%2 == 0: return n+F(n-1)
return 2*F(n-2)

Просто, не так ли? Мы практически переписали определение функции строчка в строчку.

А почему в последней строке нет условия? Всё очень просто: оператор return прекращает вычисление функции, поэтому если, например, n равно 1, то операторы после строки, в которой проверяется соответствующее условие, выполняться не будут. Поэтому если выполнение дошло до последней строки функции, то случаи n, равного единице и четного n исключены.

Теперь мы можем узнать ответ данной задачи, написав дополнительно лишь строку

(Ответ равен 4122.)

На сайте К.Полякова задачи на рекурсивные функции более сложны, но и их решить программным путем обычно очень просто.

Рассмотрим, например, задачу из варианта 8:

Приведем полную программу для решения этой задачи:

def F(n):
if n<2: return 1
if n%3 == 0: return F(n//3)-1
return F(n-1)+7

n=1
while True:
if F(n)==111:
print(n)
break
n += 1

Легко видеть, что мы организуем бесконечный цикл и последовательно вычисляем F(1), F(2) и т.д. Как только F(n) будет равно 111, это значение печатается и цикл прерывается.

В данном случае ответ равен 32804. Перебрать вручную такое количество значений n нереально, поэтому в данном случае программный способ — единственно разумный метод решения.

К сожалению, не всегда эти задачи решаются столь просто. Ниже будут рассмотрены некоторые «подводные камни», которые встречатся в задачах на рекурсию.

Недопустимо медленная рекурсивная функция

Рассмотрим такую задачу:

Пусть имеется следующая функция F(n):

Казалось бы, всё просто. Пишем программу из четырех строчек:

def F(n):
if n<3: return 1
return F(n-1)+F(n-2)
print (F(45))

Запускаем программу и. не можем дождаться, когда она выполнится и отпечатает результат.

В чем тут дело? А в том, что для того, чтобы вычислить, например, F(10), нам требуется вычислить F(9) и F(8). Для вычисления F(9) и F(8) будут вычислены F(8), F(7), F(7) и F(6). Как можно видеть, значения функции для одного и того же параметра многократно перевычисляются, а увеличение n на 1 приводит к увеличению объёма (и времени) вычислений примерно в два раза.

Вот таблица, показывающая время вычисления функции F(n) для различных n.

Как говорится, тенденция налицо, и понятно, что дождаться, когда такая функция вычислит F(45), непросто.

Какой же выход из данной ситуации?

Во-первых, можно перейти на какой-либо более эффективный язык (паскаль или C++). Но даже эти языки не спасут, если потребуется вычислить, скажем, F(100).

Во-вторых, в данном конкретном случае функция реализует вычисления членов ряда Фибоначчи, два первых члена которого — единицы, а каждый, начиная с третьего — это сумма двух предыдущих. Тогда члены нашего ряда легко получить с помощью нерекурсивной функции:

def F(n):
if n<3:
return 1
f1=1
f2=1
f3=f1+f2
i=3
while i<n:
f1=f2
f2=f3
f3=f1+f2
i += 1
return f3
print(F(45))

Эта программа выполняется мгновенно.

Но в случае более сложной функции написать её нерекурсивный эквивалент может оказаться непростым делом. Гораздо проще сделать так, чтобы ранее вычисленные значения нашей функции повторно не вычислялись. Для этого воспользуемся структурой данных, которая называется «ассоциативный массив» или «словарь». В этой структуре хранятся пары «ключ»-«значение». В нашем случае ключом будет входной параметр n, а значением — значение функции F(n).

Вот программа, использующая словарь:

def F(n):
if not n in f:
if n < 3:
f[n] = 1
else:
f[n] = F(n-1)+F(n-2)
return f[n]

Функция F(n) проверяет, есть ли значение n в словаре f. Если нет, то это значение вычисляется и заносится в словарь (в строках вида f[n]=. ). Если же такое значение уже есть, то ничего вычислять не надо. В последней строке функция возвращает значение f[n] из словаря f.

Перед вызовом функции в основной программе создается пустой словарь f (в строке f=<>).

Если воспользоваться условным выражением if-else, то вышеприведенную программу можно сильно сократить:

def F(n):
if not n in f:
f[n] = 1 if n < 3 else F(n-1)+F(n-2)
return f[n]

16 задание ЕГЭ по информатике [закрыт]

Вопрос вызван проблемой, которая больше не воспроизводится, или опечаткой. Хотя похожие вопросы могут быть уместны на этом сайте, решение для этого вопроса вряд ли поможет будущим посетителям. Обычно можно избежать подобных вопросов написанием и исследованием минимальной программы для воспроизведения проблемы до публикации вопроса.

Закрыт 1 год назад .

Помогите решить задание. Мой код выдаёт не тот ответ. Правильный ответ: 384

ЗаPython’ил ЕГЭ на сотку или почему Python поможет на ЕГЭ

Доброго времени суток каждому жителю Хабрвилля! Давненько я не писал статей! Пора это исправить!

В сегодняшней статье поговорим о насущной для многих выпускников школ теме — ЕГЭ. Да-да-да! Я знаю, что Хабр — это сообщество разработчиков, а не начинающих айтишников, но сейчас ребятам как никогда нужна поддержка именно сообщества. Ребят опять посадили на дистант. Пока не ясно на какой период, но уже сейчас можно сказать, что ЕГЭ по информатике будет на компьютерах и его можно зарешать при помощи языка Python.

Вот я и подумал, чтобы не получилось как в песне, стоит этим заняться. Я расскажу про все задачи первой части и их решения на примере демо варианта ЕГЭ за октябрь.

Всех желающих — приглашаю ниже!

Быстрый перевод из системы в систему

В Python есть интересные функции bin() , oct() и hex() . Работают данные функции очень просто:

Вывод в интерпретационном режиме

Как вы видите, выводится строка, где 0b — означает, что число далее в двоичной системе счисления, 0o — в восьмеричной, а 0x — в шестнадцатеричной. Но это стандартные системы, а есть и необычные.

Давайте посмотрим и на них:

Данная программа будет работать при переводе из десятичной системы счисления в любую до 9, так как у нас нет букв. Давайте добавим буквы:

Способ объёмен, но понятен. Теперь давайте используем тот же функцию перевода из любой системы счисления в любую:

Вызвав функцию вывода print(convert_base(156, 16, 10)) мы переведём 156 из 10 в 16 систему счисления, а введя print(convert_base(’23’, 21, 4)) переведёт 23 из 4-ичной в 21-ичную систему (ответ: B).

Задача 2

Все задания беру из первого октябрьского варианта (он же вариант № 9325894) с сайта Решу.ЕГЭ.

Решение данной задачи совсем простое: банальный перебор.

Нам вывелась вся таблица истинности (1 = True, 0 = False). Но это не очень удобно. Обратите внимание, что в задании, функция равно 0, так и давайте подправим код:

Далее — простой анализ.

Задача 5

Данная задача легко решается простой последовательностью действий в интерпретационном режиме:

Задача 6

Перепечатали и получили ответ:

Задача 12

В очередной раз, просто заменим слова на код:

Задача 14

Компьютер железный, он всё посчитает:

Задача 16

Опять же, просто дублируем программу в python:

Задача 17

Задача с файлом. Самое сложное — достать данные из файла. Но где наша не пропадала?!

Немного пояснений. Функция with() открывает файл считывает данные при помощи функции read() и закрывает файл. В остальном — задача стандартна.

Задача 19, 20 и 21

Все три задачи — задачи на рекурсию. Задачи идентичны, а вопросы разные. Итак, первая задача:

Пишем рекурсивную функцию и цикл перебора S:

Немного пояснений. В рекурсивной функции существует 3 переменные x — число камней в первой куче, y — число камней во второй куче, p — позиция. Позиция рассчитывается по таблице:

ЕГЭ по информатике 2022 — Задание 16 (Рекурсия)

Шестнадцатое задание из ЕГЭ по информатике 2022 даётся на рекурсию.

Это задание нужно делать с помощью компьютера.

В программировании рекурсией называется процесс, когда функция вызывает сама себя или, когда две функции попарно вызывают друг друга.

Мы будем писать все программы на языке программирования Python.

Что такое Функция в языке программирования Python ?

Рассмотрим пример функции, которая суммирует два числа!

Здесь функция 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)?

Напишем программу для решения данной задачи. В начале опишем все правила, которые даны в условии задачи для функции. В основной части программы запустим эту функцию.

После запуска рекурсивной функции программа выведет ответ 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)? В ответе запишите только натуральное число.

Ответ получается 148329.

Ответ: 148329

Закрепляющий пример на рекурсию 16 задания из ЕГЭ по информатике 2022.

Алгоритм вычисления значения функций F(n) и G(n), где n — натуральное число, задан следующими соотношениями:

F(n) = 0, если n 2

Чему равно значение функции F(8)? В ответе запишите только натуральное число.

Получается ответ 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.

В начале формируем функцию F. Затем перебираем числа из диапазона от 1 до 1000. Каждое число подставляем в функцию F. Если значение функции F делится на 11, то мы зачитываем такое значение i.

В ответе получается 91.

Задача (Используем глобальную переменную)

Решение:

При решении этой задачи можно применить глобальную переменную.

Здесь внутри функции заводим глобальную переменную 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)/2 1890 ?

1 Способ (Аналитическое решение)

Если мы просто перепишем функцию и попытаемся вычислить выражение F(1900)/2 1890 , то получим ошибку RecursionError: maximum recursion depth exceeded . Возникает она из-за слишком большой цепочки вызовов функции.

В подобных задачах нужно попытаться самому упростить выражение, которое пытаемся вычислить. Посмотрим, что из себя представляет функция.

F(1900) = 2*F(1899) = 2*2*F(1898) = . 2 1900

F(1900)/2 1890 = 2 1900 /2 1890 = 2 10 = 1024

Получается 1024.

2 Способ (Через lru_cache)

Чтобы уменьшить цепочку вызовов функции, можно использовать инструмент lru_cache.

В задаче функция опирается на значение функции от 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)

Ответ: 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)

Если подставим полученный результат в выражение, которое нужно найти, то получим: