Рекурсия. Разбор заданий № 16 ЕГЭ по информатике
Учитель информатики МОБУ «ССОШ №1»
Поречная Н.И.
Рекурсия
Рекурсия – это приём программирования, полезный в ситуациях, когда задача может быть естественно разделена на несколько аналогичных, но более простых задач. Или когда задача может быть упрощена до несложных действий плюс простой вариант той же задачи.
Числа Фибоначчи: 1,1,2,3,5,8,13,21,…
F(1)=1
F(2)=1
F(n)=F(n-2)+F(n-1), n>2
Проблемы рекурсии
1. Повторное вычисление одних и тех же значений при больших значения n.
Глубина рекурсии — это длина максимального пути по стрелочкам из вершины рекурсивного дерева до одного из элементарных (базовых) значений функции.
Основная ошибка : дерево рекурсивных вызовов может оказаться бесконечным и компьютер «зависнет». Процесс сведения задачи к более простым должен быть конечным.
Решение:
ЕГЭ 2022
Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:�
F(n) = 2, если n < 3�F(n) = 2·F(n – 2) - F(n – 1) + 2, если n > 2 и число n чётное,�F(n) = 2·F(n – 1) - F(n – 2) - 2, если n > 2 и число n нечётное.
Определите значение F(17).
Python:
def f(n):
if (n>0 and n<3): return 2
if (n>2 and n%2 == 0): return 2*f(n-2) - f(n-1) +2
if (n>2 and n%2 != 0): return 2*f(n-1) - f(n-2) -2
print (f(17))
ДЕМО 2023
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1; F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения (F(2023) - F(2022)) ?
Python:
def F(n):
if (n>1):
return n* F(n-1)
if n ==1:
return 1
print (F(2023)-F(2022))
Решение 1. �Увеличение глубины рекурсии
Модуль sys
Модуль sys в Python предоставляет простые функции, которые позволяют напрямую взаимодействовать с интерпретатором, изменять настройки по умолчанию.
sys.getrecursionlimit() - возвращает предельное значение глубины рекурсии.
sys.setrecursionlimit() – устанавливает заданное значение глубины рекурсии
По умолчанию глубина рекурсии в Python равна 100
Решение 1. �Увеличение глубины рекурсии
from sys import *
setrecursionlimit(10000)
def F(n):
if (n>1):
return n* F(n-1)
if n ==1:
return 1
print (F(2023)-F(2022))
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1; F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения (F(2023) - F(2022)) ?
Решение 2. �Сохранение ранее вычисленных значений
Алгоритм:
cache = {}
def F(n):
if n not in cache:
if (n>1): cache[n] = n* F(n-1)
if n ==1: cache[n] = 1
return cache[n]
for i in range (1,2024):
F(i)
print (F(2023)-F(2022))
Если дерево рекурсивных вызовов бесконечно
Рекурсия с исключениями
(№ 3698) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:�F(n) = n, при n ≤ 5,�F(n) = n + F(n/2 – 3), когда n > 5 и делится на 8,�F(n) = n + F(n + 4) , когда n > 5 и не делится на 8.Назовите максимальное значение n, для которого возможно вычислить F(n).
def f(n):
if (n<=5): return n
if n >5 and n%8==0: return n+f(n/2-3)
if n >5 and n%8!=0: return n+f(n+4)
for n in range(0,1000):
try:
print(n,f(n))
except:
...
Самый простейший пример исключения - деление на ноль:
try – инструкция, которая может породить исключение; except – перехват исключений (ошибок) и их потомков.
Анализ рекурсивной функции
Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
F(0) = 0;
F(n) = F(n − 1) + 1, если n нечётно;
F(n) = F(n / 2), если n > 0 и при этом n чётно.
Укажите количество таких значений n < 1 000 000 000, для которых F(n) = 2.
Анализ рекурсивной функции
def f(n):
if n == 0: return 0
if (n>0) and n%2!=0: return f(n-1)+1
if n>0 and n%2 == 0: return f(n/2)
for i in range(0, 10):
print(i,bin(i)[2:],f(i))
c = 0
for i in range (0, 50):
for j in range(i+1, 50):
a = 2**i+2**j
if a < 1000000000:
c=c+1
print(c)
Сколько чисел, двоичная запись которых содержит две «1» находятся в интервале от 0 до 1000000000.
Две единицы в записи числа появятся если 2i+2j
2i = 10…0
i
СПАСИБО ЗА ВНИМАНИЕ!