Category Archive: Алгоритмы

Сортировка кучей (GCC 4.9.1)

Реализация на GCC 4.9.1 сортировки кучей (пирамидальная сортировка). У сортировки кучей два больших достоинства:
  1. В худшем случае работает за O(n * log n)
  2. Не требует дополнительной памяти
Реализация:
#include<stdio.h>
//получить индекс левого потомка
int left(int i){
	return i * 2 + 1;
}
 
//получить индекс правого потомка
int right(int i){
	return i * 2 + 2;
}
 
//поменять местами два элемента массива
int swap(int *a,int i,int j){
	int tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
}
 
//вывести на экран массив
void print(int *a,int size){
	int i;
	for(i=0;i<size;i++){
		printf("%d ",a[i]);
	}
	printf("\n");
}
 
//переупорядочивание поддерева
void heapify(int *a,int size,int i){
	int l = left(i);
	int r = right(i);
	int largest = i;
	if(l < size && a[i] < a[l]){
		largest = l;
	}
	if(r < size && a[largest] < a[r]){
		largest = r;
	}
	if(i != largest){
		swap(a,i,largest);
		heapify(a,size,largest);
	}
}
 
//постройка кучи
void buildHeap(int *a,int size){
	int i;
	for(i=size/2 - 1;i>=0;i--){
		heapify(a,size,i);
	}
}
 
//сортировка кучей
void heapSort(int *a,int size){
	buildHeap(a,size);
//	printf("build\n");
//	print(a,size);
	while(--size > 0){
		swap(a,0,size);
		heapify(a,size,0);		
	}
}
 
int main(){	
	const int N = 9;
	int arr[9] = {1,6,3,5,9,4,2,8,7};
	print(arr,N);//вывести на экран исходный массив
	heapSort(arr,N);//сортировка кучей
	printf("=============\n");
	print(arr,N);//вывод отсортированного массива	
	return 0;
}
В результате исходный массив (1 6 3 5 9 4 2 8 7) будет отсортирован (1 2 3 4 5 6 7 8 9).

Перебор всех возможных вариантов

В данной статье будет рассмотрено два алгоритма перебора всех возможных вариантов. Для начала придумаем задачу, на примере которой будем рассматривать алгоритмы. Пусть у нас имеется множество S, состоящее из 4-х элементов: * - + /, и наша задача - перебрать все возможные комбинации из 3-х элементов, используя элементы множества S. Причем, выбираемые элементы могут повторяться. Например: "+*+". Первый алгоритм Сопоставим каждому элементу число, начиная с 0. * - 0 - - 1 + - 2 / - 3 Можно догадаться, что нужно перебрать элементы от 0 0 0 до 3 3 3: 0 0 0 0 0 1 0 0 2 0 0 3 0 1 0 0 0 1 ... ... 3 2 3 3 3 0 3 3 1 3 3 2 3 3 3 Всего получится 64 варианта (4 * 4 * 4 = 64) Далее нужно провести обратную операцию, сопоставив числу элемент множества S. Например, набору 2 0 2 соответствует +*+ В алгоритме мы будем имитировать сложение в столбик, каждый раз прибавляя единицу, чтобы получить новый вариант. Реализация:
char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов
int size = 3;//кол-во элементов
int arr[] = new int[size];//массив для хранения текущего варианта множества
outer: while(true){//вечный цикл
 
	//вывод варианта множества на экран
	for(int ndx : arr){
		System.out.print(abc[ndx]);
	}
	System.out.println();
 
	int i = size - 1;//ставим курсов в самую правую ячейку
	while(arr[i] == abc.length - 1){//движемся влево, если ячейка переполнена
		arr[i] = 0;//записываем в ячейку 0, т.к. идет перенос разряда
		i--;//сдвиг влево
		//если перенос влево невозможен, значит перебор закончен
		if(i < 0)break outer;
	}
	arr[i]++;//увеличиваем значение ячейки на единицу
}
В результате программа выведет все 64 варианта:
***
**-
**+
**/
*-*
*--
...
...
/++
/+/
//*
//-
//+
///
Второй алгоритм Для начала посчитаем сколько всего возможных комбинаций, это число равно n ^ k, где n - это размер алфавита (кол-во допустимых символов), а k - кол-во элементов в комбинации. Для нашего множества S, состоящего из *,-,+ и /, n равно 4. И т.к. нужно перебрать все комбинации из трех элементов, то k равно 3. Получаем: n ^ k = 4 ^ 3 = 64. В итоге мы должны получить 64 комбинации. Вот если бы существовал способ преобразования номера комбинации в элементы комбинации. И такой способ существует: для этого нужно номер комбинации преобразовать в k-значное число в системе счисления по основанию n. Первой комбинации будет соответствовать число 0, а последней 63. Перебирая числа от 0 до 63, нам нужно каждое число преобразовать в число в систему счисления по основанию 4. Для получения разрядов числа нужно целочисленно разделить число на 1, 4, 16 (т.е. n^0, n^1, n^2) и результат взять по модулю n. Пример: для числа 57 при k = 3 и n = 4 (57 / 1) % 4 = 57 % 4 = 1 (-) (57 / 4) % 4 = 14 % 4 = 2 (+) (57 / 16) % 4 = 3 % 4 = 3 (/) Т.е. комбинации под номером 57 соответствует комбинация -+/
char abc[] = new char[]{'*','-','+','/'};//множество допустимых символов (алфавит)
int N = abc.length;//N - размер алфавита
int K = 3;//кол-во элементов в комбинации
 
