ЕГЭ по информатике задание 11
Тема: «Рекурсивные алгоритмы»
Ниже на различных языках программирования записаны рекурсивные алгоритмы процедур F и G. Чему равна сумма чисел, напечатанных на экране при выполнении вызова F(22)?
Бейсик | Алгоритмический язык |
DECLARE SUB F(n) | алг F(цел n) |
DECLARE SUB G(n) | нач |
SUB F(n) | вывод n, ’ ’ |
PRINT n, ’ ’ | если mod(n,2)=0 то |
IF n MOD 2 = 0 THEN | F(n-l) |
F(n — 1) | иначе |
ELSE | G(div(n,5)) |
G(n \ 5) | все |
END IF | кон |
END SUB | алг G(цел n) |
SUB G(n) | нач |
IF n < > 1 THEN F(n + 4) | если n < >1 то F(n+4) все |
END SUB | кон |
Паскаль | Си |
procedure F(n:integer); forward; | void F(int n); |
procedure G(n:integer); forward; | void G(int n); |
procedure F(n: integer); | |
begin | void F(int n) { |
write(n, ’ ’); | printf(«%,d «, n); |
if n mod 2=0 then F(n-l) | if (n % 2 = = 0) F(n-l); |
else G(n div 5) | else G(n/5); |
end; | } |
procedure G(n: integer); | |
begin | void G(int n) { |
if n<>l then F(n+4); | if (n != 1) F(n+4);} |
end |
РЕШЕНИЕ
Еще один вид задания ЕГЭ по информатике задание 11
В данной задаче ЕГЭ по информатике используются две рекурсивные процедуры.
Процедура – это вспомогательный алгоритм (фрагмент кода программы), который служит для выполнения определенных действий.
Рекурсивной процедурой называется такая процедура, которая в процессе выполнения явно или неявно вызывает сама себя. Процесс обращения к такой функции называется рекурсией.
Разберем задание 11 из ЕГЭ по информатике на языке Паскаль:
Надо заметить, что оператор вывода находится в рекурсивной процедуре F write(n, ’ ’);
Это означает, что будут выводится числа только из процедуры F
Ход решения представлен в таблице:
Остается посчитать все вызванные числа процедуры F:
22 + 21 + 8 + 7 = 58
Ответ:58
Самостоятельная работа
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 2 при n ≤ 2;
F(n) = F(n − 1) + 3 × F(n − 2) при n > 2.
Чему равно значение функции F(5)?
В ответе запишите только натуральное число.Ответ напишите в комментариях этого поста
Данная задача была взята с открытого банка заданий ЕГЭ по информатике.