Бинарный поиск (binary_search, lower_bound, upper_bound)

binary_search
Формулировка задачи: Узнать, находится ли данный элемент в отсортированном массиве подобных элементов, для которых задано отношение порядка на множестве. Т.е. имея в наличии два элемента, можно однозначно определить операцию <. Сложность O(log(N)).
Реализация:

1. bool binary_search(const vector<int> &mas, const int &value)
2. {
3.   int l = 0, r = mas.size()-1;
4.   while (l<r)
5.   {
6.     int m = (l+r)>>1;
7.     if (mas[m] < value)
8.       l = m +1;
9.     else if (mas[m] > value)
10.       r = m - 1;
11.     else
12.       return true;
13.   }
14.   return mas[l] == value;
15. }

* This source code was highlighted with Source Code Highlighter.

Длинное + длинное

[Вся длинная арифметика]

Операция сложения двух длинных чисел:

1. BigInt operator + (const BigInt &a, const BigInt &b)
2. {
3.   BigInt res;
4.   res.amount = max(a.amount,b.amount);
5.   int r = 0;
6.   for (int i=0;i<res.amount | r;i++)
7.   {
8.     res.digits[i] = a.digits[i] + b.digits[i] + r;
9.     if (res.digits[i]>=osn)
10.     {
11.       res.digits[i]-=osn;
12.       r = 1;
13.     }
14.     else
15.       r = 0;
16.   }
17.   if (res.digits[res.amount])
18.     res.amount++; 
19.  
20.   return res;
21. }

* This source code was highlighted with Source Code Highlighter.

В данной реализации отсутствует операция взятия остатка от деления. Вместо этого используется вычитание значения основания системы счисления в строке 11.

P.S: Данная реализация появилась на основе статьи Виталия Гольдштейна с учетом оформления длинных чисел команды HotFinnKeys.

Предисловие [Длинная арифметика]

[Вся длинная арифметика] 

Итак мы начинаем разговор о длинной арифметике.
Под длинной арифметикой мы, как и все, будем понимать математические действия над числами, которые по своему размеру превышают ограничения стандартных типов данных. Так например в тип int(4 байта) уместиться число 2^31 = 2147483648 (~2e9), в unsigned int(те же 4 байта) – число 2^32 = 4294967296 (~4e9). В переменную типа long long или __int64(8 байт) “влезет” 2^63 = 9223372036854775808 (~9e18), в безнаковый тип в два раза больше (~1e19). Как мы видим, уже для чисел в 25 разрядов в десятичной системе счисления нет типа в 32 разрядной системе, который бы удовлетворял нашим нуждам. Как быть? Ведь на практике встречаются числа с куда большим количеством разрядов. Унывать не стоит! Предки уже решили эту проблему за нас. Нам остается просто научиться делать тоже самое и не изобретать велосипед. Хотя крайне полезно сперва его изобрести и попытаться самостоятельно решить возникшие в результате проблемы.

Длинная арифметика

Теория:
* Первая глава книги Окулова “Программирование в алгоритмах”.
* Раздел 4 Дистанционная подготовка по информатике
* e-maxx

Практика: Дистанционная подготовка

Условные обозначения:
* osn – основание системы счисления 
* A,B – “длинные” числа
* n – “короткое”, 0 <= n < osn

Предисловие
Основные операции:
* Ввод
* Вывод 
* A + n
* Сравнение
* A + B
* A – B (A >= B)
* A – B (со знаком)
* A * n
* A * B
* A / n, A % n 
* A / B, A % B

Дополнительные операции:
* A^n
* n!
* sqrt(A)
* N^N mod 10^P

Экзотика:
* A – n

Тренировка #4 [Меньшиков]

[Условия задач]                   [Список тренировок] 

4A. Совершенные числа
[perfect]
Хорошая несложная задача. Есть один подвох, на который натыкаются многие. Желаю наткнуться на него всем начинающим, чтобы глубже проникнуться задачей. 
4B. Разложение на слагаемые
[decomp]
Компактная рекурсивная реализация. В ходе решения встает только одна проблема: как не генерировать комбинации слагаемых, которые уже были до этого? Для этого, по рекомендации Меньшикова, условимся, что в получаемой комбинации предыдущее слагаемое не превышает текущего. Этим приемом можно пользоваться и в других подобных задачах для обеспечения уникальности последовательностей.