Задача 16 — рекурсивная функция
Задача 16 ЕГЭ по информатике посвящена рекурсивным функциям.
Рекурсивные функции — такие функции, которые обращаются к самим себе.
Рассмотрим задачу 16 из демонстрационного варианта ЕГЭ 2022 г. с сайта ФИПИ:
Вообще говоря, данная задача решается на бумаге. Для этого придется составить таблицу, содержащую значения 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 исключены.
Теперь мы можем узнать ответ данной задачи, написав дополнительно лишь строку
(Ответ равен 4122.)
На сайте К.Полякова задачи на рекурсивные функции более сложны, но и их решить программным путем обычно очень просто.
Рассмотрим, например, задачу из варианта 8:
Приведем полную программу для решения этой задачи:
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):
Казалось бы, всё просто. Пишем программу из четырех строчек:
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(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]
1. Простое вычисление заданного значения рекуррентной последовательности
Рекомендуется повторить определение числовой последовательности и способы ее задания. Удобно, например, воспользоваться образовательной платформой ЯКласс: https://www.yaklass.ru/p/algebra/9-klass .
1.1. Ручные вычисления
Алгоритм вычисления значения функции F ( n ), где n – натуральное число, задан следующими соотношениями:
F ( n ) = 4 при n = 1, n = 2 и n = 3;
F ( n ) = 5 F ( n – 3), если n делится на 4 нацело ;
F ( n ) = 2 F ( n – 1) + 4 n , если n > 3 и не делится на 4 нацело .
Чему равно значение функции F (16)?
F(6) = 2F(5) + 4 × 6 = 120 + 24 = 144
F(7) = 2F(6) + 4 × 7 = 288 + 28 = 316
F(9) = 2F(8) + 4 × 9 = 600 + 36 = 636
F(10) = 2F(9) + 4 × 10 = 1272 + 40 = 1312
F(11) = 2F(10) + 4 × 11 = 2624 + 44 = 2668
F(13) = 2F(12) + 4 × 13 = 6360 + 52 = 6412
F(14) = 2F(13) + 4 × 14 = 12824 + 56 = 12880
F(15) = 2F(14) + 4 × 15 = 25760 + 60 = 25820
F(16) = 5F(13) = 32060
Алгоритм вычисления значения функции F ( n ), где n – натуральное число, задан следующими соотношениями:
F ( n ) = 1 при n = 1;
F ( n ) = n + 2 F ( n – 1), если n четно;
F ( n ) = 1 + 3 F ( n – 2), если n > 1 и нечетно.
Чему равно значение функции F (17)?
№ 16 (вариант 14) [1]
Алгоритм вычисления значения функции F ( n ), где n – натуральное число, задан следующими соотношениями:
F ( n ) = 0 при n = 1;
F ( n ) = 1 при n = 2;
F ( n ) = 
, если n > 2 и при этом четно;
F ( n ) = 
, если n > 2 и при этом нечетно.
Чему равно значение функции F (12)?
Примечание. Квадратные скобки в выражении [х] применяются для обозначения целой части числа х.
1.2. Вычисление заданного члена рекуррентной последовательности с использованием
рекурсивной функции с помощью языка программирования
Важнейшим методологическим приемом программирования на таких языках, как Паскаль, является разбиение решаемой задачи на подзадачи – более простые, с точки зрения программирования, части исходной задачи. Алгоритмы решения таких задач называются вспомогательными алгоритмами – подпрограммами. В Паскале различаются два вида подпрограмм – процедуры и функции. [2]
Обучаясь решению заданий № 16 КЕГЭ, мы повторим применение обоих типов подпрограмм. Причем, рекурсивных, т.е. таких, что обращаются сами к себе. Но начнем с функций. При этом пока не будем особо обращать внимание на то, что функции рекурсивные. Использование функции для нахождения заданного члена рекуррентной последовательности рассмотрим на примере.
Далее, если не сказано иначе, задачи берутся с сайта К.Е. Полякова https://kpolyakov.spb.ru/school/ege.htm .
№ 4192. (П. Волгин) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 1
F(n) = F(n–1) + F(n–2), при чётном n > 0
F(n) = 1,5*F(n–1), при нечётном n > 0
Сколько различных цифр встречается в целой части значения функции F(15)?
Выше мы видим структуру программы.
1. Заголовок программы.
2. Раздел описаний.
3. Тело программы.
В данной задаче раздел описаний содержит только описание функции. Рассмотрим описание функции подробно:
function f ( n : integer ): real ; — заголовок функции.
Содержит: имя функции (в данном случае f );
тип аргумента (параметра функции n : integer )
и тип возвращаемого значения : real
В теле функции (заключенном между операторными скобками begin и end ; ) описывается алгоритм вычисления значения функции.
Параметр n называется формальным: то есть мы понимаем, что в теле программы функции будет передаваться какое-то целое число, подлежащее обработки.
В теле программы функция вызывается в данном случае в составе стандартной процедуры вывода с фактическим параметром 15.
Запустив программу на выполнение, мы получим результат 915.52734375 .
(№ 4191) (П. Волгин) Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
F(0) = 3
F(n) = F(n–1), при 0 < n ≤ 15
F(n) = 2,5*F(n–3), при 15 < n < 100
F(n) = 3,3*F(n–2), при n ≥ 100
С какой цифры начинается дробная часть значения функции F(100)?
Обратите внимание! В задачах № 4192 и 4191 мы имели дело с вещественной функцией целого аргумента. В дальнейшем, в основном, мы будем иметь дело с целой функцией целого аргумента .
(№ 4173) (Е. Джобс) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(0) = 1, F(1) = 3
F(n) = F(n–1) — F(n-2) + 3n, при n > 1.
Чему равно значение функции F(40)? В ответе запишите только целое число.
2. Использование цикла с параметром в теле программы
№ 3985. Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(0) = 0
F(n) = F(n/2), при чётном n > 0
F(n) = F(n — 1) + 3, при нечётном n > 0
Сколько существует значений n, принадлежащих отрезку [1; 1000], для которых F(n) равно 18?
Обратите внимание! Раздел описаний содержит описание переменных (которые будут использоваться в теле основной программы) и описание функции. В теле основной программы вызов функции осуществляется при проверке условия (фактическим параметром является параметр цикла i ).
(№ 3816) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = 1, при n < 2,
F(n) = F(n/3) — 1, когда n ≥ 2 и делится на 3,
F(n) = F(n — 1) + 17, когда n ≥ 2 и не делится на 3.
Назовите количество значений n на отрезке [1;100000], для которых F(n) равно 43.
(№ 4172) (Е. Джобс) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями:
F(n) = n + 3, при n ≤ 3
F(n) = F(n – 2) + n, при n > 3 и четном значении F(n-1),
F(n) = F(n – 2) + 2 × n, при n > 3 и нечетном значении F(n-1).
Определите сумму значений, являющихся результатом вызова функции для значений n в диапазоне [40; 50].
Указания к решению.
Программу на Паскале, аналогичную той, что написана для решения № 3985, написать можно. Однако работает она долго. Дело в том, что у рекурсивных алгоритмов высокая временная сложность. Почему – посмотрим далее. На своем компьютере (правда, он слабенький), я ждала 5 минут и не дождалась результата. Значения F (40), F (41), F (42) вычислялись у меня 13 секунд. А, чем больше аргумент, тем время вычисления больше. F (50) я уже тоже не дождалась.
1-й вариант . Не считать в теле программы сумму. Вычислить F (40) и F (41) (как в задачах раздела 1.2), а потом вручную посчитать остальные значения F (42), F (43), F (44), F (45), F (46), F (47), F (48), F (49), F (50) (как в задачах раздела 1.1). А потом посчитать сумму. В принципе, можно отдельно считать значения F ( i ), пока оно считается за разумное время. Чем больше i , тем время расчета больше.
2-й вариант. Использовать MS EXCEL .
1) В столбце А запишем значения n от 1 до 50 с помощью функции автозаполнения.
2) В столбце В будем вычислять значения F ( n ).
— В В1 введем формулу = А1 + 3 и с помощью автозаполнения скопируем ее в ячейки В2 и В3 (рисунок 1).
— В В4 введем формулу =B2+A4 (рисунок 2)
— В В5 введем формулу =B3+2*A5 (рисунок 3)
— Выделим ячейки В4 и В5 (обе) и с помощью автозаполнения скопируем их до ячейки В50.
— Выделим диапазон ячеек В40 : В50 и выполним для них операцию автосуммирования.
Математика 208
Здесь // обозначает деление нацело. В качестве ответа на задание выведите значение F(100).
2. Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n + 3, при n ≤ 18
F(n) = (n // 3) · F(n // 3) + n – 12, при n > 18, кратных 3
F(n) = F(n–1) + n · n + 5, при n > 18, не кратных 3
Здесь «//» обозначает деление нацело. Определите количество натуральных значений n из отрезка [1; 1000], для которых все цифры значения F(n) чётные.
16 задача ЕГЭ часть 1
Алгоритм вычисления значения функции 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)?
Вопрос 5
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(0) = 1, F(1) = 1
F(n) = 3*F(n–1) — F(n-2), при n > 1
Чему равно значение функции F(6)? В ответе запишите только целое число.
Вопрос 6
(№ 3698) Алгоритм вычисления значения функции F(n), где n – целое число, задан следующими соотношениями: