Презентация - "Презентация по информатике на тему "Методы решения задач ЕГЭ №16" по информатике (11 класс)"

Подготовка к КЕГЭ по информатике в 2022г.
Методы решения задач ЕГЭ №16 по информатике
Учитель информатики
МАОУ «МСОШ №16»
г. Миасс
Горяинов С.И.
Миасс, 2022

Задание №16
(базовый уровень, время 5 минуты)
Тема: Рекуррентные соотношения

Спецификация: Строить информационные модели объектов, систем и процессов в виде алгоритмов

Задание №16
Что проверяется:
1.5.3. Рекурсивные алгоритмы
1.1.3. Овладение понятием сложности алгоритма, знание основных алгоритмов обработки числовой и текстовой информации, алгоритмов поиска и сортировки

Что нужно помнить
Описание пользовательских функций в Python
def имя_функции(аргумент1, аргумент2, ...):
    тело_функции
В данном случае имя_функции – это любое допустимое имя, созданное по тем же правилам, что и имена переменных;
аргумент1, аргумент2, … - список аргументов функции, их может не быть совсем;
тело_функции – это код, который должен выполняться при вызове функции.
Пример простейшей функции:





Запись my_function(5) называется вызовом функции – в этом случае число 5 попадает в переменную x в функцию, после чего в качестве результата работы функции возвращается (при помощи ключевого слова return) значение x * x.

Примеры функций
Сумма цифр числа
Перевод в систему счисления n 𝒏≤𝟗

Рекурсия
Рекурсия – это такая ситуация, когда функция вызывает саму себя с новыми аргументами внутри своего тела.
Рассмотренные выше функции можно выразить рекурсивно:

Примеры заданий
Определите наименьшее значение n, при котором сумма чисел, которые будут выведены при вызове F(n), будет больше 200000. Запишите в ответе сначала найденное значение n, а затем через пробел – соответствующую сумму выведенных чисел.
def F( n ):
print(n-2)
if n > 3:
print(n+5)
F(n-5)
F(n-9)

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

Примеры заданий
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения F(2023) / F(2020)?
В данной задаче функция рекурсивно вычисляет факториал числа. Проблемой будет являться вычисление значения F(2020) и F(2023), так как глубина рекурсии в Python ограничена. Чтобы обойти эту проблему, можно использовать меморизацию:

Место для формулы.
Другим вариантом решения задачи может быть просто вычисление частного между факториалами двух чисел
2023! 2020! = 2020!∙2021∙2022∙2023 2020! =
=2021∙2022∙2023=8 266 912 626

Примеры заданий
Алгоритм вычисления функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = n, при n  3,
F(n) = 3*n + F(n / 3 + 2), когда n > 3 и делится на 5,
F(n) = 5*n - F(n + 3) , когда n > 3 и не делится на 5.
Назовите минимальное значение n, для которого F(n) определено и больше 1000.
Для решения задачи будем использовать глобальную переменную, в которой будет подсчитываться количество вызовов функции F. Если это количество превысит значение, например, 900, значит, можно считать, что эта функция при заданных аргументах образует бесконечную рекурсию вызовов и никогда не заканчивается.

Примеры заданий