Задание №16
ЕГЭ-2023. Задание № 16
Тема: Вычисление рекуррентных выражений. Время выполнения 5 минут.
Решение задания № 16 ЕГЭ-2023. Демо.
я.п. Python здесь используется в качестве калькулятора:
# f(2023)=f(2020)*2021*2022*2023, где f(2020)=2020!
# f(2020)*2021*2022*2023/f(2020)=2021*2022*2023
print(2021*2022*2023)
ЕГЭ-2024
задача 16 вариант 1 (Ушаков Д. 2024)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 1
F(2) = 2
F(n) = F(n – 1) + F(n – 2), при n > 2
Чему равно значение функции F(17)?
Решение в среде Excel:
Открываем новый файл в Excel и создаем в нем таблицу из двух столбцов (смотри ниже скриншот):
Столбец А - натуральные числа от 1 до 17.
Столбец В заполняем по условию задачи:
В ячейку В2 заносим число 1
В ячейку В3 заносим число 2
В ячейке В4 создаем универсальную функцию: F(n-1) - > это значение ячейки В3; F(n-2) -> Это значение ячейки В2. Итак: В4 = В3 + В2
Остальные ячейки столбца заполняем, применяя прием автозаполнение (по шаблону ячейки В4).
Ответ на вопрос получаем в ячейке В18:
Решение я.п. Python:
def F(n):
if n==1: return 1
elif n==2: return 2
else:
return F(n-1) + F(n-2)
print(F(17))
Решение я.п. PascalABC.net:
function F(n: integer):bigInteger;
begin
if (n=1) or (n=2) then
Result:=n
else
Result:=F(n-1) + F(n-2);
end;
begin
print(F(17));
end.
После запуска программы получим ответ: 2584.
Задача 16 вариант 2 (Ушаков Д. 2024)
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(1) = 2
F(n) = F(n – 1) + F(n / 3), при n > 1 и n кратно 3
F(n) = F(n – 1) + 1, при n > 1 и n не кратно 3
Чему равно значение функции F(50)?
Решение в Excel:
В ячейку В2 заносим число 2. В ячейке В3 создаем универсальную функцию (по условию задачи):
При создании универсальной функции используем функции Excel: ЕСЛИ(), ОСТАТ(), ЦЕЛОЕ() и ВПР().
Вставим функцию ЕСЛИ(), используя мастер создания функции. И в окне функции, как показано ниже, записываем действия при выполнении логического выражение (в логическом выражении проверяется остаток от деления числа n на 3).
Действия записываются для ячейки А3=n. Если остаток от деления числа n на 3 равен нулю (то есть, число делится на 3 без остатка), записываем выражение для случая ИСТИНА (Значение_если_ИСТИНА): В2 + ВПР(ЦЕЛОЕ(А3/3);А:В; 2).
В противном случае (Значение_если_ЛОЖЬ): В2 + 1
Результат выполнения функций ОСТАТ() и ЦЕЛОЕ(), в принципе, понятен. Но вот поясню, как работает функция ВПР(), тем более, с ней нам придется не раз столкнуться при работе в Excel.
Аргументами функции ВПР() являются три аргумента (слева направо):
Что_искать в левом крайнем столбце таблицы. В нашем случае - это целое от деления А3 на 3 (в ячейке А3 находится текущее значение n).
Где_искать (диапазон таблицы). В нашем случае, это А:В
Откуда_брать_значение в качестве промежуточного результата. Здесь мы указываем номер столбца, в нашем случае - это столбец 2.Считается слева направо.
Например, для ячейки А4=3, число 3 делится на 3 без остатка! Следовательно, будет выполняться действие, включающее ВПР. Предыдущее значение функции (В2 = 3). Посмотрим, что возвращает функция ВПР() в этом случае. Итак, ВПР(3/3; А:В;2) - в крайнем левом столбце функция находит значение, равное ЦЕЛОЙ части от деления 3/3, это 1. 1 находится в ячейке А2, а в столбце В в строке 2 функция берет значение для F(1) = 2. Таким образом, итог выполнения действия: 3 + 2 = 5. И в ячейке В4 будет значение 5. Результат выполнения виден на скриншоте страницы в Excel.
Действие универсальной формулы распространим на весь столбец вниз и результат возьмем в ячейке В51 (для n=50) - 292.
Решение я.п. Python:
def F(n):
if n==1: return 2
elif n%3==0:
return F(n-1) + F(n//3)
else:
return F(n-1) + 1
print(F(50))
Решение я.п.PascalABC.net:
function F(n: integer): bigInteger;
begin
if n=1 then
Result:=2
else
if n mod 3=0 then
Result:=F(n-1) + F(n div 3)
else
Result:=F(n-1) + 1;
end;
begin
print(F(50));
end.
Результат: 292
Задачи для самостоятельного решения:
Задача 1. (вариант 6, сб. Ушаков Д.)
Алгоритм вычисления значения функции F(n), где n —целое неотрицательное число, задан следующими соотношениями:
F(0) = 0
F(1) = 1
F(2) = 3
F(n) = F(n – 2) + F(n / 2), при n > 2 и n — чётно
F(n) = n + F(n – 1) + F(n – 3), при n > 2 и n — нечётно
Укажите наименьшее значение n, при котором значение F(n) будет больше 1000?
Ответ
31
Если возникли трудности с реализацией:
я.п. PascalABC.net
uses school;
function F(n:integer):longint;
begin
if (n=0) or (n=1) then Result:=n
else
if n=2 then Result:=3
else
if (n>2) and n.isEven then
F:=F(n-2) + F(n div 2)
else
F:=n + F(n-1) + F(n-3)
end;
begin
for var x:=1 to 200 do
if F(x)>1000 then begin
x.Print;
break
end;
end.
я.п. Python
def F(n):
if (n==0) or (n==1): return n
elif n==2: return 3
elif n%2==0:
return F(n-2) + F(n//2)
else:
return n + F(n-1) + F(n-3)
for n in range(200):
if F(n)>1000:
print(n)
break
Задача 2 (вариант 1, сб. Евич Л.Н. - 14 вариантов, 2023г)
Алгоритм вычисления значения функции F(n), где n- целое неотрицательное число, задан следующими соотношениями:
F(n) = 1, если n <= 1;
F(2) = 2;
F(n) = 2n - F(n div 3) - F(n- 1), если n > 2 и n кратно трём;
F(n) = n + F(n- 2) + F(n div 10), если n > 2 и при этом n не кратно трём.
Найдите количество чисел n из промежутка [50; 100], для которых 50< F(n) <= 200 .
Пояснение. Здесь n div а означает целую часть от деления n на а.
Ответ
28
Задача 3 (вариант 9, сб. Евич Л.Н., 14 вариантов, 2023)
Алгоритм вычисления значения функции F(n), где n - натуральное число, задан следующими соотношениями:
F(n) = 2, если n < 20;
F(n) = 1 + 2F(n - 17), если 20 <= n < 150;
F(n) = -3 + F(n - 23), если 150 <= n < 1000;
F(n) = 2 + F(n - 42), если n >= 1000.
Чему равно значение функции F(1150)?
Ответ:
280
Задача 4. (вариант 1, сб. Крылов С., Чуркина Е., 2024г)
Алгоритм вычисления значения функции F(n) - где n - натуральное число, задан следующими соотношениями:
F(n) = 5, при n = 1;
F(n) = 2n + 1 + F(n - 1), если n > 1.
Чему равно значение выражения F(2024) - F(2022)?
Ответ
8096
Задача 5. (вариант 7, сб. Крылов С., Чуркина Е., 2024)
Алгоритм вычисления значения функции F(n), где n – целое неотрицательное число, задан следующими соотношениями:
Чему равно значение функции F(24)?
Ответ
887040
Решения заданий № 16 ЕГЭ прошлых лет
