Задание 16. Вычисление рекуррентных выражений. ЕГЭ 2024 по информатике
Средний процент выполнения: 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
Задача 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
Задача 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
Задача 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
Задача 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
Задача 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
Задача 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.
Задача 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
Задача 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
Задача 10
На рисунке на различных языках программирования записан рекурсивный алгоритм F. Определите, сколько чисел будет напечатано на экране при выполнении вызова F(26).
Решение
На рисунке представлена схема выполнения вызова процедуры F(26) в виде дерева.
Согласно алгоритма, вывод чисел на экран осуществляется, когда остаток от деления n на 3 не равен 1.
Количество чисел напечатанных на экране (26, 21, 15, 9, 3) : 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 чисел.