ЕГЭ, вопрос 16: Б. Рекурсивный алгоритм
Проверяемые элементы содержания по спецификации (2021): Вычисление рекуррентных выражений.
Кодификатор 1.5.3/1.1.3. Уровень сложности П, 1 балл (был Б).
Время выполнения — 9 мин. (было 5).
Рекурсивный алгоритм по мнению разработчиков ЕГЭ это:
- Математическая функция, что наглядно проиллюстрировано заданиями без программирования.
- Программистская утопия, точнее говоря, крайне мало востребованная версия использования функций, скорее классическая основа для «подвешивания» компьютера в неявном бесконечном цикле.
При этом алгоритм подобного типа в значительной степени востребован в области обработки символов и шифровании.
Однако задание проверяет способность на определенный уровень абстрагирования. Если вы категорически не можете стабильно его выполнить, то стать программистом вам вряд ли суждено.
Решение может быть осуществлено как в уме, так и составлением таблиц состояния переменных. Истина, как всегда лежит посередине. То есть, в условиях экзамена, обходиться без записей — крайняя глупость. Но заполнение таблицы для 10–20 значений нужно крайне редко. Скорее речь идет о нахождении закономерности и расчете нескольких промежуточных значений. На это требуется 2–3 минуты, не более.
Задания
- Демо 2021 ().
- Демо 2020 (11). Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик Python SUB F(n)
PRINT n
IF n >= 3 THEN
F(n \ 2)
F(n - 1)
END IF
END SUBdef F(n):
print(n, end='')
if n >= 3:
F(n // 2)
F(n - 1)Алгоритмический язык Паскаль алг
F(цел n)
нач
вывод n
если n >= 3 то
F(div(n, 2))
F(n - 1) все
конprocedure F(n: integer);
begin
write(n);
if n >= 3 then
begin
F(n div 2);
F(n - 1)
end
end;C++ void F(int n) {
std::cout << n;
if (n >= 3) {
F(n / 2);
F(n - 1);
}
}
- Демо 2019 (11). Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик Python SUB F(n)
IF n > 0 THEN
F(n - 1)
PRINT n
F(n - 2)
END IF
END SUBdef F(n):
if n > 0:
F(n - 1)
print(n)
F(n - 2)Алгоритмический язык Паскаль алг F(цел n)
нач
если n > 0 то
F(n - 1)
вывод n
F(n - 2)
все
конprocedure F(n: integer);
begin
if n > 0 then
begin
F(n - 1);
write(n);
F(n - 2)
end
end;Си++ void F(int n){
if (n > 0){
F(n - 1);
std::cout << n;
F(n - 2);
}
}
- Демо 2018 (11). Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик Python SUB F(n)
IF n > 0 THEN
PRINT n
F(n - 3)
F(n \ 3)
END IF
END SUBdef F(n):
if n > 0:
print(n)
F(n - 3)
F(n // 3)Алгоритмический язык Паскаль алг F(цел n)
нач
если n > 0 то
вывод n
F(n - 3)
F(div(n, 3))
все
конprocedure F(n: integer);
begin
if n > 0 then
begin
write(n);
F(n - 3);
F(n div 3)
end
end;Си++ void F(int n){
if (n > 0){
std::cout <<n;
F(n - 3);
F(n / 3);
}
}
- D2018 (11). Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик Python SUB F(n)
IF n > 0 THEN
F(n - 1)
PRINT n
F(n \ 4)
END IF
END SUBdef F(n):
if n > 0:
F(n - 1)
print(n)
F(n // 4)Алгоритмический язык Паскаль алг F(цел n)
нач
если n > 0 то
F(n - 1)
вывод n
F(div(n, 4))
все
конprocedure F(n: integer);
begin
if n > 0 then
begin
F(n - 1);
write(n);
F(n div 4)
end
end;C++ void F(int n){
if (n > 0){
F(n - 1);
std::cout << n;
F(n / 4);
}
}
- R2018 (11). Ниже на четырех языках программирования записан рекурсивный алгоритм F.
Бейсик Python SUB F (n)
IF n > 0 THEN
F(n \ 4)
PRINT n
F(n - 1)
END IF
END SUBdef F(n):
if n > 0:
F(n // 4)
print(n)
F (n - 1)Си++ Паскаль void F(int n){
if (n > 0){
F(n / 4)
std::cout << n;
F(n - 1);
}
}procedure F(n: integer);
begin
if n > 0 then
begin
F(n div 4);
write(n);
F(n - 1);
end
end;
- Демо 2017 (11). Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик Python DECLARE SUB F(n)
SUB F(n)
IF n > 2 THEN
PRINT n
F(n - 3)
F(n — 4)
END IF
END SUBdef F(n):
if n > 2:
print(n)
F(n - 3)
F(n — 4)Алгоритмический язык Паскаль алг F(цел n)
нач
если n > 2 то
вывод n, нс
F(n - 3)
F(n — 4)
все
конprocedure F(n: integer);
begin
if n > 2 then begin
writeln(n);
F(n - 3);
F(n — 4)
end
end;Си void F(int n) {
if (n > 2) {
printf("%d\n", n);
F(n - 3);
F(n — 4);
}
}
- Демо 2016 (11). Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.
Бейсик Python DECLARE SUB F(n)
DECLARE SUB G(n)
SUB F(n)
IF n > 0 THEN G(n - 1)
END SUB
SUB G(n)
PRINT "*"
IF n > 1 THEN F(n - 3)
END SUBF(n):
if n > 0:
G(n - 1)
def G(n):
print("*")
if n > 1:
F(n - 3)Алгоритмический язык Паскаль алг F(цел n)
нач
если n > 0 то
G(n - 1)
все
кон
алг G(цел n)
нач
вывод "*"
если n > 1 то
F(n - 3)
все
конprocedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
begin
if n > 0 then
G(n - 1);
end;
procedure G(n: integer);
begin
writeln('*');
if n > 1 then
F(n - 3);
end;Си void F(int n);
void G(int n);
void F(int n){
if (n > 0)
G(n - 1);
}
void G(int n){
printf("*");
if (n > 1)
F(n - 3);
}
- Демо 2015 (11). Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик Python SUB F(n)
PRINT n
IF n < 5 THEN
F(n + 1)
F(n + 3)
END IF
END SUBdef F(n):
print(n)
if n < 5:
F(n + 1)
F(n + 3)Алгоритмический язык Паскаль алг F(цел n)
нач
вывод n, нс
если n < 5 то
F(n + 1)
F(n + 3)
все
конprocedure F(n: integer);
begin
writeln(n);
if n < 5 then
begin
F(n + 1);
F(n + 3)
end
endСи void F(int n)
{
printf("%d\n", n);
if (n < 5) {
F(n + 1);
F(n + 3);
}
}
- Демо 2014. Задание не вводилось, был просто вызов функции (B14): см. вопрос 21.
- Демо 2013. Задание не вводилось, был просто вызов функции (B14): см. вопрос 21.
- Демо 2012. Задание не вводилось, был просто вызов функции (B14): см. вопрос 21.
- Демо 2011. Задание не вводилось.
- Демо 2010. Задание не вводилось.
- Демо 2009. Задание не вводилось.
- Демо 2008. Задание не вводилось.
- (т2-2015/1)
- (т2-2015/2)
- с114 (11). Ниже на пяти языках программирования записаны две рекурсивные функции: F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n - 1) + G(n - 2)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n - 1) + F(n - 2)
ELSE
G = n+1
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 2 then
F := F(n - 1) + G(n - 2)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 2 then
G := G(n - 1) + F(n - 2)
else
G := n+1;
end;Си Алгоритмический язык int F(int n)
{
if (n > 2)
return F(n - 1) + G(n-2);
else return n;
}
int G(int n)
{
if (n > 2)
return G(n - 1) + F(n -2);
else return n+1;
}нач
если n > 2
то
знач := F(n - 1)+G(n - 2)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n - 1)+F(n - 2)
иначе
знач := n+1
все
конPython def F(n):
if n > 2:
return F(n - 1)+ G(n - 2)
else: return n
def G(n):
if n > 2:
return G(n - 1)+ F(n - 2)
else: return n+1
- с124 (11). Ниже на пяти языках программирования записаны две рекурсивные функции: F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n - 1) + G(n - 2)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n - 1) + F(n - 2)
ELSE
G = n+1
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 2 then
F := F(n - 1) + G(n - 2)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 2 then
G := G(n - 1) + F(n - 2)
else
G := n+1;
end;Си Алгоритмический язык int F(int n)
{
if (n > 2)
return F(n - 1) + G(n-2);
else return n;
}
int G(int n)
{
if (n > 2)
return G(n - 1) + F(n -2);
else return n+1;
}нач
если n > 2
то
знач := F(n - 1)+G(n - 2)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n - 1)+F(n - 2)
иначе
знач := n+1
все
конPython def F(n):
if n > 2:
return F(n - 1)+ G(n - 2)
else: return n
def G(n):
if n > 2:
return G(n - 1)+ F(n - 2)
else: return n+1
- с113 (11). Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1; F(2) = 2; F(3) = 3;
F(n) = F(n — 3) * n, при n > 3
Чему равно значение функции F(10)?
- с123 (11). Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1; F(2) = 2; F(3) = 3;
F(n) = F(n — 3) * n, при n > 3
Чему равно значение функции F(11)?
- с112 (11). Ниже на пяти языках программирования записаны две рекурсивные функции: F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n - 1) + G(n - 2)
ELSE
F = 2
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n - 1) + F(n - 2)
ELSE
G = 2
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 2 then
F := F(n - 1) + G(n - 2)
else
F := 2;
end;
function G(n: integer): integer;
begin
if n > 2 then
G := G(n - 1) + F(n - 2)
else
G := 2;
end;Си Алгоритмический язык int F(int n)
{
if (n > 2)
return F(n-1) + G(n-2);
else return 2;
}
int G(int n)
{
if (n > 2)
return G(n-1) + F(n-2);
else return 2;
}алг цел 1F(цел n)
нач
если n > 2
то
знач := F(n - 1)+G(n - 2)
иначе
знач := 2
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n - 1)+F(n - 2)
иначе
знач := 2
все
конPython def F(n):
if n > 2:
return F(n-1)+ G(n-2)
else: return 2
def G(n):
if n > 2:
return G(n-1)
- ш115 (11). Ниже на пяти языках программирования записаны две рекурсивные функции: F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 1 THEN
F = F(n - 1) + G(n - 1)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 1 THEN
G = G(n - 1) + F(n)
ELSE
G = n
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 1 then
F := F(n - 1) + G(n - 1)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 1 then
G := G(n - 1) + F(n)
else
G := n;
end;Си Алгоритмический язык int F(int n)
{
if (n > 1)
return F(n-1) + G(n-1);
else return n;
}
int G(int n)
{
if (n > 1)
return G(n-1) + F(n);
else return n;
}алг цел F(цел n)
нач
если n > 1
то
знач := F(n - 1)+G(n - 1)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 1
то
знач := G(n - 1)+F(n)
иначе
знач := n
все
конPython def F(n):
if n > 1:
return F(n-1)+ G(n-1)
else: return n
def G(n):
if n > 1:
return G(n-1)+ F(n)
else: return n
- ш125 (11). Ниже на пяти языках программирования записаны две рекурсивные функции: F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 1 THEN
F = F(n - 1) + G(n - 1)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 1 THEN
G = G(n - 1) + F(n)
ELSE
G = n
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 1 then
F := F(n - 1) + G(n - 1)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 1 then
G := G(n - 1) + F(n)
else
G := n;
end;Си Алгоритмический язык int F(int n)
{
if (n > 1)
return F(n-1) + G(n-1);
else return n;
}
int G(int n)
{
if (n > 1)
return G(n-1) + F(n);
else return n;
}алг цел F(цел n)
нач
если n > 1
то
знач := F(n - 1)+G(n - 1)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 1
то
знач := G(n - 1)+F(n)
иначе
знач := n
все
конPython def F(n):
if n > 1:
return F(n-1)+ G(n-1)
else: return n
def G(n):
if n > 1:
return G(n-1)+ F(n)
else: return n
- ш114 (11). Ниже на пяти языках программирования записаны рекурсивные функции F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n-1) + G(n-2)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n-1) + F(n-2)
ELSE
G = 3-n
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 2 then
F := F(n-1) + G(n-2)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 2 then
G := G(n-1) + F(n-2)
else
G := 3-n;
end;Си Алгоритмический язык int F(int n) {
if (n > 2)
return F(n-1) + G(n-2);
else return n;
}
int G(int n) {
if (n > 2)
return G(n-1) + F(n-2);
else return 3-n;
}алг цел F(цел n)
нач
если n > 2
то
знач := F(n-1) + G(n-2)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n-1) + F(n-2)
иначе
знач := 3-n
все
конPython def F(n):
if n > 2:
return F(n-1) + G(n-2)
else: return n
def G(n):
if n > 2:
return G(n-1) + F(n-2)
else: return 3-n
- ш124 (11). Ниже на пяти языках программирования записаны рекурсивные функции F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n-1) + G(n-2)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n-1) + F(n-2)
ELSE
G = 3-n
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 2 then
F := F(n-1) + G(n-2)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 2 then
G := G(n-1) + F(n-2)
else
G := 3-n;
end;Си Алгоритмический язык int F(int n) {
if (n > 2)
return F(n-1) + G(n-2);
else return n;
}
int G(int n) {
if (n > 2)
return G(n-1) + F(n-2);
else return 3-n;
}алг цел F(цел n)
нач
если n > 2
то
знач := F(n-1) + G(n-2)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n-1) + F(n-2)
иначе
знач := 3-n
все
конPython def F(n):
if n > 2:
return F(n-1) + G(n-2)
else: return n
def G(n):
if n > 2:
return G(n-1) + F(n-2)
else: return 3-n
- ш113 (11). Ниже на пяти языках программирования записаны рекурсивные функции F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n-1) + G(n-1) + F(n-2)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n-1)+F(n-1)+G(n-2)
ELSE
G = 3-n
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 2 then
F := F(n-1)+G(n-1)+F(n-2)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 2 then
G := G(n-1)+F(n-1)+G(n-2)
else
G := 3-n;
end;Си Алгоритмический язык int F(int n){
if (n > 2)
return F(n-1)+G(n-1)+F(n-2);
else return n;
}
int G(int n){
if (n > 2)
return G(n-1)+F(n-1)+G(n-2);
else return 3-n;
}алг цел F(цел n)
нач
если n > 2
то
знач := F(n-1)+G(n-1)+F(n-2)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n-1)+F(n-1)+G(n-2)
иначе
знач := 3-n
все
конPython def F(n):
if n > 2:
return F(n-1)+G(n-1)+F(n-2)
else: return n
def G(n):
if n > 2:
return G(n-1)+F(n-1)+G(n-2)
else: return 3-n
- ш123 (11). Ниже на пяти языках программирования записаны рекурсивные функции F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n-1) + G(n-1) + F(n-2)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n-1)+F(n-1)+G(n-2)
ELSE
G = 3-n
END IF
END FUNCTIONfunction F(n: integer): integer;
begin
if n > 2 then
F := F(n-1)+G(n-1)+F(n-2)
else
F := n;
end;
function G(n: integer): integer;
begin
if n > 2 then
G := G(n-1)+F(n-1)+G(n-2)
else
G := 3-n;
end;Си Алгоритмический язык int F(int n){
if (n > 2)
return F(n-1)+G(n-1)+F(n-2);
else return n;
}
int G(int n){
if (n > 2)
return G(n-1)+F(n-1)+G(n-2);
else return 3-n;
}алг цел F(цел n)
нач
если n > 2
то
знач := F(n-1)+G(n-1)+F(n-2)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n-1)+F(n-1)+G(n-2)
иначе
знач := 3-n
все
конPython def F(n):
if n > 2:
return F(n-1)+G(n-1)+F(n-2)
else: return n
def G(n):
if n > 2:
return G(n-1)+F(n-1)+G(n-2)
else: return 3-n
- ш112 (11). Ниже на пяти языках программирования записаны рекурсивные функции F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n-1) + G(n-1) + F(n-2)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n-1) + F(n-1) + G(n-2)
ELSE
G = n+1
END IF
END FUNCTIONfunction F(n: integer):
integer;
begin
if n > 2 then
F := F(n-1)+G(n-1)+F(n-2)
else
F := n;
end;
function G(n: integer):
integer;
begin
if n > 2 then
G := G(n-1)+F(n-1)+G(n-2)
else
G := n+1;
end;Си Алгоритмический язык int F(int n) {
if (n > 2)
return F(n-1)+G(n-1)+F(n-2);
else return n;
}
int G(int n){
if (n > 2)
return G(n-1)+F(n-1)+G(n-2);
else return n+1;
}алг цел F(цел n)
нач
если n > 2
то
знач := F(n-1)+G(n-1)+F(n-2)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n-1)+F(n-1)+G(n-2)
иначе
знач := n+1
все
конPython def F(n):
if n > 2:
return F(n-1)+G(n-1)+F(n-2)
else: return n
def G(n):
if n > 2:
return G(n-1)+F(n-1)+G(n-2)
else: return n+1- ш122 (11). Ниже на пяти языках программирования записаны рекурсивные функции F и G.
Бейсик Паскаль FUNCTION F(n)
IF n > 2 THEN
F = F(n-1) + G(n-1) + F(n-2)
ELSE
F = n
END IF
END FUNCTION
FUNCTION G(n)
IF n > 2 THEN
G = G(n-1) + F(n-1) + G(n-2)
ELSE
G = n+1
END IF
END FUNCTIONfunction F(n: integer):
integer;
begin
if n > 2 then
F := F(n-1)+G(n-1)+F(n-2)
else
F := n;
end;
function G(n: integer):
integer;
begin
if n > 2 then
G := G(n-1)+F(n-1)+G(n-2)
else
G := n+1;
end;Си Алгоритмический язык int F(int n) {
if (n > 2)
return F(n-1)+G(n-1)+F(n-2);
else return n;
}
int G(int n){
if (n > 2)
return G(n-1)+F(n-1)+G(n-2);
else return n+1;
}алг цел F(цел n)
нач
если n > 2
то
знач := F(n-1)+G(n-1)+F(n-2)
иначе
знач := n
все
кон
алг цел G(цел n)
нач
если n > 2
то
знач := G(n-1)+F(n-1)+G(n-2)
иначе
знач := n+1
все
конPython def F(n):
if n > 2:
return F(n-1)+G(n-1)+F(n-2)
else: return n
def G(n):
if n > 2:
return G(n-1)+F(n-1)+G(n-2)
else: return n+1
- ш111 (11).
- ш121 (11).
- Демо 2010. Задание не вводилось.