ЕГЭ по информатике задание 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(« |
| if n mod 2=0 then F(n-l) | if (n |
| 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)?
В ответе запишите только натуральное число.Ответ напишите в комментариях этого поста
Данная задача была взята с открытого банка заданий ЕГЭ по информатике.
