Сроки выполнения задания:

до 27 марта

Написать 3 реализации алгоритма поиска всех уникальных пар целочисленных НЕОТРИЦАТЕЛЬНЫХ элементов в массиве, в сумме дающих заданное число

Требуется написать 3 функции на языках С/С++, принимающие массив целых, искомое число и возвращающие количество уникальных пар элементов, в сумме дающих value.

Так, например, при value=50 массив {20,30,30,40,40} содержит 2 пары (20-30, 20-30).

Массив, подаваемый на вход, должен быть отсортирован по возрастанию элементов!

Функции должны иметь следующую сигнатуру и располагаться в файле src/alg.cpp:

int countPairs1(int *arr,int len,int value)
{

}
int countPairs2(int *arr,int len,int value)
{

}
int countPairs3(int *arr,int len,int value)
{

}

Описания параметров функций:

• arr - адрес первого элемента массива (массив из неубывающих элементов!)
• len - размер массива в элементах
• value - искомое значение суммы двух элементов (т.е. arr[i]+arr[j]==value)

Описания функций:

• Функция countPairs1 должна содержать реализацию массива с полным перебором всех сумм (цикл в цикле).
• Функция countPairs2 должна содержать улучшенный поиск сумм, с отбрасыванием заведомо лишних значений (движение с двух концов навстречу).
• Функция countPairs3 должна содержать алгоритм бинарного поиска второго элемента пары, в сумме дающей заданное число.

Функции возвращает количество пар (0 - если таких нет).

Все три функции для одного и того же массива должны возвращать одно и тоже число. Время работы функций должно быть (t1>t2>t3).

Помимо указанных функций, в файл alg.cpp можно помещать определения вспомогательных функций.