Задание 16. Вычисление рекуррентных выражений. ЕГЭ 2024 по информатике

Задание 16. Вычисление рекуррентных выражений. ЕГЭ 2024 по информатике

За это задание ты можешь получить 1 балл. На решение дается около 2 минут. Уровень сложности: повышенный.
Средний процент выполнения: 54.9%
Ответом к заданию 16 по информатике может быть цифра (число) или слово.

Задачи для практики

Задача 1

Функция F(n), где n — натуральное число, вычисляется по следующему правилу:

F(n) = n, при n < 4;

F(n) = F(n-3)*3, при n > 3 кратном трём;

F(n) = F(n-1)+7, при n > 3, которое даёт остаток 1 при делении на 3;

F(n) = F(n-2)+n, при n > 3, которое даёт остаток 2 при делении на 3.

Чему равно значение функции F(28)?

Для выполнения задания рекомендуется написать программу.

Решение

Перепишем правило вычисления функции в рекуррентную функцию на языке Python:

def f(n):

if n < 4:

return n

elif n % 3 == 0:

return f(n-3)*3

elif n % 3 == 1:

return f(n-1)+7

else:

return f(n-2)+n

print(f(28))

При запуске программа выдаст ответ: 19690

Ответ: 19690

Задача 2

Функция F(n), где n — натуральное число, вычисляется по следующему правилу:

F(n) = n, при n < 4;

F(n) = F(n-3)*3, при n > 3 кратном трём;

F(n) = F(n-1)+7, при n > 3, которое даёт остаток 1 при делении на 3;

F(n) = F(n-2)+n, при n > 3, которое даёт остаток 2 при делении на 3.

Чему равно значение функции F(25)?

Для выполнения задания рекомендуется написать программу.

Решение

Перепишем правило вычисления функции в рекуррентную функцию на языке Python:

def f(n):

if n < 4:

return n

elif n % 3 == 0:

return f(n-3)*3

elif n % 3 == 1:

return f(n-1)+7

else:

return f(n-2)+n

print(f(25))

Решение на С++:

#include <iostream>
using namespace std;

int f(int n){
if (n < 4)
return n;
else if (n % 3 == 0)
return f(n-3)*3;
else if (n % 3 == 1)
return f(n-1)+7;
else
return f(n-2)+n;
}

int main() {
cout << f(25);
return 0;
}

При запуске программа выдаст ответ: 6568

Ответ: 6568

Задача 3

Функция F(n), где n — натуральное число, вычисляется по следующему правилу:

F(n) = n, при n < 2;

F(n) = F(n-2)+n, при n > 1 чётном

F(n) = F(n-1)+2*F(n-3), при n > 1 нечётном

Чему равно значение функции F(199)?

Для выполнения задания рекомендуется написать программу.

Решение

Перепишем правило вычисления функции в рекуррентную функцию на языке Python:

def f(n):

if n < 2:

return n

elif n % 2 == 0:

return f(n-2)+n

else:

return f(n-1)+2*f(n-3)

print(f(199))

При запуске программа выдаст ответ: 29304

Ответ: 29304

Задача 4

Функция F(n), где n — натуральное число, вычисляется по следующему правилу:

F(n) = n, при n < 2;

F(n) = F(n-1)+F(n-3), при n > 1 чётном

F(n) = F(n-2)*n, при n > 1 нечётном

Чему равно значение функции F(10)?

Для выполнения задания рекомендуется написать программу.

Решение

Перепишем правило вычисления функции в рекуррентную функцию на языке Python:

def f(n):

if n < 2:

return n

elif n % 2 == 0:

return f(n-1)+f(n-3)

else:

return f(n-2)*n

print(f(10))

При запуске программа выдаст ответ: 1050

Ответ: 1050

Задача 5

Функция F(n), где n — натуральное число, вычисляется по следующему правилу:

F(n) = n, при n ≤ 2;

F(n) = F(n-1)*(n-2), при n > 2

Чему равно значение функции F(8)?

Для выполнения задания рекомендуется написать программу.

Решение

Перепишем правило вычисления функции в рекуррентную функцию на языке Python:

def f(n):

if n <= 2:

return n

else:

return f(n-1)*(n-2)

print(f(8))

При запуске программа выдаст ответ: 1440

Ответ: 1440

Задача 6

Функция F(n), где n — натуральное число, вычисляется по следующему правилу:

