1.5 Математика

Математика играет ключевую роль в спортивном программировании. Невозможно стать сильным участником соревнований без хорошей математической базы. В этом разделе собраны важные понятия и формулы, которые дальше будут встречаться в курсе.

Формулы сумм

Каждая сумма вида

\[ \sum_{x=1}^{n} x^k = 1^k + 2^k + 3^k + \dots + n^k, \]

где \(k\) — положительное целое число, имеет замкнутую формулу (это многочлен степени \(k+1\)).

Например:

\[ \sum_{x=1}^{n} x = 1 + 2 + \dots + n = \frac{n(n+1)}{2}, \]

\[ \sum_{x=1}^{n} x^2 = 1^2 + 2^2 + \dots + n^2 = \frac{n(n+1)(2n+1)}{6}. \]

(Существует и общая формула для таких сумм — формула Фаульхабера, но она довольно громоздкая.)

Арифметическая прогрессия

Арифметическая прогрессия — это последовательность, в которой разность между соседними членами постоянна.

Пример (разность \(+5\)):

4, 9, 14, 19

Сумма арифметической прогрессии вычисляется так:

\[ \underbrace{a + \dots + b}_{n\ \text{чисел}} = \frac{n(a+b)}{2}, \]

где \(a\) — первый член, \(b\) — последний, \(n\) — количество членов.

Проверка на примере:

\[ 4+9+14+19 = 4\cdot \frac{4+19}{2} = 46. \]

Почему это работает: среднее значение членов прогрессии равно \((a+b)/2\), а членов всего \(n\).

Геометрическая прогрессия

Геометрическая прогрессия — это последовательность, в которой отношение соседних членов постоянно.

Пример (знаменатель \(k=3\)):

2, 6, 18, 54

Сумма геометрической прогрессии:

\[ a + ak + ak^2 + \dots + b = \frac{bk - a}{k - 1}, \]

где \(a\) — первый член, \(b\) — последний, \(k\) — знаменатель прогрессии.

Проверка на примере:

\[ 2+6+18+54 = \frac{54\cdot 3 - 2}{3-1} = 80. \]

Вывод формулы (идея): пусть

\[ S = a + ak + ak^2 + \dots + b. \]

Тогда

\[ kS = ak + ak^2 + ak^3 + \dots + bk. \]

Вычитая \(S\) из \(kS\), получаем \(kS - S = bk - a\), откуда и следует формула.

Частный случай:

\[ 1 + k + k^2 + \dots + k^n = \frac{k^{n+1}-1}{k-1}\quad (k\neq 1). \]

Эта запись особенно часто всплывает при анализе алгоритмов и подсчётах количества состояний.

Функции

Функция \(\lfloor x \rfloor\) округляет число \(x\) вниз до целого, а функция \(\lceil x \rceil\) — вверх.

Например:

\[ \left\lfloor \frac{7}{3} \right\rfloor = 2,\qquad \left\lceil \frac{7}{3} \right\rceil = 3. \]

Функции \(\min(x_1,\dots,x_n)\) и \(\max(x_1,\dots,x_n)\) возвращают соответственно минимальное и максимальное из заданных значений.

Например:

\[ \min(2,7,4)=2,\qquad \max(2,7,4)=7. \]

Факториал

Факториал \(n!\) можно определить так:

\[ n! = \prod_{x=1}^{n} x = 1\cdot 2\cdot 3 \cdots n, \]

или рекурсивно:

\[ 0! = 1,\qquad n! = n\cdot (n-1)!. \]

Числа Фибоначчи

Числа Фибоначчи встречаются очень часто. Их можно определить рекурсивно:

\[ f(0)=0,\quad f(1)=1,\quad f(n)=f(n-1)+f(n-2). \]

Первые значения:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Существует и замкнутая формула (формула Бине):

\[ f(n)= \frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n\sqrt{5}}. \]

На практике в программировании Фибоначчи почти всегда считают через динамику/быстрое возведение матрицы, а не по этой формуле (из‑за погрешностей при работе с вещественными).

Логарифмы

Логарифм числа \(x\) по основанию \(k\) обозначается \(\log_k(x)\). По определению,

\[ \log_k(x)=a \iff k^a=x. \]

Полезная интуиция: \(\log_k(x)\) — это «сколько раз нужно делить \(x\) на \(k\), чтобы получить 1».

Например, \(\log_3(243)=5\), потому что:

243 → 81 → 27 → 9 → 3 → 1.

Логарифмы постоянно встречаются при анализе алгоритмов, где на каждом шаге что‑то делится пополам/на константу (двоичный поиск, быстрые структуры данных и т. п.).

Основные свойства:

• Логарифм произведения:

\[ \log_k(ab)=\log_k(a)+\log_k(b). \]

• Следствие (степень):

\[ \log_k(x^n)= n\cdot \log_k(x). \]

• Логарифм частного:

\[ \log_k\left(\frac{a}{b}\right)=\log_k(a)-\log_k(b). \]

• Переход к другому основанию:

\[ \log_u(x)=\frac{\log_k(x)}{\log_k(u)}. \]

Натуральный логарифм \(\ln(x)\) — логарифм по основанию \(e\approx 2{.}71828\).

Ещё один практический факт: число цифр целого \(x\) в системе счисления по основанию \(b\) равно

\[ \left\lfloor \log_b(x) \right\rfloor + 1. \]

Например, число \(200\) в двоичной системе — это \(11001000\), и действительно

\[ \left\lfloor \log_2(200) \right\rfloor + 1 = 8. \]