Шестнадцатое задание из ЕГЭ по информатике 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 решать ?
Характеристика задания
1. Тип ответа: запись числового значения.
2. Структура содержания задания: дана рекурсивная функция.
3. Уровень сложности задания: повышенный.
4. Примерное время выполнения: (5) минут.
5. Количество баллов: (1).
6. Требуется специальное программное обеспечение: да.
7. Задание проверяет умение работать с рекурсивными алгоритмами, осуществлять вычисления с помощью языка программирования.
Пример задания (демоверсия (2022))
Алгоритм вычисления значения функции (F(n)), где (n) — натуральное число, задан следующими соотношениями:
(F(n)) (=) (1) при (n=1);
(F(n) = n + F(n-1)), если (n) чётно,
(F(n)) (= 2 × F(n-2)), если (n>1) и при этом (n) нечётно.
Чему равно значение функции (F(26))?
Как решать задание?
Задание можно решить «ручным» методом, т. е. самостоятельно посчитать функцию. Это займёт слишком много времени, поэтому лучше написать программу.
Что такое функция, можно вспомнить тут.
Что такое рекурсивный алгоритм, можно вспомнить тут.
Напишем программу
 |
Объявим функцию |
 |
Опишем первое условие: если (n=1), то… |
 |
Оператор return прекращает вычисление функции. При (n=1) функция закончит своё вычисление и будет равна (1) |
 |
В следующем условии будет определять чётность (n). % — это получение остатка от деления |
 |
Если (n) будет чётным, то выполним следующее действие: (n+f(n-1)) |
 |
Если (n) больше единицы и при этом нечётное… Напомним, знак (!=) обозначает «не равно» |
 |
Выполним действие: (2*f(n-2)) |
 |
