Шестнадцатое задание из ЕГЭ по информатике 2021 даётся на рекурсию.
Это задание нужно делать с помощью компьютера.
В программировании рекурсией называется процесс, когда функция (процедура) вызывает сама себя или, когда две функции попарно вызывают друг друга.
Мы будем писать все программы на языке программирования Pascal ABC.
Что такое Функция в языке программирования Паскаль ?
Рассмотрим пример функции, которая суммирует два числа!
var a, b, summa: integer; // Функция, которая суммирует два числа. function F(x:integer; y:integer):integer; begin F := x + y; end; BEGIN Readln(a); Readln(b); summa := F(a, b); WriteLn(summa); END.
Здесь функция F, которая суммирует два числа.
В главной часте программы, которая заключена между BEGIN и END, запрашиваются два числа с клавиатуры: a и b! Эти два числа передаются в функцию F. В функции эти числа кладутся в локальные переменные x и y. Переменные x и y суммируются, и результатом работы функции будет сумма переменных a и b.
Результат работы функции будет помещён в переменную summa (В строке summa := F(a, b)).
Таким образом, в переменной summa будет сумма двух переменных a и b.
Значение, которое вернёт функция, указано в строчке F := x + y;
Функции позволяют сократить программный код для однотипных расчётов.
Отличие функций от процедур в языке программирования Паскаль заключается в том, что функция возвращает значение, которое можно присвоить переменной, а процедура - нет.
Ещё важные моменты для 16 задания из ЕГЭ по информатике 2021
Команда "условие" в языке программирования Паскаль:
Сложное условие:
if (x > 0) and (x < 100) then a := a + 1;
Чтобы выполнилась строчка: a := a + 1; необходимо, чтобы верно было и первое выражение в скобках, и второе.
Чтобы записать условие, где срабатывает хотя бы одно выражение, необходимо воспользоваться союзом or (или):
if (x > 10) or (x = 5) then a := a + 1;
Если мы используем сложное условие (т.е. несколько выражений), то ОБЯЗАТЕЛЬНО необходимо ставить скобки !!!
Ещё нужно знать:
Пример: x := 5 mod 2; // В переменной x будет 1, т.е. остаток от деления 5 на 2
Проверить кратно ли число другому числу (Делится ли нацело):
if x mod 3 = 0 then … // Если остаток от деления на 3 равен нулю (Т.е. если переменная x делится нацело на 3), то…
Определить на что оканчивается число:
x :=a mod 10; // Чтобы определить на какую цифру оканчивается число, необходимо найти остаток от деления на 10.if x mod 10 = 1 then … // Если переменная x оканчивается на 1, то…
Тренировочные задачи 16 задания из ЕГЭ по информатике 2021
Задача (Стандартная)
Алгоритм вычисления значения функции 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)?
Решение:
Напишем программу для решения данной задачи. В начале опишем все правила, которые даны в условии задачи для функции. В основной части программы запустим эту функцию.
//Сама функция function F(n:integer):integer; begin if n = 1 then F := 1; if n mod 2 = 0 then F := n + F(n-1); if (n > 1) and (n mod 2 <> 0) then F := 3 * F(n - 2); end; //Основная часть программы, где запускаем функцию. BEGIN WriteLn(F(25)); END.
После запуска рекурсивной функции программа выведет ответ 531441.
Выражение n mod 2 <> 0 (остаток от деления на "2" не равен нулю) обозначает нечётное число.
Ответ: 531441
Продолжаем тренировку по подготовке к 16 заданию ЕГЭ по информатике 2021.
Задача (Продолжаем подготовку)
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(1) = 1
F(2) = 3
F(n) = F(n–1) * n + F(n–2) * (n – 1) , при n > 2
Чему равно значение функции F(8)? В ответе запишите только натуральное число.
Решение:
//Сама функция function F(n:integer):integer; begin if n = 1 then F := 1; if n = 2 then F := 3; if n > 2 then F := F(n - 1) * n + F(n - 2) * (n - 1); end; //Основная часть программы, где запускаем функцию. BEGIN WriteLn(F(8)); END.
Ответ получается 148329.
Ответ: 148329
Закрепляющий пример на рекурсию 16 задания из ЕГЭ по информатике 2021.
Задача(Две функции)
Алгоритм вычисления значения функций 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)? В ответе запишите только натуральное число.
Решение:
function G(n: integer):integer; forward; //Функция F function F(n:integer):integer; begin if n > 2 then F:= G(n - 2) else F:=0; end; //Функция G function G(n:integer):integer; begin if n > 1 then G:= F(n - 1) + n else G:=0; end; //Основная часть программы, где запускаем функцию. BEGIN WriteLn(F(8)); END.
Получается ответ 9.
Обратите внимание на строчку: "function G(n: integer):integer; forward;". Она пишется потому, что мы обращаемся в функции F к функции G, но функция G ещё не написана. Поэтому обязательно нужно её "объявить" в начале, используя слово forward.
Ответ: 9
Удачи при решении 16 задания из ЕГЭ по информатике 2021.
