ЕГЭ по информатике задание 11
Тема: «Рекурсивные алгоритмы»
Ниже на трёх языках программирования записана рекурсивная функция (процедура) F.
Python | Паскаль | Си |
def F(n): print(n, end=») if n >= 5: F(n — 2) F(n — 1) F(n — 2) |
procedure F(n: integer); begin write(n); if n >= 5 then begin F(n — 2); F(n — 1); F(n — 2) end end; |
void F(int n) { printf(«%d», n); if (n >= 5) { F(n — 2); F(n — 1); F(n — 2); } } |
Что выведет программа при вызове F(6)? В ответе запишите последовательность выведенных цифр слитно (без пробелов).
Данный пример взят из открытого банка заданий по информатике на сайте http://fipi.ru
РЕШЕНИЕ
Еще один вид задания ЕГЭ по информатике задание 11
В данной задаче ЕГЭ по информатике используются одна рекурсивная процедура.
Процедура – это вспомогательный алгоритм (фрагмент кода программы), который служит для выполнения определенных действий.
Рекурсивной процедурой называется такая процедура, которая в процессе выполнения явно или неявно вызывает сама себя. Процесс обращения к такой функции называется рекурсией.
Разберем задание 11 из ЕГЭ по информатике на языке Паскаль. Для наглядности будем решать задачу в виде дерева.На узлах записаны значения параметров при вызове функции, а на ребрах(ветвях) порядок рекурсивных вызовов.
Таким образом, при вызове F(6) программа выведет последовательность цифр: 6453434. Для проверки результата воспользуемся программой Pascalabc или в online на сайте http://rextester.com/l/pascal
Ответ: 6453434
В некоторых задачах немного другой вопрос. Например, необходимо найти сумму чисел, которые будут выведены при вызове F(6). Решается задание точно также деревом, а затем складываются все выведенные числа: 6 + 4 + 5 + 3 +4 +3 +4 = 29
Самостоятельная работа
Ниже на трёх языках программирования записана рекурсивная функция (процедура) F.
Python Паскаль Си def F(n):
print(n, end=»)
if n >= 2:
F(n — 2)
F(n — 2)
F(n — 1)
procedure F(n: integer);
begin
write(n);
if n >= 2 then
begin
F(n — 2);
F(n — 2);
F(n — 1)
end
end;
void F(int n) {
printf(«%d», n);
if (n >= 2) {
F(n — 2);
F(n — 2);
F(n — 1);
}
}
Что выведет программа при вызове F(3). В ответе запишите последовательность выведенных цифр слитно (без пробелов).
Данная задача была взята с открытого банка заданий ЕГЭ по информатике.