ЕГЭ информатика: задание 16

Вариант 1

F и G, большое n

Алгоритм вычисления функций F(n) и G(n), где n — целое число, задан следующими соотношениями:
F(n) = 2 × (G(n − 1) + 12);
G(n) = 3 × n, если n < 10;
G(n) = G(n − 4) + 7, если n ≥ 10.
Чему равно значение выражения F(29878)?

Разбор

Шаг 1. F(29878) = 2·(G(29877) + 12).

Шаг 2. Каждый шаг G уменьшает аргумент на 4 и добавляет 7. От 29877 до значения меньше 10 нужно t = ⌊(29877 − 10) / 4⌋ + 1 = 7467 шагов; аргумент станет 9.

Шаг 3. G(29877) = G(9) + 7·7467 = 27 + 52269 = 52296. F(29878) = 2·(52296 + 12) = 104616.

Программой. Прямой вызов упадёт с ошибкой «maximum recursion depth exceeded»: глубина рекурсии тысячи вызовов. Помогает запоминание @lru_cache и постепенное заполнение: вызываем G для 0, 1, 2, … по порядку — тогда каждый новый вызов сразу находит уже посчитанное значение.

Ответ: 104616

Решение на Python.

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def G(n):
    if n < 10:
        return 3 * n
    return G(n - 4) + 7

def F(n):
    return 2 * (G(n - 1) + 12)

for i in range(29878):   # заполняем кэш по возрастанию: каждый вызов опирается на готовые значения
    G(i)
print(F(29878))

Вариант 2

отношение значений

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 3 при n = 1;
F(n) = (n − 1) × F(n − 1), если n > 1.
Чему равно значение выражения (F(2024) − 2·F(2023)) / F(2022)?

Разбор

Идея. Считать сами значения не нужно — они огромные. Распишем F(N) через F(N − 1), F(N − 2) и сократим.

F(2024) = (2024−1)·F(2023) и F(2023) = (2023−1)·F(2022). Делим числитель на F(2022): 2023·2022 − 2·2022 = 4086462.

