Подтема 4 из 6
Раскрыть и сократить
Задача темы вручную: большие значения раскрывают до общего множителя или слагаемого, и оно сокращается.
Отношение сокращается
Как найти ответ задачи темы без программы?
Расписать большие значения через самое маленькое из выражения — F(2024) — и сократить его. Раскроем формулу F(n) = n · F(n − 1) несколько раз:
- F(2026) = 2026 · F(2025) = 2026 · 2025 · F(2024);
- F(2025) = 2025 · F(2024).
Подставим в выражение и вынесем общий множитель:
(2026 · 2025 · F(2024) + 3 · 2025 · F(2024)) / F(2024) = (2026 + 3) · 2025 = 2029 · 2025 = 4 108 725.
Ответ совпал с программой из подтемы 2. Само F(2024) — число почти из шести тысяч цифр — считать не пришлось.
Тонкости:что можно сокращать
Сокращать можно только на число, не равное нулю. У нашей функции все значения положительные: F(1) = 1, а дальше умножаем на натуральные числа. Последнее умножение удобно сделать в Python: print(2029 * 2025).
Разность сокращается
А если в выражении не отношение, а разность?
Раскрыть большее значение до меньшего: меньшее вычтется целиком, и останутся только прибавки последних шагов. Пусть F(1) = 2; F(n) = F(n − 1) + 3n при n > 1. Найдём F(2026) − F(2023):
F(2026) = F(2025) + 3 · 2026 = F(2024) + 3 · 2025 + 3 · 2026 = F(2023) + 3 · 2024 + 3 · 2025 + 3 · 2026.
F(2026) − F(2023) = 3 · 2024 + 3 · 2025 + 3 · 2026 = 3 · 6075 = 18 225.
Так работает любая функция вида F(n) = F(n − 1) + a(n), где a(n) — прибавка на шаге: разность F(N) − F(M) равна сумме прибавок a(M + 1) + … + a(N). Сумма начинается с M + 1 — всё, что накоплено до F(M), вычитается.
Общее неизвестное
Что делать, если значений несколько и они вычитаются с множителями?
Обозначить самое маленькое значение буквой, выразить через неё остальные и проверить, что буква сократится. Пусть F(n) = 1 при n ≤ 2; F(n) = F(n − 2) + n при n > 2. Найдём 3 · F(30) − F(28) − F(26) − F(24).
Обозначим X = F(24). Тогда F(26) = X + 26, F(28) = X + 26 + 28 = X + 54, F(30) = X + 26 + 28 + 30 = X + 84. Подставляем:
3(X + 84) − (X + 54) − (X + 26) − X = 3X + 252 − X − 54 − X − 26 − X = 172.
Все X сократились: три со знаком плюс и три со знаком минус. Значит, ответ не зависит от F(24) — его и не нужно считать.
Если бы X не сократился, пришлось бы считать F(24) по-настоящему. Заменять неизвестное значение нулём или единицей «для удобства» нельзя.
Ветви и сокращение
А если у функции ветви по чётности?
Раскрывать так же, но формулу выбирать для каждого аргумента — и только для тех аргументов, что встретились по пути. Пусть F(1) = F(2) = 1, а при n > 2: F(n) = 3 · F(n − 2), если n нечётно; F(n) = 2n · F(n − 1) + F(n − 3), если n чётно. Найдём F(12) / F(7):
- 12 чётное: F(12) = 24 · F(11) + F(9).
- 11 и 9 нечётные: F(11) = 3 · F(9) = 9 · F(7), F(9) = 3 · F(7).
- Подставляем: F(12) = 24 · 9 · F(7) + 3 · F(7) = 219 · F(7).
Значит, F(12) / F(7) = 219. Понадобились только аргументы 12, 11, 9 и 7 — считать все значения от 1 до 12 не пришлось.
Точная арифметика
Когда деление в Python может подвести?
/ всегда даёт дробное число с ограниченной точностью, а // — целую часть частного. Поэтому // ставят там, где деление нацело, а дробные промежуточные значения считают точно.
В задаче темы деление нацело, и // даёт точный ответ. Если в условии спрашивают целую часть частного, это тоже //. А вот пример, где промежуточное значение дробное: G(n) = n / 2 при n ≥ 10; G(n) = 1 + G(n + 3) при n < 10. Найдём 2 · G(2).
G(2) = 1 + G(5) = 2 + G(8) = 3 + G(11), а G(11) = 11 / 2 = 5,5. Значит, G(2) = 8,5 и 2 · G(2) = 17.
Если в базе заменить / на //, получится 11 // 2 = 5, G(2) = 8 и ответ 16 — неверный. Целый ответ задачи не значит, что все деления по пути — нацело. Точно дроби считает :
from fractions import Fraction def G(n): if n >= 10: return Fraction(n, 2) return 1 + G(n + 3) print(2 * G(2))Тонкости:степень и ^
Если в условии n², в Python это n ** 2. Запись n ^ 2 — совсем другая операция над двоичными разрядами, и ошибки Python не покажет.
Итого
- Отношениерасписать до самого маленького значения и сократить
- Задача темы(2026 + 3) · 2025 = 4 108 725
- Разностьостаются прибавки a(M + 1) + … + a(N)
- Несколько значенийобщее неизвестное X должно сократиться
- Ветвираскрывать только нужные аргументы, ветвь — по каждому
- Деление
//— нацело и целая часть,Fraction— для дробей
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
//, а не через /?ОтветСкрыть ответ
// даёт точное целое. / даёт дробное 4108725.0, а при ответе больше 2⁵³ — ещё и неточное.Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Отношение факториалов
F(1) = 1; F(n) = n · F(n − 1) при n > 1. Найди (F(102) − 2 · F(101)) / F(100).
Введите число.
Подсказка
Распиши F(102) и F(101) через F(100) и вынеси его за скобки.
Решение
F(102) = 102 · 101 · F(100), F(101) = 101 · F(100). Числитель: (102 · 101 − 2 · 101) · F(100) = 101 · 100 · F(100). После сокращения: 101 · 100 = 10 100.
import sys sys.setrecursionlimit(5000) def F(n): if n == 1: return 1 return n * F(n - 1) print((F(102) - 2 * F(101)) // F(100))Ответ: 10100
Задача в формате экзамена: отношение
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = 1 при n = 1; F(n) = (n + 2) · F(n − 1), если n > 1. Чему равно значение выражения (F(2030) − 3 · F(2029)) / F(2028)?
Введите число.
Подсказка
Множитель здесь n + 2: F(2030) = 2032 · F(2029), F(2029) = 2031 · F(2028).
Решение
Числитель: 2032 · F(2029) − 3 · F(2029) = 2029 · F(2029) = 2029 · 2031 · F(2028). После сокращения на F(2028): 2029 · 2031 = 4 120 899.
import sys sys.setrecursionlimit(5000) def F(n): if n == 1: return 1 return (n + 2) * F(n - 1) print((F(2030) - 3 * F(2029)) // F(2028))Ответ: 4120899
Разность через одно
F(n) = 1 при n ≤ 3; F(n) = F(n − 2) + n при n > 3. Найди F(101) − F(95).
Введите число.
Подсказка
Раскрой F(101) до F(95): F(101) = F(99) + 101 = …
Решение
F(101) = F(95) + 97 + 99 + 101. F(95) вычитается целиком, остаётся 97 + 99 + 101 = 297.
def F(n): if n <= 3: return 1 return F(n - 2) + n print(F(101) - F(95))Ответ: 297
Задача в формате экзамена: разность
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями: F(n) = n при n ≤ 10; F(n) = n + F(n − 4), если n > 10. Чему равно значение выражения F(3001) − F(2993)?
Введите число.
Подсказка
Раскрой F(3001) через F(2997) до F(2993).
Решение
F(3001) = 3001 + F(2997) = 3001 + 2997 + F(2993). F(2993) вычитается, остаётся 3001 + 2997 = 5998.
import sys sys.setrecursionlimit(5000) def F(n): if n <= 10: return n return n + F(n - 4) print(F(3001) - F(2993))Ответ: 5998
Общее неизвестное
F(n) = 1 при n ≤ 3; F(n) = F(n − 3) + 2n при n > 3. Найди 2 · F(40) − F(37) − F(34).
Введите число.
Подсказка
Обозначь F(34) = X и вырази F(37) и F(40) через X.
Решение
F(37) = X + 74, F(40) = X + 74 + 80 = X + 154. 2(X + 154) − (X + 74) − X = 308 − 74 = 234 — X сократился.
def F(n): if n <= 3: return 1 return F(n - 3) + 2 * n print(2 * F(40) - F(37) - F(34))Ответ: 234
Отношение при ветвях по чётности
F(1) = F(2) = 1; при n > 2 F(n) = 2 · F(n − 2), если n нечётно, и F(n) = 3n · F(n − 1) + F(n − 3), если n чётно. Найди F(10) / F(5).
Введите число.
Подсказка
Вырази F(10) через F(9) и F(7), а их — через F(5).
Решение
10 чётное: F(10) = 30 · F(9) + F(7). 9 и 7 нечётные: F(9) = 2 · F(7) = 4 · F(5), F(7) = 2 · F(5). Значит, F(10) = 120 · F(5) + 2 · F(5) = 122 · F(5).
def F(n): if n <= 2: return 1 elif n % 2 == 1: return 2 * F(n - 2) else: return 3 * n * F(n - 1) + F(n - 3) print(F(10) // F(5))Ответ: 122
Дробь в базе
G(n) = n / 4 при n ≥ 20; G(n) = G(n + 3) + 2 при n < 20. Найди 4 · G(1).
Введите число.
Подсказка
База G(22) = 22 / 4 = 5,5 — дробь: не заменяй / на //.
Решение
Аргументы 1, 4, 7, 10, 13, 16, 19, 22: семь переходов по +2 и база G(22) = 5,5. G(1) = 5,5 + 14 = 19,5, и 4 · G(1) = 78. С // в базе вышло бы 4 · 19 = 76.
from fractions import Fraction def G(n): if n >= 20: return Fraction(n, 4) return G(n + 3) + 2 print(4 * G(1))Ответ: 78