Алгоритмы, основанные на простых множествах

Представление множеств

Множества – одно из основных понятий вычислительной математики и программирования. Почти каждая математическая модель, описывающая объекты реального мира содержит множества. Под простыми множествами мы будем понимать последовательность простых данных, то есть символов и чисел.

Основными структурами данных для хранения простых множеств являются массивы. Массивы могут быть одномерными и многомерными (наиболее распространены двумерные, или матрицы). Последовательность элементов одномерного массива имеет вид: A={1,2,3,4}. Произвольную последовательность элементов массива можно записать как (1, 2, 3). Для операций над элементами множеств могут привлекаться вспомогательные переменные. Часто используются указатели массива: l – левая граница, r – правая граница. В процессе работы алгоритма значение l увеличивается, а r – уменьшается.

Обмен значений двух переменных

Эта задача является наиболее распространенной и используется во многих, более сложных алгоритмов. Наиболее общее ее решение гласит – необходима третья переменная.

Алгоритм 1. Обмен значений двух переменных

SWAP(A,B)

t ←A

A←B

B←t

Однако, для числовых A и В можно использовать алгоритм без дополнительной переменной.

Алгоритм 2. Обмен значений двух переменных-2

SWAP(A,B)

А← A + B

B ←A – B

A←A – B

Если начальные значения А и В обозначим А0, В0, то в каждой строке алгоритма А и В принимают следующие значения:

А = А0 + В0,             В = В0

А = А0 + В0,             В = А0

А = В0,           В = А0

Нахождение минимального и максимального элемента

Одной из наиболее часто встречающихся задач является поиск элемента массива, удовлетворяющего заданным требованиям. В этом случае производят однократный перебор всех элементов и проверку каждого значения при заданном условии. Поиск макс./мин. значений может быть также осуществлен при однократном проходе цикла:

Алгоритм 3. Нахождение мин/макс значений элементов

A[] ← (A₁,A₂, …A_N)

MINMAX(A[])

Min←A[1]

max ←A[1]

for I←2 to N do

if A[I] < min then min←A[I] fi

if A[I] > max then max←A[I] fi

od

Группировка элементов массива

Дан массив А и число В. Переставить элементы в массиве А таким образом, чтобы слева от некоторой границы стояли числа меньше В, а справа – больше В.

Алгоритм 4. Группировка элементов массива

A[] ← (A₁,A₂, …A_N)

GROUPING1(A[],N,B)

l ←0

r ←N

while l ≠ r do

if A[l + 1]≤B then l←l + 1

elsif A[r] ≥ B then r←r + 1

else SWAP(A[l + 1],A[r])

l ←l + 1, r←r – 1

fi

od

Та же задача, но требуется, чтобы сначала шли элементы, меньшие B, затем равные B, а лишь затем большие B.

Решение. Теперь потребуются три границы: до первой будут идти элементы, меньшие B, от первой до второй – равные B, затем неизвестно какие до третьей, а после третьей – большие B. (Более симметричное решение использовало бы четыре границы, но вряд ли игра стоит свеч.) В качестве очередного рассматриваемого элемента берем элемент справа от средней границы.

Алгоритм 5. Группировка элементов массива-2

A[]← (A₁,A₂, …A_N)

GROUPING2(A[],N,B)

l← 0

m← 0

r← N

while m ≠ r do

if A[m + 1] = B then

m ← m + 1

elsif A[m + 1] > B then

SWAP(A[m + 1],A[r])

r← r – 1

else

SWAP(A[m + 1],A[l + 1])

l ← l + 1,m←m + 1

fi

od

Генерирование перестановок

Рассматривая задачу комивояжера мы столкнулись с необходимостью генерировать перестановки в массиве целых чисел, означающих номера городов. Под перестановкой мы будем понимать возможную последовательность элементов массива. Например, для массива из трех элементов A={1,2,3} можно указать 6 различных последовательностей: (1, 2, 3), (2, 1, 3), (2, 3, 1), (3, 2, 1), (3, 1, 2), (1, 3, 2). Число перестановок для множества из N элементов равно (N!). А вот пример программы, которая генерирует перестановки, используя антилексографический порядок (описать алгоритм самостоятельно) для перебора всех маршрутов в задаче комивояжера:

#include <stdio.h>
#include <conio.h>
int N=4;
void reverse(int *tours,int N)
{
int i=1,j=N,t;
while(i<j)
{
t=tours[i];
tours[i]=tours[j];
tours[j]=t;
i++;j--;
}
}
void antilex(int *tours,int m)
{
int t;
if(m==1)
{
for(int k=1;k<=N;k++)
printf("%d ",tours[k]);
printf("\n");
}
else
for(int i=1;i<=m;i++)
{
antilex(tours,m-1);
if(i<m)
{
t=tours[i];
tours[i]=tours[m];
tours[m]=t;
reverse(tours,m-1);
}
}
}
void main(void)
{
int tours[4];
for(int i=1;i<=N;i++)
tours[i]=i;
clrscr();
antilex(tours,N);
}