Организуем вывод данных, в скобках укажем необходимое нам значение (n). Запустим программу |
Ответ: (4122).
В программировании рекурсия, или же рекурсивная функция — это такая функция, которая вызывает саму себя.
Рекурсивные функции с возвращаемыми значениями
Задание 6 (ИНФ-11 ЕГЭ 2023_ДЕМО)
Алгоритм вычисления значения функции F(n), где n – натуральное число,
задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения F(2023) / F(2020)?
Вариант программы 1
Лимит рекурсии по умолчанию в Python является 1000, вы получите ошибку « RecursionError: максимальная глубина рекурсии превышена в сравнении »
Это может быть исправлено, увеличивая предел рекурсиона в Python, ниже – фрагмент о том, как вы можете увеличить предел рекурсии.
import sys
sys.setrecursionlimit(2030)
Вариант программы 2
Алгоритмы, опирающиеся на несколько предыдущих значений
Задание 6 (Решу ЕГЭ)
Последовательность чисел Падована задается рекуррентным соотношением:
F(1) = 1
F(2) = 1
F(3) = 1
F(n) = F(n–3) + F(n–2), при n >3, где n – натуральное число.
Чему равно двенадцатое число в последовательности Падована?
В ответе запишите только натуральное число.
Задание 6 (Решу ЕГЭ)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1;
F(n) = n + F(n − 2), если n — нечётно, и n > 1;
F(n) = n × F(n − 1), если n — чётно.
Чему равно значение функции F(60)?
Алгоритмы, опирающиеся на несколько предыдущих значений
Задание 6 (Решу ЕГЭ)
Алгоритм вычисления значения функции F(n) и G(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 0
F(n) = F(n–1) + n, при n >1
G(1) = 1
G(n) = G(n–1) * n, при n >1
Чему равно значение функции F(5) + G(5)?
В ответе запишите только натуральное число.
Сложные задачи
Задание 6 (Поляков ЕГЭ)
(№ 5604) (А. Куканова) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = sqrt(n), если sqrt(n) – натуральное число,
F(n) = F(n + 1) + 1, если sqrt(n) – дробное число.
Чему равно значение выражения F(4850) + F(5000)?
При делении натурального числа на 2 мы получаем в остатке (%) или 0 или 1 (чётные и нечётные числа), таким образом проверяем, если корень дает четное или нечётное целое число, то выводим корень этого числа во всех остальных случаях применяет функцию F(n+1)+1
sqrt(n) запишем как n**0.5, что бы не подключать дополнительный математический модуль из библиотеки
Задание 6 (Поляков ЕГЭ)
Определите, сколько символов * выведет эта процедура при вызове F(140):
Алгоритмы, опирающиеся на несколько предыдущих значений
Задание 6 (Поляков ЕГЭ)
(№ 5604) (А. Куканова) Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = n!, если n ≥ 5000,
F(n) = 2 · F(n + 1) / (n + 1), если 1 ≤ n < 5000.
Чему равно значение выражения 1000 · F(7) / F(4)?
Примечание.
Факториал числа n, который обозначается как n!, вычисляется по формуле n!=1·2·…·n.
Модуль math – один из наиважнейших в Python. Этот модуль предоставляет обширный функционал для проведения вычислений с вещественными числами (числами с плавающей точкой).
Для использования этих функций в начале программы необходимо подключить модуль, что делается командой import:
# программный код
import math
num1 = math.sqrt(2) # вычисление корня квадратного из двух
Как можно заметить из примера выше, для вызова функции мы вынуждены указывать название модуля и символ точки. С другой стороны, если функции используются достаточно часто, то такой вызов (постоянное указание названия модуля и символа точки) может усложнить программу и сделать её менее читабельной. Для того, чтобы не указывать название модуля и символ точки при вызове функций, мы пишем следующий код:
# программный код
from math import *
Если нужно использовать только некоторые функции модуля, то мы можем импортировать только их следующим образом:
from math import sqrt, ceil, factorial
ещё не решила)
Вычисление значений рекурсивной
функции
Разбор заданий № 16 КЕГЭ-2021
(соответствует за да нию № 11 ЕГЭ 2020)
Проверяемые элементы содержания: Вычисление рекуррентных выражений. Индуктивное определение
объектов. Умение записать и исполнить ре курсивный вычислительный алгоритм,
заданный в виде рекуррентных соотношений.
Проверяемые умения или способы действий: Строить информационные модели объектов, систем и процессов в
виде алгоритмов.
(повышенный уровень, время – 9 мин)
Что нужно знать:
|
Рекурсия[1] — |
|||
|
процесса внутри самого этого объекта или процесса, |
|||
|
является частью самого |
|||
|
Рекурсия |
|||
|
основе заданных базовых |
|||
|
Рекурсивная функция[2] (от |
|||
|
f(n) числового |
|||
|
позволяет вычислять значения f(n) на |
|||
|
рассуждению по индукции. Чтобы вычисление |
|||
|
чтобы для некоторых n |
|||
|
(например, для n |
|||
|
Рекурсивно |
|||
|
самой с другими |
|||
|
● Конечная |
|||
|
конечного аргумента за конечное число рекурсивных |
|||
|
отдельно определённых частных случаев, вычисляемых |
|||
|
пример: |
|||
|
● Бесконечная |
|||
|
во всех случаях (по крайней мере, для некоторых из |
|||
|
могут задаваться бесконечные ряды, бесконечные |
|||
|
Примером рекурсии в математике является числовая |
|||
|
рекуррентной формулой, когда каждый следующий член последовательности |
|||
|
вычисляется как результат функции от n предыдущих |
|||
|
Фибоначчи). |
|||
|
Рекурсивные алгоритмы – |
|||
|
или через другие |
|||
|
В программировании рекурсия[3] — |
|||
|
непосредственно (простая рекурсия) или через |
|||
|
косвенная рекурсия), |
|||
|
функцию A. Рекурсивная программа |
|||
|
потенциально бесконечное вычисление, причём без явных повторений частей |
|||
|
программы и |
|||
|
Структурно |
|||
|
команду ветвления (выбор одной из двух или |
|||
|
условия (условий), которое в данном случае уместно |
|||
|
рекурсии»), |
|||
|
является рекурсивной и хотя бы одна — терминальной. Рекурсивная ветвь |
|||
|
выполняется, когда условие прекращения рекурсии ложно, |
|||
|
рекурсивный |
|||
|
Терминальная |
|||
|
возвращает некоторое значение, не выполняя рекурсивного вызова. Правильно |
|||
|
написанная |
|||
|
рекурсивных |
|||
|
результате чего цепочка последовательных рекурсивных вызовов прервётся и |
|||
|
выполнится возврат. |
|||
|
Помимо функций, выполняющих один |
|||
|
ветви, бывают случаи «параллельной рекурсии», |
|||
|
делается два или более рекурсивных вызова. |
|||
|
обработке сложных |
|||
|
Основной недостаток |
|||
|
Рекурсивным называется |
Рекуррентное |
||
|
Для того, чтобы |
В рекуррентном соот |
||
Рекомендации:
|
Задание |
|
алгоритма в одной из систем программирования, либо организацией цепочки |
|
вычислений в электронных |
Информационные ресурсы:
1.
Теория:
Интерактивный плакат «Фракталы» http://elementy.ru/posters/fractals;
Запись вспомогательных алгоритмов на языке Паскаль;
Функции;
Рекурсия в
Python; Программирование на python: Теоретический материал (Рекурсия)
2. Задания
для тренировки: ЕГЭ−2021, Информатика: задания, ответы, решения. Обучающая
система Дмитрия Гущина
3. Онлайн-тест
Константина Полякова для подготовки к ЕГЭ:
16 —
Рекурсивные алгоритмы (Паскаль).
16 — Рекурсивные алгоритмы (Python).
16 — Рекурсивные алгоритмы (C++).
За да ние № 16 (ДЕМО ФИПИ КЕГЭ-2021)
|
Алгоритм |
|
|
следующими |
|
|
F(n) = 1 при n = |
|
|
F(n) |
|
|
F(n) |
|
|
Чему равно значение функции F(26)? |
|
|
Решение: |
I вариант – решение в
электронных таблицах:
1.
Составим таблицу для n = 1÷26. Введем в ячейки B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:
2. С
помощью автозаполнения копируем формулы из диапазона C2:D2 в E2:AA2
II вариант – решение на
Python:
Ответ:
4122
За да ние № 16 (ЕГЭ−2021. Досрочная волна)
|
Алгоритм |
|
|
следующими |
|
|
F(n) = 1 при n = |
|
|
F(n) |
|
|
F(n) |
|
|
Чему равно значение функции F(24)? |
|
|
Решение: |
I
вариант – решение в электронных таблицах:
1. Составим таблицу для n
= 1÷24. Введем в ячейки B2, C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:
2. С
помощью автозаполнения копируем формулы из диапазона C2:D2 в
E2:Y2
II
вариант – решение на Python:
Ответ: 2072
Разбор заданий №16. Готовимся к
итоговой аттестации 2021. Лещинер, В.Р.[4]Вариант № 1
|
Алгоритм вычисления значения функции F(n), |
|
|
следующими |
|
|
F(n) = |
|
|
F(n) = 2×n + F(n |
|
|
F(n) = 3 × F(n — |
|
|
Чему равно значение функции F(18)? |
|
|
Решение: |
I
вариант – решение в электронных таблицах:
1. Составим таблицу для n
= 1÷18. Введем в ячейки B2, C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:
2. С
помощью автозаполнения копируем формулы из диапазона C2:D2 в
E2:S2
II
вариант – решение на Python:
Ответ:
6597
Вариант № 2
|
Алгоритм вычисления значения функции F(n), |
|
|
следующими |
|
|
F(n) = |
|
|
F(n) = 3×n + F(n |
|
|
F(n) = 3 × F(n — |
|
|
Чему равно значение функции F(20)? |
|
|
Решение: |
I
вариант – решение в электронных таблицах:
1. Составим таблицу для n
= 1÷20. Введем в ячейки B2, C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:
2. С
помощью автозаполнения копируем формулы из диапазона C2:D2 в
E2:U2
II
вариант – решение на Python:
Ответ:
19743
Задание № 16.1
|
Алгоритм вычисления значения функции F(n), |
|
|
следующими |
|
|
F(n) = 1 при |
|
|
F(n) = F(n — 1) + 2 × F(n — 2) при |
|
|
Чему равно значение функций F(7), |
|
|
В ответе запишите только натуральное |
|
|
Решение: |
I вариант – решение в
электронных таблицах:
1.
Составим таблицу для n = 1÷17. Введем в ячейки
B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:
2. С помощью автозаполнения
копируем формулы из ячейки D2 в диапазон E2:R2
II вариант – решение на
Python:
Ответ:
43, 1365, 43691
Задание № 16.2
|
Алгоритм вычисления значения функции F(n), |
|
|
следующими |
|
|
F(n) = 2 при п ≤ 2; |
|
|
F(n) = F(n — 1) + 3 × |
|
|
Чему равно значение функции F(5), |
|
|
В ответе запишите только натуральное число. |
|
|
Решение: |
I вариант – решение в
электронных таблицах:
1.
Составим таблицу для n = 1÷15. Введем в ячейки
B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:
2. С помощью автозаполнения
копируем формулы из ячейки D2 в диапазон E2:P2
II вариант – решение на
Python:
Ответ: 38, 2318, 150632
|
Задание № 16.3 |
||
|
Алгоритм вычисления значения функции F(n), |
||
|
следующими |
||
|
F(n) = n при п ≤ 2; |
||
|
F(n) = F(n — 1) + 3 × |
||
|
Чему равно значение функции F(6), |
||
|
В ответе запишите только натуральное число. |
||
|
Решение: |
||
I вариант – решение в
электронных таблицах:
1.
Составим таблицу для n = 1÷18. Введем в ячейки
B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:
2. С помощью автозаполнения копируем формулы из
ячейки D2 в диапазон E2:S2
II вариант – решение на
Python:
Ответ: 59, 8843, 1318811
|
Задание № 16.4 |
||
|
Алгоритм вычисления значения функции F(n), |
||
|
следующими |
||
|
F(n) = n + 1 при п ≤ 2; |
||
|
F(n) = F(n — 1) + 2 × |
||
|
Чему равно значение функции F(4), |
||
|
В ответе запишите только натуральное число. |
||
|
Решение: |
||
I вариант – решение в
электронных таблицах:
1.
Составим таблицу для n = 1÷14. Введем в ячейки
B2,
C2
и D2
формулы
соответствующие заданным рекуррентным соотношениям:
2. С помощью автозаполнения копируем формулы из
ячейки D2 в диапазон E2:O2
II вариант – решение на
Python:
Ответ: 13, 427, 13653
За да ние № 11 (ДЕМО ЕГЭ-2020 ФИПИ)
|
Ниже на пяти языках программирования |
||
|
Бейсик |
Python |
С++ |
|
SUB F(n) PRINT n, IF n >= 3 THEN F(n 2) F(n — 1) END IF END SUB |
def F(n): F(n // 2) F(n — 1) |
void F(int n) { std::cout << n; if (n F(n / 2); F(n — 1); } } |
|
Алгоритмический |
Паскаль |
|
|
алг F(div(n, 2)) F(n |
procedure F(n div 2); F(n |
|
|
Запишите подряд |
||
|
экран при выполнении |
||
|
котором они выводятся |
Решение:
|
f(5) |
5 |
>= 3 – yes |
|||||||
|
f(div(5,2)) |
2 |
>= 3 – not |
∎ |
||||||
|
f(5 — 1) |
4 |
>= 3 – yes |
|||||||
|
f(div(4,2)) |
2 |
>= 3 – not |
∎ |
||||||
|
f(4-1) |
3 |
>= 3 – yes |
|||||||
|
f(div(3,2)) |
1 |
>= 3 – not |
∎ |
||||||
|
f(3-1) |
2 |
>= 3 – not |
∎ |
||||||
|
Ответ: |
5 |
24 |
23 |
12 |
Ответ: 5242312
За да ние № 11 (ДЕМО ЕГЭ-2019 ФИПИ)
|
Ниже на пяти языках программирования |
||
|
Бейсик |
Python |
С++ |
|
SUB F(n) IF n > 0 THEN F(n — 1) PRINT n F(n — 2) END IF END SUB |
def F(n): if n > 0: F(n — 1) print(n) F(n — 2) |
void } } |
|
Алгоритмический |
Паскаль |
|
|
алг F(цел n) нач если n > 0 то F(n — 2) все кон |
procedure F(n: integer); begin if F(n — 2) end end; |
|
|
Запишите подряд |
||
|
экран при выполнении |
||
|
котором они выводятся |
Решение:
|
n=4 |
f(4) |
4 |
f(4-2) |
2 |
f(2-2) |
∎ |
|||||||||
|
F(n — 1) F(n — 2) |
f(3) |
3 |
f(3-2) |
1 |
f(1-2) |
∎ ↑ |
f(1) |
1 |
∎ ↑ |
||||||
|
f(2) |
2 |
f(2-2) |
∎ ↑ |
f(1-1) |
∎ ↑ |
f(0) |
∎ ↑ |
||||||||
|
f(1) |
1 |
f(1-2) |
∎ ↑ |
||||||||||||
|
f(0) |
∎ ↑ |
||||||||||||||
|
Ответ: |
1 |
2 |
3 |
1 |
4 |
1 |
2 |
Ответ: 1231412
За да ние № 11 (ДЕМО ЕГЭ-2018 ФИПИ)
|
Ниже на пяти языках программирования |
||
|
Бейсик |
Python |
С++ |
|
SUB F(n) IF n > 0 THEN PRINT n F(n — 3) F(n 3) END IF END SUB |
def F(n): if n > F(n // 3) |
void } } |
|
Алгоритмический |
Паскаль |
|
|
алг F(цел n) нач если n > 0 то F(n — 3) F(div(n, 3)) все кон |
procedure F(n: integer); begin if F(n div 3) end end; |
|
|
Запишите подряд |
||
|
экран при выполнении |
||
|
котором они выводятся |
Решение:
|
f(9) |
9 |
f(div(6, 3)) |
3 |
||||||||
|
⤷ |
f(9-3) |
6 |
f(div(6, 3)) |
2 |
⤴ |
f(3-3) |
∎ |
||||
|
⤷ |
f(6-3) |
3 |
f(div(3, 3)) |
1 |
⤴ |
f(2-3) |
∎ |
f(div(3,3)) |
1 |
||
|
⤷ |
f(3-3) |
⤴ |
f(1-3) |
∎ |
f(1-3) f(div(1,3)) |
∎ ∎ |
|||||
|
Ответ: |
9 |
6 |
3 |
1 |
2 |
3 |
1 |
Ответ: 9631231
Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.
Задача 16 ЕГЭ по информатике посвящена рекурсивным функциям.
Рекурсивные функции — такие функции, которые обращаются к самим себе.
Рассмотрим задачу 16 из демонстрационного варианта ЕГЭ 2022 г. с сайта ФИПИ:
Алгоритм вычисления значения функции F(n), где n – натуральное число,
задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n чётно,
F(n) = 2 × F(n − 2), если n > 1 и при этом n нечётно.
Чему равно значение функции F(26)?
Вообще говоря, данная задача решается на бумаге. Для этого придется составить таблицу, содержащую значения 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 исключены.
Теперь мы можем узнать ответ данной задачи, написав дополнительно лишь строку
print(F(26))
(Ответ равен 4122.)
На сайте К.Полякова задачи на рекурсивные функции более сложны, но и их решить программным путем обычно очень просто.
Рассмотрим, например, задачу из варианта 8:
(№ 3820) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = 1, при n < 2,
F(n) = F(n/3) — 1, когда n ≥ 2 и делится на 3,
F(n) = F(n — 1) + 7, когда n ≥ 2 и не делится на 3.
Назовите минимальное значение n, для которого F(n) равно 111.
Приведем полную программу для решения этой задачи:
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):
F(n)=1 при n<3;
F(n)=F(n-1)+F(n-2) при n>=3.
Чему равно F(45)?
Казалось бы, всё просто. Пишем программу из четырех строчек:
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.
| n | F(n) | Время, с |
| 33 | 3524578 | 1.40 |
| 34 | 5702887 | 2.31 |
| 35 | 9227465 | 4.21 |
| 36 | 14930352 | 6.91 |
| 37 | 24157817 | 11.24 |
| 38 | 39088169 | 18.93 |
| 39 | 63245986 | 31.45 |
| 40 | 102334155 | 57.24 |
| 41 | 165580141 | 104.53 |
Как говорится, тенденция налицо, и понятно, что дождаться, когда такая функция вычислит 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={}
print(F(45))
Функция 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]
f={}
print(F(45))
Когда рекурсия не завершается
(Продолжение следует немного позже.)
(c) Ю.Д.Красильников, 2021-2022 г.