Шестнадцатое задание из ЕГЭ по информатике 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 задания из ЕГЭ по информатике 2022
Задача (Стандартная)
Алгоритм вычисления значения функции 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 задания из ЕГЭ по информатике 2022.
Оставить коментарий: