Главная Посты Курсы Связь О сайте

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



Шестнадцатое задание из ЕГЭ по информатике 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

Задача (Используем глобальную переменную)
ЕГЭ по информатике - задание 16 (Глобальная переменная)
Решение:

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


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.






05-01-2022 в 11:50:42





Похожая статья:

ЕГЭ по информатике 2022 - Задание 15 (Простым языком)

Сегодняшний урок посвящён 15 заданию из ЕГЭ по информатике 2022. Темой...

Категория: ЕГЭ  Подкатегория: -
Дата: 15-01-2018 в 16:47:34 3


Комментарии:

Ты офигенный, спасибо за то ,что ты так стараешься и подробно объясняешь!
Никита 05-01-2022 в 14:52:23



Оставить коментарий:



Напишите email, чтобы получать сообщения о новых комментариях (необязательно):


Задача против робота. Расположите картинки горизонтально: