Задание 16 ЕГЭ по информатике

1. 1.

   from functools import lru_cache
   @lru_cache(None)          # кэш: каждый F(n) считается один раз
   def F(n):
       if n < 3:
           return n
       return F(n-1) + F(n-2)
   print(F(24))

Ответ: Программа печатает 75025: кэш считает каждое F(n) ровно один раз

1. 1. Условие содержит два разных шага, и выбор между ними зависит от чётности n. В коде это обычная развилка.
2. 2.

   from functools import lru_cache

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

   print(F(12))

3. 3. Порядок проверок важен: сначала база (n ≤ 2), потом нечётный случай, потом всё остальное. Если поставить проверку чётности раньше базы, программа уйдёт в бесконечную рекурсию при n = 1.
4. 4. Проверим начало вручную: F(1) = F(2) = 1; F(3) нечётное, значит, F(2) + F(1) = 2; F(4) чётное, значит, 3 · F(3) = 6; F(5) = F(4) + F(3) = 8; F(6) = 3 · 8 = 24.
5. 5. Кэш здесь обязателен: в нечётной ветке два обращения к функции, и без запоминания дерево вызовов растёт лавинообразно.
6. 6. Проверка себя: посчитайте первые шесть значений вручную и сравните с тем, что печатает программа при маленьких n. Если расходится — ошибка в переносе условия, а не в вычислениях.

Ответ: Значения растут быстро; программа печатает точный результат, а ручная проверка первых шести значений подтверждает, что условие перенесено верно

1. 1. Шаг 1. Считать надо снизу вверх, от базы к искомому значению: каждое следующее значение выражается через предыдущее, и таблица заполняется по одной строке.
2. 2. F(1) = 1 — это база, она дана в условии.
3. 3. F(2): двойка чётная, значит правило F(n − 1) + 2n: 1 + 2·2 = 1 + 4 = 5.
4. 4. F(3): тройка нечётная, правило F(n − 1) + 3: 5 + 3 = 8.
5. 5. F(4): чётное, 8 + 2·4 = 8 + 8 = 16.
6. 6. F(5): нечётное, 16 + 3 = 19.
7. 7. F(6): чётное, 19 + 2·6 = 19 + 12 = 31.
8. 8. F(7): нечётное, 31 + 3 = 34. Ответ: 34.
9. 9.

   Шаг 2. Та же функция программой:

   from functools import lru_cache

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

   print(F(7))

10. 10. Шаг 3. Код пишется по условию дословно, строка за строкой: сначала база, потом каждое правило со своим условием. Это и есть главный приём линии 16 — не придумывать формулу, а перенести условие в функцию.
11. 11. Шаг 4. Порядок проверок важен. База n == 1 стоит первой: если поставить её после проверки чётности, единица уйдёт в ветку «нечётное» и вызовет F(0), которого в условии нет, — рекурсия уйдёт в минус бесконечность.
12. 12. Шаг 5. Обратите внимание, что 2 * n использует текущее n, а не n − 1. Здесь легко ошибиться, переписывая формулу: в правиле стоит именно 2n, и для F(4) это 8, а не 6.
13. 13. Шаг 6. Проверка таблицей — обязательный шаг. Напечатайте все значения от базы до искомого: for n in range(1, 8): print(n, F(n)). Ряд 1, 5, 8, 16, 19, 31, 34 совпал с ручным расчётом ✔ Если бы программа выдала другое, разошлись бы они на конкретном n, и ошибку было бы видно сразу.

Ответ: 34

1. 1.

   vyzovov = 0

   def F(n): global vyzovov

       vyzovov += 1
       if n <= 2:
           return 1
       return F(n - 1) + F(n - 2)

   print(F(10), vyzovov)