Программой тоже можно: Python хранит такие числа точно, но рекурсию нужно заполнять постепенно, а делить — целочисленно (//), иначе получится переполнение при переводе в дробное число.

Ответ: 4086462

Решение на Python.

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def F(n):
    if n == 1:
        return 3
    return (n - 1) * F(n - 1)

for i in range(1, 2024):   # заполняем кэш по возрастанию
    F(i)
print((F(2024) - 2 * F(2023)) // F(2022))

Вариант 3

подсчёт значений

Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = F(n − 1) + n, если n чётно и n > 1;
F(n) = F(n // 2) + 2n, если n нечётно и n > 1.
Определите количество натуральных значений n на отрезке [1; 500], для которых F(n) < 799.

Разбор

Шаг 1. Записываем функцию на Python строго по условию, с запоминанием @lru_cache — иначе одни и те же значения будут пересчитываться много раз.

Шаг 2. Перебираем n от 1 до 500, проверяем условие и считаем подходящие n. Первые значения для проверки: F(1) = 1, F(2) = 3, F(3) = 7, F(4) = 11, F(5) = 13, F(6) = 19, F(7) = 21.

Ответ: 166

Решение на Python.

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return F(n - 1) + n
    return F(n // 2) + 2 * n

count = 0
for n in range(1, 501):
    if F(n) < 799:
        count += 1
print(count)

Вариант 4

F и G, большое n

Алгоритм вычисления функций F(n) и G(n), где n — целое число, задан следующими соотношениями:
F(n) = 3 × (G(n − 1) + 13);
G(n) = n, если n < 10;
G(n) = G(n − 4) + 3, если n ≥ 10.
Чему равно значение выражения F(32984)?

Разбор

Шаг 1. F(32984) = 3·(G(32983) + 13).

Шаг 2. Каждый шаг G уменьшает аргумент на 4 и добавляет 3. От 32983 до значения меньше 10 нужно t = ⌊(32983 − 10) / 4⌋ + 1 = 8244 шагов; аргумент станет 7.

Шаг 3. G(32983) = G(7) + 3·8244 = 7 + 24732 = 24739. F(32984) = 3·(24739 + 13) = 74256.

Программой. Прямой вызов упадёт с ошибкой «maximum recursion depth exceeded»: глубина рекурсии тысячи вызовов. Помогает запоминание @lru_cache и постепенное заполнение: вызываем G для 0, 1, 2, … по порядку — тогда каждый новый вызов сразу находит уже посчитанное значение.

Ответ: 74256

Решение на Python.

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def G(n):
    if n < 10:
        return 1 * n
    return G(n - 4) + 3

def F(n):
    return 3 * (G(n - 1) + 13)

for i in range(32984):   # заполняем кэш по возрастанию: каждый вызов опирается на готовые значения
    G(i)
print(F(32984))

Вариант 5

отношение значений

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 2 при n = 1;
F(n) = (n + 3) × F(n − 1), если n > 1.
Чему равно значение выражения (F(2022) − 8·F(2021)) / F(2020)?

Разбор

Идея. Считать сами значения не нужно — они огромные. Распишем F(N) через F(N − 1), F(N − 2) и сократим.

F(2022) = (2022+3)·F(2021) и F(2021) = (2021+3)·F(2020). Делим числитель на F(2020): 2025·2024 − 8·2024 = 4082408.

Программой тоже можно: Python хранит такие числа точно, но рекурсию нужно заполнять постепенно, а делить — целочисленно (//), иначе получится переполнение при переводе в дробное число.

Ответ: 4082408

Решение на Python.

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def F(n):
    if n == 1:
        return 2
    return (n + 3) * F(n - 1)

for i in range(1, 2022):   # заполняем кэш по возрастанию
    F(i)
print((F(2022) - 8 * F(2021)) // F(2020))

Вариант 6

подсчёт значений

Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
F(n) = n при n < 3;
F(n) = F(n − 1) + F(n − 2), если n ≥ 3 и n кратно 3;
F(n) = F(n − 1) − F(n − 2) + n, если n ≥ 3 и n не кратно 3.
Определите количество натуральных значений n на отрезке [1; 800], для которых F(n) при делении на 9 даёт остаток 6.

Разбор

Шаг 1. Записываем функцию на Python строго по условию, с запоминанием @lru_cache — иначе одни и те же значения будут пересчитываться много раз.

Шаг 2. Перебираем n от 1 до 800, проверяем условие и считаем подходящие n. Первые значения для проверки: F(1) = 1, F(2) = 2, F(3) = 3, F(4) = 5, F(5) = 7, F(6) = 12, F(7) = 12.

Ответ: 60

Решение на Python.

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n < 3:
        return n
    if n % 3 == 0:
        return F(n - 1) + F(n - 2)
    return F(n - 1) - F(n - 2) + n

count = 0
for n in range(1, 801):
    if F(n) % 9 == 6:
        count += 1
print(count)

Вариант 7

F и G, большое n

Алгоритм вычисления функций F(n) и G(n), где n — целое число, задан следующими соотношениями:
F(n) = 4 × (G(n − 3) + 18);
G(n) = n, если n < 5;
G(n) = G(n − 2) + 5, если n ≥ 5.
Чему равно значение выражения F(52022)?

Разбор

Шаг 1. F(52022) = 4·(G(52019) + 18).

Шаг 2. Каждый шаг G уменьшает аргумент на 2 и добавляет 5. От 52019 до значения меньше 5 нужно t = ⌊(52019 − 5) / 2⌋ + 1 = 26008 шагов; аргумент станет 3.

Шаг 3. G(52019) = G(3) + 5·26008 = 3 + 130040 = 130043. F(52022) = 4·(130043 + 18) = 520244.

Программой. Прямой вызов упадёт с ошибкой «maximum recursion depth exceeded»: глубина рекурсии тысячи вызовов. Помогает запоминание @lru_cache и постепенное заполнение: вызываем G для 0, 1, 2, … по порядку — тогда каждый новый вызов сразу находит уже посчитанное значение.

Ответ: 520244

Решение на Python.

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def G(n):
    if n < 5:
        return 1 * n
    return G(n - 2) + 5

def F(n):
    return 4 * (G(n - 3) + 18)

for i in range(52022):   # заполняем кэш по возрастанию: каждый вызов опирается на готовые значения
    G(i)
print(F(52022))

Вариант 8

подсчёт значений

Алгоритм вычисления значения функции F(n), где n — целое неотрицательное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = F(n − 1) + n, если n чётно и n > 1;
F(n) = F(n // 2) + 2n, если n нечётно и n > 1.
Определите количество натуральных значений n на отрезке [1; 1000], для которых F(n) при делении на 7 даёт остаток 2.

Разбор

Шаг 1. Записываем функцию на Python строго по условию, с запоминанием @lru_cache — иначе одни и те же значения будут пересчитываться много раз.

Шаг 2. Перебираем n от 1 до 1000, проверяем условие и считаем подходящие n. Первые значения для проверки: F(1) = 1, F(2) = 3, F(3) = 7, F(4) = 11, F(5) = 13, F(6) = 19, F(7) = 21.

Ответ: 132

Решение на Python.

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return F(n - 1) + n
    return F(n // 2) + 2 * n

count = 0
for n in range(1, 1001):
    if F(n) % 7 == 2:
        count += 1
print(count)

Вариант 9

отношение значений

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n × F(n − 1), если n > 1.
Чему равно значение выражения (F(2020) + 9·F(2019)) / F(2018)?

Разбор

Идея. Считать сами значения не нужно — они огромные. Распишем F(N) через F(N − 1), F(N − 2) и сократим.

Выносим F(2018): 2020·2019 + 9·2019 = 4096551.

Программой тоже можно: Python хранит такие числа точно, но рекурсию нужно заполнять постепенно, а делить — целочисленно (//), иначе получится переполнение при переводе в дробное число.

Ответ: 4096551

Решение на Python.

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    return (n) * F(n - 1)

for i in range(1, 2020):   # заполняем кэш по возрастанию
    F(i)
print((F(2020) + 9 * F(2019)) // F(2018))

Вариант 10

F и G, большое n

Алгоритм вычисления функций F(n) и G(n), где n — целое число, задан следующими соотношениями:
F(n) = 2 × (G(n − 5) + 3);
G(n) = 3 × n, если n < 10;
G(n) = G(n − 2) + 7, если n ≥ 10.
Чему равно значение выражения F(49057)?

Разбор

Шаг 1. F(49057) = 2·(G(49052) + 3).

Шаг 2. Каждый шаг G уменьшает аргумент на 2 и добавляет 7. От 49052 до значения меньше 10 нужно t = ⌊(49052 − 10) / 2⌋ + 1 = 24522 шагов; аргумент станет 8.

Шаг 3. G(49052) = G(8) + 7·24522 = 24 + 171654 = 171678. F(49057) = 2·(171678 + 3) = 343362.

Программой. Прямой вызов упадёт с ошибкой «maximum recursion depth exceeded»: глубина рекурсии тысячи вызовов. Помогает запоминание @lru_cache и постепенное заполнение: вызываем G для 0, 1, 2, … по порядку — тогда каждый новый вызов сразу находит уже посчитанное значение.

Ответ: 343362

Решение на Python.

from functools import lru_cache
import sys
sys.setrecursionlimit(10000)

@lru_cache(None)
def G(n):
    if n < 10:
        return 3 * n
    return G(n - 2) + 7

def F(n):
    return 2 * (G(n - 5) + 3)

for i in range(49057):   # заполняем кэш по возрастанию: каждый вызов опирается на готовые значения
    G(i)
print(F(49057))

Рекурсивные функции

Как считать

Глубина рекурсии

Типичные ошибки

Разобранные варианты

Вариант 1

Вариант 2

Вариант 3

Вариант 4

Вариант 5

Вариант 6

Вариант 7

Вариант 8

Вариант 9

Вариант 10

Для самостоятельного решения

Вариант 11

Вариант 12

Вариант 13

Вариант 14

Вариант 15