e-maxx_algo
.pdf
скорее занимательная тенденция.
Свойства
Числа Фибоначчи обладают множеством интересных математических свойств. Вот лишь некоторые из них:
●Соотношение Кассини:
●Правило "сложения":
●Из предыдущего равенства при 
вытекает:
●Из предыдущего равенста по индукции можно получить, что 
всегда кратно 
.
●Верно и обратное к предыдущему утверждение: если 
кратно 
, то 
кратно 
.
●НОД-равенство:
●По отношению к алгоритму Евклида числа Фибоначчи обладают тем замечательным свойством, что они являются наихудшими входными данными для этого алгоритма (см. "Теорема Ламе" в Алгоритме Евклида).
Фибоначчиева система счисления
Теорема Цекендорфа утверждает, что любое натуральное число 
можно представить единственным образом в виде суммы чисел Фибоначчи:
где 
, 
, , 
(т.е. в записи нельзя использовать два соседних числа Фибоначчи).
Отсюда следует, что любое число можно однозначно записать в фибоначчиевой системе счисления, например:
причём ни в каком числе не могут идти две единицы подряд.
Нетрудно получить и правило прибавления единицы к числу в фибоначчиевой системе счисления: если младшая цифра равна 0, то её заменяем на 1, а если равна 1 (т.е. в конце стоит 01), то 01 заменяем на 10. Затем "исправляем" запись, последовательно исправляя везде 011 на 100. В результате за линейное время будет получена запись нового числа.
Перевод числа в фибоначчиеву систему счисления осуществляется простым "жадным" алгоритмом: просто перебираем числа Фибоначчи от больших к меньшим и, если некоторое , то входит в запись числа 
, и
мы отнимаем 
от 
и продолжаем поиск.
Формула для n-го числа Фибоначчи
Формула через радикалы
Существует замечательная формула, называемая по имени французского математика Бине (Binet), хотя она была известна до него Муавру (Moivre):
Эту формулу легко доказать по индукции, однако вывести её можно с помощью понятия образующих функций или с помощью решения функционального уравнения.
Сразу можно заметить, что второе слагаемое всегда по модулю меньше 1, и более того, очень быстро убывает (экспоненциально). Отсюда следует, что значение первого слагаемого даёт "почти" значение . Это можно записать в строгом виде:
где квадратные скобки обозначают округление до ближайшего целого.
Впрочем, для практического применения в вычислениях эти формулы мало подходят, потому что требуют очень высокой точности работы с дробными числами.
Матричная формула для чисел Фибоначчи
Нетрудно доказать матричное следующее равенство:
Но тогда, обозначая
получаем:
|
|
Таким образом, для нахождения -го числа Фибоначчи надо возвести матрицу |
в степень . |
Вспоминая, что возведение матрицы в -ую степень можно осуществить за |
(см. Бинарное возведение |
в степень), получается, что -ое число Фибоначчи можно легко вычислить за |
c использованием |
только целочисленной арифметики. |
|
Периодичность последовательности Фибоначчи по модулю
Рассмотрим последовательность Фибоначчи |
по некоторому модулю . Докажем, что она является периодичной, |
||
и причём период начинается с |
(т.е. предпериод содержит только |
). |
|
Докажем это от противного. Рассмотрим 
пар чисел Фибоначчи, взятых по модулю 
:
Поскольку по модулю 
может быть только различных пар, то среди этой последовательности найдётся как минимум две одинаковые пары. Это уже означает, что последовательность периодична.
Выберем теперь среди всех таких одинаковых пар две одинаковые пары с наименьшими номерами. Пусть это пары
с некоторыми номерами |
и |
. Докажем, что |
. Действительно, в противном случае |
для них найдутся предыдущие пары |
и |
, которые, по свойству чисел Фибоначчи, также |
|
будут равны друг другу. Однако это противоречит тому, что мы выбрали совпадающие пары с наименьшими номерами, что и требовалось доказать.
Литература
● Роналд Грэхэм, Дональд Кнут, Орен Паташник. Конкретная математика [1998]
Обратный элемент в кольце по модулю
Определение
Пусть задан некоторый натуральный модуль 
, и рассмотрим кольцо, образуемое этим модулем (т.е. состоящее из чисел от 
до 
). Тогда для некоторых элементов этого кольца можно найти обратный элемент.
Обратным к числу 
по модулю 
называется такое число 
, что:
и его нередко обозначают через 
.
Понятно, что для нуля обратного элемента не существует никогда; для остальных же элементов обратный может как существовать, так и нет. Утверждается, что обратный существует только для тех элементов 
, которые
взаимно просты с модулем 
.
Рассмотрим ниже два способа нахождения обратного элемента, работающих при условии, что он существует.
В завершение, рассмотрим алгоритм, который позволяет найти обратные ко всех числам по некоторому модулю за линейное время.
Нахождение с помощью Расширенного алгоритма Евклида
Рассмотрим вспомогательное уравнение (относительно неизвестных 
и 
):
|
|
|
Это линейное диофантово уравнение второго порядка. Как показано в соответствующей статье, из |
|
|
условия |
следует, что это уравнение имеет решение, которое можно найти с помощью |
|
Расширенного алгоритма Евклида (отсюда же, кстати говоря, следует, что когда |
, решения, а потому |
|
и обратного элемента, не существует). |
|
|
С другой стороны, если мы возьмём от обеих частей уравнения остаток по модулю 
, то получим:
Таким образом, найденное 
и будет являться обратным к 
.
Реализация (с учётом того, что найденное 
надо взять по модулю 
, и 
могло быть отрицательным):
int x, y;
int g = gcdex (a, m, x, y); if (g != 1)
cout << "no solution";
else {
x = (x % m + m) % m; cout << x;
}
Асимптотика этого решения получается 
.
Нахождение с помощью Бинарного возведения в степень
Воспользуемся теоремой Эйлера:
которая верна как раз для случая взаимно простых 
и 
.
Кстати говоря, в случае простого модуля 
мы получаем ещё более простое утверждение — малую теорему Ферма:
Умножим обе части каждого из уравнений на 
, получим:
●для любого модуля 
:
●для простого модуля 
:
Таким образом, мы получили формулы для непосредственного вычисления обратного. Для практического применения обычно используют эффективный алгоритм бинарного возведения в степень, который в нашем
случае позволит произвести возведение в степень за 
.
Этот метод представляется несколько проще описанного в предыдущем пункте, однако он требует знания значения функции Эйлера, что фактически требует факторизации модуля 
, что иногда может оказаться весьма сложной задачей.
Если же факторизация числа известна, то тогда и этот метод также работает за асимптотику 
.
Нахождение всех простых по заданному модулю за линейное время
Пусть дан простой модуль 
. Требуется для каждого числа в отрезке 
найти обратное к нему.
Применяя описанные выше алгоритмы, мы получим лишь решения с асимптотикой |
. Здесь же |
|||
мы приведём простое решение с асимптотикой |
. |
|
|
|
Решение это выглядит следующим образом. Обозначим через |
искомое обратное к числу |
по модулю . |
||
Тогда для |
верно тождество: |
|
|
|
|
|
|
|
|
|
|
|
|
|
Реализация этого удивительно лаконичного решения:
r[1] = 1;
for (int i=2; i<m; ++i)
r[i] = (m - (m/i) * r[m%i] % m) % m;
Доказательство этого решения представляет из себя цепочку простых преобразований: Распишем значение 
:
откуда, беря обе части по модулю 
, получаем:
Умножая обе части на обратное к 
и обратное к 
, получаем искомую формулу:
что и требовалось доказать.
Код Грея
Определение
Кодом Грея называется такая система нумерования неотрицательных чисел, когда коды двух соседних чисел отличаются ровно в одном бите.
Например, для чисел длины 3 бита имеем такую последовательность кодов Грея: 
, 
, 
, 
, 
,
, 
, 
. Например, 
.
Этот код был изобретен Фрэнком Грэем (Frank Gray) в 1953 году.
Нахождение кода Грея
Рассмотрим биты числа и биты числа |
. Заметим, что -ый бит |
равен единице только в том случае, когда |
||
-ый бит равен единице, а |
-ый бит равен нулю, или наоборот ( |
-ый бит равен нулю, а |
-ый равен |
|
единице). Таким образом, имеем: |
|
: |
|
|
int g (int n) {
return n ^ (n >> 1);
}
Нахождение обратного кода Грея
Требуется по коду Грея 
восстановить исходное число 
.
Будем идти от старших битов к младшим (пусть самый младший бит имеет номер 1, а самый старший — ). Получаем такие соотношения между битами 
числа 
и битами 
числа 
:
Ввиде программного кода это проще всего записать так:
int rev_g (int g) { int n = 0;
for (; g; g>>=1) n ^= g;
return n;
}
Применения
Коды Грея имеют несколько применений в различных областях, иногда достаточно неожиданных:
●
-битный код Грея соответствует гамильтонову циклу по 
-мерному кубу.
●В технике, коды Грея используются для минимизации ошибок при преобразовании аналоговых сигналов в цифровые (например, в датчиках). В частности, коды Грея и были открыты в связи с этим применением.
●Коды Грея применяются в решении задачи о Ханойских башнях.
Пусть — количество дисков. Начнём с кода Грея длины , состоящего из одних нулей (т.е. |
), и будем двигаться |
||
по кодам Грея (от |
переходить к |
). Поставим в соответствие каждому -ому биту текущего кода Грея - |
|
ый диск (причём самому младшему биту соответствует наименьший по размеру диск, а самому старшему биту
— наибольший). Поскольку на каждом шаге изменяется ровно один бит, то мы можем понимать изменение бита 
как перемещение 
-го диска. Заметим, что для всех дисков, кроме наименьшего, на каждом шаге имеется ровно
один вариант хода (за исключением стартовой и финальной позиций). Для наименьшего диска всегда имеется
два варианта хода, однако имеется стратегия выбора хода, всегда приводящая к ответу: если 
нечётно, то последовательность перемещений наименьшего диска имеет вид (где
— стартовый стержень, 
— финальный стержень, 
— оставшийся стержень), а если 
чётно, то 
.
● Коды Грея также находят применение в теории генетических алгоритмов.
Задачи в online judges
Список задач, которые можно сдать, используя коды Грея: ● SGU #249 "Matrix" [сложность: средняя]
Длинная арифметика
Длинная арифметика — это набор программных средств (структуры данных и алгоритмы), которые позволяют работать с числами гораздо больших величин, чем это позволяют стандартные типы данных.
Виды целочисленной длинной арифметики
Вообще говоря, даже только в олимпиадных задачах набор средств достаточно велик, поэтому произведём классификацию различных видов длинной арифметики.
Классическая длинная арифметика
Основная идея заключается в том, что число хранится в виде массива его цифр.
Цифры могут использоваться из той или иной системы счисления, обычно применяются десятичная система счисления и её степени (десять тысяч, миллиард), либо двоичная система счисления.
Операции над числами в этом виде длинной арифметики производятся с помощью "школьных" алгоритмов сложения, вычитания, умножения, деления столбиком. Впрочем, к ним также применимы алгоритмы быстрого умножения: Быстрое преобразование Фурье и Алгоритм Карацубы.
Здесь описана работа только с неотрицательными длинными числами. Для поддержки отрицательных чисел необходимо ввести и поддерживать дополнительный флаг "отрицательности" числа, либо же работать в дополняющих кодах.
Структура данных
Хранить длинные числа будем в виде вектора чисел 
, где каждый элемент — это одна цифра числа.
typedef vector<int> lnum;
Для повышения эффективности будем работать в системе по основанию миллиард, т.е. каждый элемент вектора 
содержит не одну, а сразу 
цифр:
const int base = 1000*1000*1000;
Цифры будут храниться в векторе в таком порядке, что сначала идут наименее значимые цифры (т.е. единицы, десятки, сотни, и т.д.).
Кроме того, все операции будут реализованы таким образом, что после выполнения любой из них лидирующие нули (т. е. лишние нули в начале числа) отсутствуют (разумеется, в предположении, что перед каждой операцией лидирующие нули также отсутствуют). Следует отметить, что в представленной реализации для числа ноль корректно поддерживаются сразу два представления: пустой вектор цифр, и вектор цифр, содержащий единственный элемент — ноль.
Вывод
Самое простое — это вывод длинного числа.
Сначала мы просто выводим самый последний элемент вектора (или 
, если вектор пустой), а затем выводим все оставшиеся элементы вектора, дополняя их нулями до 
символов:
printf ("%d", a.empty() ? 0 : a.back()); for (int i=(int)a.size()-2; i>=0; --i)
printf ("%09d", a[i]);
(здесь небольшой тонкий момент: нужно не забыть записать приведение типа |
, поскольку в противном случае |
||
число |
будут беззнаковым, и если |
, то при вычитании произойдёт переполнение) |
|
Чтение
Считываем строку в 
, и затем преобразовываем её в вектор:
for (int i=(int)s.length(); i>0; i-=9)
if (i < 9)
a.push_back (atoi (s.substr (0, i).c_str()));
else
a.push_back (atoi (s.substr (i-9, 9).c_str()));
Если использовать вместо 
массив 
'ов, то код получится ещё компактнее:
for (int i=(int)strlen(s); i>0; i-=9) { s[i] = 0;
a.push_back (atoi (i>=9 ? s+i-9 : s));
}
Если во входном числе уже могут быть лидирующие нули, то их после чтения можно удалить таким образом:
while (a.size() > 1 && a.back() == 0) a.pop_back();
Сложение
Прибавляет к числу 
число 
и сохраняет результат в 
:
int carry = 0;
for (size_t i=0; i<max(a.size(),b.size()) || carry; ++i) { if (i == a.size())
a.push_back (0);
a[i] += carry + (i < b.size() ? b[i] : 0); carry = a[i] >= base;
if (carry) a[i] -= base;
}
Вычитание
Отнимает от числа 
число 
(
) и сохраняет результат в 
:
int carry = 0;
for (size_t i=0; i<b.size() || carry; ++i) {
a[i] -= carry + (i < b.size() ? b[i] : 0); carry = a[i] < 0;
if (carry) a[i] += base;
}
while (a.size() > 1 && a.back() == 0) a.pop_back();
Здесь мы после выполнения вычитания удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
Умножение длинного на короткое
Умножает длинное 
на короткое 
(
) и сохраняет результат в 
:
int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i) { if (i == a.size())
a.push_back (0);
long long cur = carry + a[i] * 1ll * b; a[i] = int (cur % base);
carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0) a.pop_back();
Здесь мы после выполнения деления удаляем лидирующие нули, чтобы поддерживать предикат о том, что таковые отсутствуют.
(Примечание: способ дополнительной оптимизации. Если скорость работы чрезвычайно важна, то можно попробовать заменить два деления одним: посчитать только целую часть от деления (в коде это переменная 
), а затем уже посчитать по ней остаток от деления (с помощью одной операции умножения).
Как правило, этот приём позволяет ускорить код, хотя и не очень значительно.)
Умножение двух длинных чисел
Умножает 
на 
и результат сохраняет в 
:
lnum c (a.size()+b.size());
for (size_t i=0; i<a.size(); ++i)
for (int j=0, carry=0; j<(int)b.size() || carry; ++j) {
long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
c[i+j] = int (cur % base); carry = int (cur / base);
}
while (c.size() > 1 && c.back() == 0) c.pop_back();
Деление длинного на короткое
Делит длинное 
на короткое 
(
), частное сохраняет в 
, остаток в 
:
int carry = 0;
for (int i=(int)a.size()-1; i>=0; --i) {
long long cur = a[i] + carry * 1ll * base; a[i] = int (cur / b);
carry = int (cur % b);
}
while (a.size() > 1 && a.back() == 0) a.pop_back();
Длинная арифметика в факторизованном виде
Здесь идея заключается в том, чтобы хранить не само число, а его факторизацию, т.е. степени каждого входящего в него простого.
Этот метод также весьма прост для реализации, и в нём очень легко производить операции умножения и деления, однако невозможно произвести сложение или вычитание. С другой стороны, этот метод значительно экономит память в сравнении с "классическим" подходом, и позволяет производить умножение и деление значительно (асимптотически) быстрее.
Этот метод часто применяется, когда необходимо производить деление по непростому модулю: тогда достаточно хранить число в виде степеней по простым делителям этого модуля, и ещё одного числа — остатка по этому же модулю.
Длинная арифметика по системе простых модулей (Китайская теорема или схема Гарнера)
Суть в том, что выбирается некоторая система модулей (обычно небольших, помещающихся в стандартные типы данных), и число хранится в виде вектора из остатков от его деления на каждый из этих модулей.
Как утверждает Китайская теорема об остатках, этого достаточно, чтобы однозначно хранить любое число в диапазоне от 0 до произведения этих модулей минус один. При этом имеется Алгоритм Гарнера, который позволяет произвести
это восстановление из модульного вида в обычную, "классическую", форму числа.
Таким образом, этот метод позволяет экономить память по сравнению с "классической" длинной арифметикой (хотя в некоторых случаях не столь радикально, как метод факторизации). Крому того, в модульном виде можно очень быстро производить сложения, вычитания и умножения, — все за асимптотически однаковое время, пропорциональное количеству модулей системы.
Однако всё это даётся ценой весьма трудоёмкого перевода числа из этого модульного вида в обычный вид, для чего, помимо немалых временных затрат, потребуется также реализация "классической" длинной арифметики с умножением.
Помимо этого, производить деление чисел в таком представлении по системе простых модулей не представляется возможным.
Виды дробной длинной арифметики
Операции над дробными числами встречаются в олимпиадных задачах гораздо реже, и работать с огромными
дробными числами значительно сложнее, поэтому в олимпиадах встречается только специфическое
подмножество дробной длинной арифметики.
Длинная арифметика в несократимых дробях
Число представляется в виде несократимой дроби , где 
и 
— целые числа. Тогда все операции над дробными числами нетрудно свести к операциям над числителями и знаменателями этих дробей.
Обычно при этом для хранения числителя и знаменателя приходится также использовать длинную арифметику, но, впрочем, самый простой её вид — "классическая" длинная арифметика, хотя иногда оказывается достаточно встроенного 64-битного числового типа.
Выделение позиции плавающей точки в отдельный тип
Иногда в задаче требуется производить расчёты с очень большими либо очень маленькими числами, но при этом не допускать их переполнения. Встроенный -байтовый тип , как известно, допускает значения экспоненты в диапазоне 
, чего иногда может оказаться недостаточно.
Приём, собственно, очень простой — вводится ещё одна целочисленная переменная, отвечающая за экспоненту, а после выполнения каждой операции дробное число "нормализуется", т.е. возвращается в отрезок ,
путём увеличения или уменьшения экспоненты.
При перемножении или делении двух таких чисел надо соответственно сложить либо вычесть их экспоненты. При сложении или вычитании перед выполнением этой операции числа следует привести к одной экспоненте, для чего одно из них домножается на 
в степени разности экспонент.
Наконец, понятно, что не обязательно выбирать 
в качестве основания экспоненты. Исходя из устройства встроенных типов с плавающей точкой, самым выгодным представляется класть основание равным 
.