2. 2. Шаг 1. Программа печатает 55 109: значение F(10) равно 55, а функция вызвалась 109 раз.
3. 3. Шаг 2. Откуда столько. Каждый вызов при n > 2 порождает два новых, и дерево вызовов растёт как само число Фибоначчи. Точная формула: вызовов ровно 2·F(n) − 1, и для n = 10 это 2 · 55 − 1 = 109 ✔
4. 4. Шаг 3. Почему это катастрофа при больших n. F(30) = 832 040, значит вызовов будет около 1,7 миллиона. F(40) — уже около двухсот миллионов, и программа думает минутами. А в линии 16 значения вроде F(50) встречаются регулярно.
5. 5. Шаг 4. Причина расточительности — повторный счёт одного и того же. F(8) вычисляется и внутри F(10), и внутри F(9); F(7) — четырежды; F(3) — десятки раз. Разных значений всего десять, а вычислений сто девять.
6. 6.

   Шаг 5. Лечение — одна строка:

   from functools import lru_cache

   vyzovov = 0

   @lru_cache(None)
   def F(n):

   global vyzovov

       vyzovov += 1
       if n <= 2:
           return 1
       return F(n - 1) + F(n - 2)

   print(F(10), vyzovov)

7. 7. Шаг 6. Теперь печатается 55 10: тот же ответ, но вызовов ровно десять — по одному на каждое значение от 1 до 10. Декоратор запоминает результат и при повторном обращении возвращает готовое число, не заходя в тело функции.
8. 8. Шаг 7. Сложность изменилась с экспоненциальной на линейную: было порядка 2ⁿ, стало n. Именно поэтому @lru_cache(None) пишут в линии 16 всегда, не задумываясь, — цена строки нулевая, а без неё половина заданий не решается.
9. 9. Шаг 8. Аргумент None означает «кэш без ограничения размера». Можно написать @lru_cache(maxsize=None) — это то же самое. И одно ограничение: кэшируются только функции, у которых аргументы неизменяемые (числа, строки, кортежи). Список в аргументе вызовет ошибку — его заменяют кортежем.

Ответ: 55; 109 вызовов без кэша и 10 с кэшем

1. 1.

   from functools import lru_cache

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

   for n in range(1, 26):
       print(n, F(n))

2. 2. Шаг 1. Печатаем таблицу, а не одно значение. Это обязательный приём линии 16: по таблице видно, как растёт функция, и первые строки можно сверить с ручным счётом.
3. 3. Шаг 2. Первые значения: F(1) = 1, F(2) = 5, F(3) = 8, F(4) = 16, F(5) = 19, F(6) = 31, F(7) = 34. Совпадает с ручным расчётом из предыдущего разбора ✔ Значит, правила перенесены в код верно, и дальше можно доверять программе.
4. 4. Шаг 3. Заметна закономерность: на чётных шагах функция прибавляет 2n, на нечётных всегда 3. Значит, за пару шагов (нечётный плюс чётный) прибавляется примерно 2n + 3, и рост получается квадратичным. Для F(25) ждём величину порядка нескольких сотен — это ориентир правдоподобности.
5. 5.

   Шаг 4. Программа печатает F(25). Чтобы ответить на второй вопрос, добавляем короткий цикл:

   n = 1
   while F(n) <= 200:
       n += 1
   print(n, F(n))

6. 6. Шаг 5. Здесь кэш работает особенно наглядно: цикл вызывает F для каждого n подряд, и каждое значение считается один раз, а дальше берётся готовым. Без кэша тот же цикл пересчитывал бы всю цепочку заново на каждом шаге.
7. 7. Шаг 6. Про формулировку «при каком наименьшем n». Цикл идёт вверх и останавливается на первом n, для которого условие нарушено, — это и есть наименьшее. Если бы спрашивали наибольшее n, при котором F(n) не превышает 200, ответом было бы предыдущее значение, то есть n - 1.
8. 8. Шаг 7. Проверка на границе. Напечатайте F(n − 1) и F(n) рядом: первое должно быть не больше 200, второе — больше. Если оба больше или оба меньше, цикл остановился не там, и почти всегда причина в знаке — <= вместо <.
9. 9. Шаг 8. И общее правило линии 16: не сворачивайте соотношения в формулу. Соотношения нарочно составлены так, что замкнутого выражения у них нет или оно громоздко. Переносите условие дословно, ставьте кэш и печатайте таблицу — три шага, которые закрывают линию целиком.
10. 10. Шаг 9. Что печатает программа. Значение F(25) = 349. А порог в 200 впервые превышается при n = 18, где F(18) = 205; на предыдущем шаге F(17) = 169, то есть ещё не превышает ✔ Обе величины стоит выписать рядом — так видно, что граница найдена верно.

Ответ: F(25) = 349; порог 200 впервые превышен при n = 18 (F(18) = 205)