int pow[] = new int[K + 1];//массив для степеней числа N: N^0, N^1, .., N^K   
pow[0] = 1;
for (int i = 1; i <= K; i++) {//вычисляем степени числа N
	pow[i] = pow[i - 1] * N
}
 
//перебираем все номера комбинаций
for (int i = 0; i < pow[K]; i++) {
	char arr[] = new char[K];
	//вычисляем элементы комбинации
	for (int j = 0; j < K; j++) {
		//каждый элемент получаем из массива abc по индексу,
		//индекс - это число в системе счисления по основанию N (0..N-1)
		//в соответствующем разряде j (от 0 до K-1 включительно)
		arr[j] = abc[(i / pow[j]) % N];
	}
	//вывод в консоль
	for(char ch : arr){
		System.out.print(ch);
	}
	System.out.println();
}
Вывод программы:
0 ***
1 -**
2 +**
3 /**
4 *-*
.....
57 -+/
58 ++/
59 /+/
60 *//
61 -//
62 +//
63 ///
В данном алгоритме перебор идет как бы слева направо, но это не важно, т.к. мы перебираем все комбинации.

Перебор всех подмножеств заданного множества (Java)

Пусть дано множество, состоящее из четырех элементов: {a,b,c,d}. Необходимо перебрать все возможные подмножества данного множества: 1) {} - пустое множество 2) {a} 3) {b} 4) {a,b} 5) {c} 6) {a,c} 7) {b,c} 8) {a,b,c} 9) {d} 10) {a,d} 11) {b,d} 12) {a,b,d} 13) {c,d} 14) {a,c,d} 15) {b,c,d} 16) {a,b,c,d} Причем подмножества {a,b} и {b,a} считаются одним и тем же подмножеством. Данную задачу будем решать с использованием битовых масок и битовых операций. Сразу приведу реализацию:
char arr[] = new char[]{'a','b','c','d'};
int N = arr.length;
for (int mask = 0; mask < (1 << N); mask++) {//перебор масок			
	for (int j = 0; j < N; j++) {//перебор индексов массива
		if((mask & (1 << j)) != 0){//поиск индекса в маске
			System.out.print(arr[j] + " ");//вывод элемента
		}
	}
	System.out.println();//перевод строки для вывод следующего подмножества
}
А теперь пояснения. 1 << N - побитовый сдвиг единицы на N позиций влево. В двоичном виде единица выглядит так 00000001. В нашем случае N = 4. После сдвига на 4 позиции влево появится новое число, двоичный вид которого 00010000. Теперь, если вычесть из этого числа единицу получим: 00001111. Если опустить ведущие нули, то получим 1111. Четыре единицы - это состояние, когда в подмножество попадают все элементы, 0000 - пустое множество, 1010 - подмножество состоит из первого и третьего элемента множества (нумерация с нуля, отсчет ведется справа) и т.д. Т.е. мы перебираем числа, двоичное представление которых от 0000 до 1111. После того как мы получили маску (mask), необходимо узнать в каких позициях стоят единицы. Проверять будем следующим образом. Например, на каком-то шаге цикла программы маска равна 1100, мы перебираем все позиции путем сдвига единицы: 0001, 0010, 0100 и 1000. Для проверки воспользуемся операцией побитового И (если в одинаковых позициях стоят единицы, то результат единица, иначе ноль). В Java обозначается как & В нашем случае: 1100 & 0001 = 0000 1100 & 0010 = 0000 1100 & 0100 = 0100 1100 & 1000 = 1000 Т.е. если в итоге получилось число отличное от нуля, то включаем элемент в множество. 0100 - включаем в множество элемент с индексом 2 1000 - включаем в множество элемент с индексом 3 Нумерация с нуля и справа. Результат работы программы (первая строка пустая - это пустое множество):

a 
b 
a b 
c 
a c 
b c 
a b c 
d 
a d 
b d 
a b d 
c d 
a c d 
b c d 
a b c d 
В данной реализации мы хранили маски в типе int. (1 << 30) равно 1 073 741 824 Безопасное значение N для типа int: 30. Свыше 30 будет переполнение переменных типа int, поэтому нужно использовать long. При N > 30 перебор будет ощутимо все медленнее и медленнее. Если будете делать реализацию с long, то при сдвиге единицы нужно писать так:
1L << j
Т.е. нужно к единице приписать L, и тогда результат операции будет long, в противном случае будет int с переполнением.

НОК и НОД (lcm и gcd) на Java

НОД (Наибольший общий делитель) или gcd (Greatest Common Divisor) НОД - наибольшее число, которое является делителем одновременно для чисел a и b. Реализация (Алгоритм Евклида):
long gcd(long a,long b){
	return b == 0 ? a : gcd(b,a % b);		
}
Применение:
System.out.println(gcd(10,24));//результат: 2
System.out.println(gcd(12,24));//результат: 12
System.out.println(gcd(11,24));//результат: 1
НОК (Наименьшее общее кратное) или lcm (Least Common Multiple) НОК - наименьшее число, которое делится на a и b без остатка. НОК можно найти через НОД по следующей формуле: нок Реализация:
long lcm(long a,long b){
	return a / gcd(a,b) * b;
}
Примечание: a / gcd(a,b) * b более предпочтительно, чем a * b / gcd(a,b), т.к. во втором случае при больших числах переполнение случиться намного раньше. Применение:
System.out.println(lcm(3, 4));//результат: 12
System.out.println(lcm(3, 9));//результат: 9
System.out.println(lcm(5,12));//результат: 60