Однострочники на С++. Часть 2

в 15:52, , рубрики: c++, quicksort, Алгоритмы, бинарный поиск в массиве, массив, однострочники, Программирование, С++, случайные числа, сортировка, метки: , , , , , ,

image
Ранее я уже публиковал статью о Однострочниках на С++, теперь я хочу рассказать несколько STL алгоритмов и не только.
Заинтересовавших прошу под кат.

1. Сравнение двух чисел

Функция возвращает значение разницы между двумя числами, поэтому если разница больше 0, то число a больше b, если равна 0, то числа одинаковы, иначе число a меньше b.

template <typename TYPE>
int compare (const TYPE a, const TYPE b){
   return ( a - b );
}

Посмотреть листинг программы...

#include <iostream>
using namespace std;

//шаблон функция если возвращает отрицательное значение то число a<b
//если 0 то числа равные, иначе число a>b  
template <typename TYPE>
int compare (const TYPE a, const TYPE b){
   return ( a - b );
}

int main( int argc, char const *argv[] ) {
  int a=1,b=2;
  cout<<compare(a,b)<<endl;
  return 0;
}

2. Сортировка массива

Элементы сортируются в диапазоне [left, right). Сложность алгоритма О(nlog(n)), где n=right-left.

template <typename TYPE>
int sort(TYPE *mas, int left,  int right) {
    sort (mas+left, mas+right);
}

Посмотреть листинг программы...

#include <iostream>
using namespace std;

//шаблон функции параметрамы которой есть левая и 
//правая граница масива которую нужно отсортировать
template <typename TYPE>
int sort(TYPE *mas, int left,  int right) {
    sort (mas+left, mas+right);
}

int main(int argc, char const *argv[]) {
  int a[5]={5,4,3,2,1};
  sort(a,0,5);
  for(int i=0;i<5;i++)
   cout<<*(a+i)<<endl;
  return 0;
}

3. Изменение массива

С левой границы по правую элементы массива можно изменить, увеличить или уменьшить.

int transformArray(int * arr, int left, int right, int value) {
  transform(arr+left, arr+right, arr+left, bind2nd(plus<int>(), value));
}

Посмотреть листинг программы...

#include <iostream>
using namespace std;

//функция параметры которой сам массив, левая и правая граница
//которую нужно изменить, та value - число на котороэ нужно
//поменять елементы масива
int transformArray(int * arr, int left, int right, int value) {
  transform(arr+left, arr+right, arr+left, bind2nd(plus<int>(), value));
}

int main(int argc, char const *argv[]) {
  int a[5]={1,2,3,4,5};
  transformArray(a,0,5,-1);
  for(int i=0;i<5;i++)
    cout<<*(a+i)<<endl;
  return 0;
}

4. Заполнение массива случайными числами

Массив заполняется случайными числами, но нужно ещё применить srand.

int genArr(int * arr, int left, int right) {
  generate(arr+left, arr+right, rand);
}

Посмотреть листинг программы...

#include <iostream>
using namespace std;

//функция генерирует случайние числа и вносит
//их у масив начиная с левой по правую границу
int genArr(int * arr, int left, int right) {
  generate(arr+left, arr+right, rand);
}

int main(int argc, char const *argv[]) {
  int a[5],key=123;
  srand(key);//чтобы числа были разные
  genArr(a,0,5);
  for(int i=0;i<5;i++)
    cout<<*(a+i)<<endl;
  return 0;
}

5. Генерация перестановки элементов массива

Функцию можно вызывать много раз, при этом постоянно будут разные перестановки до того момента, когда функция (int)genPermunation(int *, int, int) вернет значение 0. Тоисть больше нельзя найти перестановку из элементов массива.

int genPermunation(int * arr, int left, int right) {
  return next_permutation(arr+left, arr+right);
}

Посмотреть листинг программы...

#include <iostream>
using namespace std;

//функция генерирует перестановку елементов
//если функция вернёт значение 0, то перестановок больше нет
int genPermunation(int * arr, int left, int right) {
  return next_permutation(arr+left, arr+right);
}

int main(int argc, char const *argv[]) {
  int a[5]={1,2,3,4,5};
  while(genPermunation(a,0,5)) {
     for(int i=0;i<5;i++)
       cout<<*(a+i)<<" ";
     cout<<'n';
   }
   return 0;
}

6. Проверка наличии элемента в массиве

Функция возвращает 1 или 0, поэтому послу return дважды!.. Параметрами функции есть массив, правая, левая граница и само число. Но для этой функции надо чтобы в массиве был барьерный элемент, у меня он например 0.

int find(int * arr, int left, int right, int value) {
  return !(!*find(arr+left,arr+right,value));
}

Посмотреть листинг программы...

#include <iostream>
using namespace std;

//функция проверяет наличие элемента и если элемента
//найден возвращает 1 иначе 0
int find(int * arr, int left, int right, int value) {
  return !(!*find(arr+left,arr+right,value));
}

int main(int argc, char const *argv[]) {
  int a[5]={1,2,3,4,0};
  cout<<(find(a,0,4,5)?"YESn":"NOn");
  return 0;
}

7. Подсчёт элементов

Функция считает количество элементов со значением value в массиве начиная с правой по левою границу.

int count(int * arr, int left, int right, int value) {
  return count(arr+left,arr+right,value);
}

Посмотреть листинг программы...

#include <iostream>
using namespace std;

//функция подсчитивает количиство элеметов со значением value
int count(int * arr, int left, int right, int value) {
  return count(arr+left,arr+right,value);
}

int main(int argc, char const *argv[]) {
  int a[5]={1,2,3,4,1};
  cout<<count(a,0,5,1)<<endl;
  return 0;
}

8. Поиск минимума(или максимума) в массиве

int min_element(int * arr, int left, int right) {
  return *min_element(arr+left,arr+right);
}
int max_element(int * arr, int left, int right) {
  return *max_element(arr+left,arr+right);
}

Посмотреть листинг программы...

#include <iostream>
using namespace std;

//ищем минимальное значение в массиве
int min_element(int * arr, int left, int right) {
  return *min_element(arr+left,arr+right);
}

//ищем максимальное значение в массиве
int max_element(int * arr, int left, int right) {
  return *max_element(arr+left,arr+right);
}

int main(int argc, char const *argv[]) {
  int a[5]={1,2,3,4,1};
  cout<<min_element(a,0,5)<<endl;
  cout<<max_element(a,0,5)<<endl;
  return 0;
}

9.Бинарный поиск

Возвращает значение true, если в упорядочиваемому массиве есть элемент value, в противном случае false.

bool binary_search(int * arr(begin), int * arr(end), int value);

Посмотреть листинг программы...

#include <iostream>
using namespace std;

int main(int argc, char const *argv[]) {
  int a[5]={1,4,3,2,9};
  sort(a,a+5);
  cout<<(binary_search(a,a+5,3)?"YESn":"NOn");
  return 0;
}

10. Сортировка слиянием

Если мы имеем два сортирование массивы, то ми можем объединить два массива с помощью слияния.

merge ( int * arrA(begin), int * arrA(end), int * arrB(begin), int *arrB(end), int * arrC(begin));

Посмотреть листинг программы...

#include <iostream>
using namespace std;

int main(int argc, char const *argv[]) {
  int a[5]={1,3,5,7,9};
  int b[5]={10,8,6,4,2};
  int c[10];
  sort(a,a+5);
  sort(b,b+5);
  merge(a,a+5,b,b+5,c);
  for(int i=10;i--;cout<<c[9-i]<<" ");
  cout<<endl;
  return 0;
}

Автор: Oleksandr17

* - обязательные к заполнению поля