Теория к ЕГЭ по информатике

Перевод в двоичную систему: делим число на 2 и записываем остатки снизу вверх. Дописать цифру $d$ справа к двоичной записи $N$ — то же, что получить $2N+d$; дописать две цифры — $4N+\overline{d_1{d}_2}$.

Правило произведения: если позицию 1 можно заполнить $a$ способами, позицию 2 — $b$ способами, то пару — $ab$. Число способов выбрать $k$ позиций из $L$: $C_L^k=\frac{L!}{k!(L-k)!}$.

Число в системе с основанием $b$: $\overline{a_n\dots a_0}=a_n{b}^n+\dots +a_0$. $b^k$ записывается как 1 и $k$ нулей. $b^k-1$ — это $k$ цифр $(b-1)$. Перевод — последовательным делением на $b$.

Рекурсивная функция определяется через свои значения при меньших аргументах и базовый случай. Считать удобнее снизу вверх: $F(1),F(2),\dots ,F(N)$ — каждое значение по уже найденным.