F(n) = 1, при n ≤ 2;

F(n) = F(n-1)+F(n-2), при n > 2

Чему равно значение функции F(19)?

Для выполнения задания рекомендуется написать программу.

Решение

Перепишем правило вычисления функции в рекуррентную функцию на языке Python:

def f(n):

if n <= 2:

return 1

else:

return f(n-1)+f(n-2)

print(f(19))

При запуске программа выдаст ответ: 4181

Ответ: 4181

Задача 7

На рисунке на различных языках программирования записан рекурсивный алгоритм F.

Определите сумму чисел, напечатанных на экране при выполнении вызова F(4)?

Решение

Поскольку нам необходимо посчитать сумму чисел, порядок вызова функций не имеет значения. Заметим, что первый вывод печатает на экране все параметры n, с которыми вызываются функции, а второй печатает параметр n, только если он больше 3. Изначальная F(4) вызовет 4 функции: F(3), F(2), F(1), F(0).

Итого, будут вызваны функции: F(4), F(3), F(2), F(1), F(0), причём для F(4) вывод на экран произойдёт дважды. Итоговая сумма чисел: 4+4+3+2+1+0=14

Ответ: 14.

Ответ: 14

Задача 8

На картинке на различных языках программирования записан рекурсивный алгоритм F. Сколько чисел будет выведено в консоль при выполнении вызова функции F(8)?

Решение

Решение при помощи программы на языке С++:

#include <iostream>
using namespace std;

int f(int n){
if (n > 2) {
cout << n;
f(n - 2);
f(n - 3);
}
}

int main() {
cout << f(8);
return 0;
}

Программ выведет на экран число из 6 цифр: 864353

Ответ: 6

Задача 9

Функция F(n), где n — натуральное число, вычисляется по следующему правилу:

F(n) = n, при n < 4;

F(n) = F(n-3)*3, при n > 3 кратном трём;

F(n) = F(n-1)+7, при n > 3, которое даёт остаток 1 при делении на 3;

F(n) = F(n-2)+n, при n > 3, которое даёт остаток 2 при делении на 3.

Чему равно значение функции F(22)?

Для выполнения задания рекомендуется написать программу.

Решение

Перепишем правило вычисления функции в рекуррентную функцию на языке Python:

def f(n):

if n < 4:

return n

elif n % 3 == 0:

return f(n-3)*3

elif n % 3 == 1:

return f(n-1)+7

else:

return f(n-2)+n

print(f(22))

При запуске программа выдаст ответ: 2194

Ответ: 2194

Задача 10

На рисунке на различных языках программирования записан рекурсивный алгоритм F. Определите, сколько чисел будет напечатано на экране при выполнении вызова F(26).

Решение

На рисунке представлена схема выполнения вызова процедуры F(26) в виде дерева.

Согласно алгоритма, вывод чисел на экран осуществляется, когда остаток от деления n на 3 не равен 1.

Количество чисел напечатанных на экране (26, 21, 15, 9, 3) : 5

Ответ: 5

Задача 11

На рисунке на различных языках программирования записан рекурсивный алгоритм F.

Определите, сколько чисел будет напечатано на экране при выполнении вызова F(6).

Решение

При вызове функции F(6) выполняется подпрограмма, в которой переменная n принимает значение 6. Каждый раз при вызове процедур F(n — 2) и F(n — 3) в качестве фактического параметра n в них передаётся текущее значение этой переменной. На рисунке участки, ограниченные пунктиром, демонстрируют область видимости соответствующего значения переменной n.

Каждый раз, возвращаясь из процедуры, переменная n принимает значение, которое было до вызова данной процедуры. Например, если процедура F(n — 2) была вызвана при n = 6, то, попадая в процедуру, переменная n примет значение 4(= 6 − 2). После выхода из этой процедуры значение переменной n вновь будет равно 6.

На рисунке представлена схема выполнения вызова процедуры F(6) в виде дерева.

В данном случае осуществляется вертикальный обход дерева в прямом (префиксном) порядке. То есть сначала просматривается вершина, затем правое поддерево, затем левое поддерево.

Согласно алгоритму, сразу после входа в процедуру осуществляется вывод на экран переменной n. Следовательно, при выполнении вызова F(6) на экране будет отображена последовательность чисел: 6 4 2 0 -1 1 3 1 0. На экране будет напечатано 9 чисел.

Ответ: 9