47954 (Основы дискретной математики), страница 3
Описание файла
Документ из архива "Основы дискретной математики", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "47954"
Текст 3 страницы из документа "47954"
Сортировка с помощью прямого включения
Элементы массива, начиная со второго, последовательно берутся по одному и включаются на нужное место в уже упорядоченную часть массива, расположенную слева от текущего элемента а[i]. В отличие от стандартной ситуации включения элемента в заданную позицию массива, позиция включаемого элемента при этом неизвестна. Определим её, сравнивая в цикле поочерёдно a[i] с a [i‑1], а [i‑2],… до тех пор, пока не будет найден первый из элементов меньший или равный а[i], либо не будет достигнут левый конец массива. Поскольку операции сравнения и перемещения чередуются друг с другом, то этот способ часто называют просеиванием или погружением. Очевидно, что программа, реализующая описанный алгоритм, должна содержать цикл в цикле.
program sortirovka_l;
(*сортировка включением по линейному поиску*)
const N=5;
type item= integer;
var a: array [0..n] of item; i, j: integer; x: item;
begin (*задание искомого массива*)
for i:=1 to N do begin write ('введите элемент a [', i, ']=');
readln (a[i])
end;
for i:=1 to N do begin write (a[i], ' ');
end;
writeln;
(*алгоритм сортировки включением*)
for i:=2 to n do
begin
x:=a[i]; j:=i; a[0]:=x; (*барьер*)
while x begin a[j]:=a [j‑1]; j:=j‑1; end; a[j]:=x; {for k:=1 to n do write (a[k], ' ') end; writeln;} end; (*вывод отсортированного массива*) for i:=1 to N do begin write (a[i], ' '); end; readln; end. В рассмотренном примере программы для анализа процедуры пошаговой сортировки можно рекомендовать использовать трассировку каждого прохода по массиву с целью визуализации его текущего состояния. В тексте программы в блоке непосредственного алгоритма сортировки в фигурных скобках находится строка, которая при удалении скобок выполнит требуемое (параметр k необходимо описать в разделе переменных – var k:integer). Вернемся к анализу метода прямого включения. Поскольку готовая последовательность уже упорядочена, то алгоритм улучшается при использовании алгоритма поиска делением пополам. Такой способ сортировки называют методом двоичного включения. program sortirovka_2; (*сортировка двоичным включением*) const N=5; type item= integer; var a: array [0..n] of item; i, j, m, L, R: integer; x: item; begin (*задание элементов массива*) for i: – l to N do begin write ('введите элемент a [', i, ']= '); readln (a[i]); end; for i:=1 to N do begin write (a[i], ' '); end; writeln; (*алгоритм сортировки двоичным включением*) for i:=2 to n do begin x:=a[i]; L:=l; R:^i; while L begin m:=(L+R) div 2; if a [m] <=x then L:=m+1 else R:=m; end; for j:=i downto R+l do a[j]:=a [j‑1]; a[R]:=x; end; (* вывод отсортированного массива*) for i: – l to N do begin write (a[i], ' '); end; readln; end. Сортировка Шелла Метод, предложенный Дональдом Л. Шеллом, является неустойчивой сортировкой по месту. Эффективность метода Шелла объясняется тем, что сдвигаемые элементы быстро попадают на нужные места. Среднее время для сортировки Шелла равняется O(n1.25), для худшего случая оценкой является O(n1.5). Дальнейшие ссылки см. в книге Кнута [4]. На рисунке 1.8 приведен пример сортировки вставками. Мы сначала вынимали 1, затем сдвигали 3 и 5 на одну позицию вниз, после чего вставляли 1. Таким образом, нам требовались два сдвига. В следующий раз нам требовалось два сдвига, чтобы вставить на нужное место 2. На весь процесс нам требовалось 2+2+1=5 сдвигов. На рисунке 1.9 иллюстрируется сортировка Шелла. Мы начинаем, производя сортировку вставками с шагом 2. Сначала мы рассматриваем числа 3 и 1: извлекаем 2, сдвигаем 3 на 1 позицию с шагом 2, вставляем 2. Затем повторяем то же для чисел 5 и 2: извлекаем 2, сдвигаем вниз 5, вставляем 2 и т. д. Закончив сортировку с шагом 2, производим ее с шагом 1, т. е. выполняем обычную сортировку вставками. Всего при этом нам понадобится 1 + 1+ 1 = 3 сдвига. Таким образом, использовав вначале шаг, больший 1, мы добились меньшего числа сдвигов. Рисунок 1.9 – Сортировка Шелла Можно использовать самые разные схемы выбора шагов. Как правило, сначала мы сортируем массив с большим шагом, затем уменьшаем шаг и повторяем сортировку. В самом конце сортируем с шагом 1. Хотя этот метод легко объяснить, его формальный анализ довольно труден. В частности, теоретикам не удалось найти оптимальную схему выбора шагов. Кнут провел множество экспериментов и следующую формулу выбора шагов (h) для массива длины N. Вот несколько первых значений h: Чтобы отсортировать массив длиной 100, прежде всего, найдем номер s, для которого hs 100. Согласно приведенным цифрам, s = 5. Нужное нам значение находится двумя строчками выше. Таким образом, последовательность шагов при сортировке будет такой: 13–4–1. Ну, конечно, нам не нужно хранить эту последовательность: очередное значение h находится из предыдущего. Сортировка с помощью дерева Улучшенный метод сортировки выбором с помощью дерева. Метод сортировки прямым выбором основан на поисках наименьшего элемента среди неготовой последовательности. Усилить метод можно запоминанием информации при сравнении пар элементов. Этого добиваются определением в каждой паре меньшего элемента за n/2 сравнений. Далее n/4 сравнений позволит выбрать меньший из пары уже выбранных меньших и т. д. Получается двоичное дерево сравнений после n‑1 сравнений, у которого в корневой вершине находится наименьший элемент, а любая вершина содержит меньший элемент из двух приходящих к ней вершин. Одним из алгоритмов, использующих структуру дерева, является сортировка с помощью пирамиды (Дж. Вильямс) [3]. Пирамида определяется как последовательность ключей hL…hR, такая, что hi<=h2i и hi<=h2i+l, для i=L,…, R/2. Другими словами, пирамиду можно определить как двоичное дерево заданной высоты h, обладающее тремя свойствами: • каждая конечная вершина имеет высоту h или h‑1; • каждая конечная вершина высоты h находится слева от любой конечной вершины высоты h‑1; • значение любой вершины больше значения любой следующей за ней вершины. Рассмотрим пример пирамиды, составленной по массиву 27 9 14 8 5 11 7 2 3. У пирамиды n=9 вершин, их значения можно разместить в массиве а, но таким образом, что следующие за вершиной из a[i] помещаются в a[2i] и a [2i+l]. Заметим, что а[6]=11, а[7]=7, а они следуют за элементом а[3]=14 (рисунок 1.10). Рисунок 1.10 – Пирамида Очевидно, что если 2i > n, тогда за вершиной a[i] не следуют другие вершины, и она является конечной вершиной пирамиды. Процесс построения пирамиды для заданного массива можно разбить на четыре этапа: 1) меняя местами а[1] и а[n], получаем 3 9 14 8 5 11 7 2 27; 2) уменьшаем n на 1, т. е. n=n‑1, что эквивалентно удалению вершины 27 из дерева; 3) преобразуем дерево в другую пирамиду перестановкой нового корня с большей из двух новых, непосредственно следующих за ним вершин, до тех пор, пока он не станет больше, чем обе вершины, непосредственно за ним следующие; 4) повторяем шаги 1, 2, 3 до тех пор, пока не получим n=1. Для алгоритма сортировки нужна процедура преобразования произвольного массива в пирамиду (шаг 3). В ней необходимо предусмотреть последовательный просмотр массива справа налево с проверкой одновременно двух условий: больше ли а[n], чем a[2i] и a [2i+l]. Полный текст программы приведен ниже. program sortirovka_5; (*улучшенная сортировка выбором – сортировка с помощью дерева*) const N=8; type item= integer; var a: array [1..n] of item; k, L, R: integer; x: item; procedure sift (L, R:integer); var i, j: integer; x, y: item; begin i:=L; j:=2*L; x:=a[L]; if (j while (j<=R) and (x a[j]:=y; a[i]:=a[j]; i:=j; j:=2*j; if (j end; end; begin (*задание искомого массива*) for k:=1 to N do begin write ('Bведите элемент a [', k, ']='); readln (a[k]); end; for k:=1 to N do begin write (a[k], ' '); end; writeln; (*алгоритм сортировки с помощью дерева*) (*построение пирамиды*) L:=(n div 2) +1; R:=n; while L>1 do begin L:=L‑1; SIFT (L, R); end; (*сортировка*) while R>1 do begin x:=a[l]; a[l]:=a[R]; a[R]:=x; R:=R‑1; SIET (1, R); end; (*вывод отсортированного массива*) for k:=1 to N do begin write (a[k], ' '); end; readln; end. Сортировка с помощью обменов 1‑ый вариант. Соседние элементы массива сравниваются и при необходимости меняются местами до тех пор, пока массив не будет полностью упорядочен. Повторные проходы массива сдвигают каждый раз наименьший элемент оставшейся части массива к левому его концу. Метод широко известен под названием «пузырьковая сортировка» потому, что большие элементы массива, подобно пузырькам, «всплывают» на соответствующую позицию. Основной фрагмент программы содержит два вложенных цикла, причём внутренний цикл удобнее выбрать с шагом, равным -1 [8]: for i: =2 to n do for j:=n downto i do if a [j‑1]>a[j] then begin {обмен}x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=xend; 2‑ой вариант. Пузырьковая сортировка является не самой эффективной, особенно для последовательностей, у которых «всплывающие» элементы находятся в крайней правой стороне. В улучшенной (быстрой) пузырьковой сортировке предлагается производить перестановки на большие расстояния, причем двигаться с двух сторон. Идея алгоритма заключается в сравнении элементов, из которых один берется слева (i = 1), другой – справа (j = n). Если a[i] <= a[j], то устанавливают j = j – 1 и проводят следующее сравнение. Далее уменьшают j до тех пор, пока a[i] > a[j]. В противном случае меняем их местами и устанавливаем i = i + 1. Увеличение i продолжаем до тех пор, пока не получим a[i] > a[j]. После следующего обмена опять уменьшаем j. Чередуя уменьшение j и увеличение i, продолжаем этот процесс с обоих концов до тех пор, пока не станет i = j. После этого этапа возникает ситуация, когда первый элемент занимает ему предназначенное место, слева от него младшие элементы, а справа – старшие [8]. Далее подобную процедуру можно применить к левой и правой частям массива и т. д. Очевидно, что характер алгоритма рекурсивный. Для запоминания ведущих левого и правого элементов в программе необходимо использовать стек. Характерной чертой алгоритмов сортировки с помощью обмена является обмен местами двух элементов массива после их сравнения друг с другом. В так называемой «пузырьковой сортировке» проводят несколько проходов по массиву, в каждом из которых повторяется одна и та же процедура: сравнение двух последовательно стоящих элементов и их обмен местами в порядке меньшинства (старшинства). Подобная процедура сдвигает наименьшие элементы к левому концу массива. program sortirovka_6; (*сортировка прямым обменом – пузырьковая сортировка*) const N=5; type item= integer; var a: array [1..n] of item; i, j: integer; x: item; begin (*задание искомого массива*) for i:=1 to N do begin write ('введи элемент a [', i, ']= '); readln (a[i]); end; for i:=1 to N do begin write (a[i], ' '); end; writeln; (*алгоритм пузырьковой сортировки*) for i:=2 to n do for j:=n downto i do begin if a [j‑1]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=x; end; end; (*вывод отсортированного массива*) for i:=1 to N do begin write (a[i], ' '); end; readln; end. Представленную программу можно легко улучшить, если учесть, что если после очередного прохода перестановок не было, то последовательность элементов уже упорядочена, т. е. продолжать проходы не имеет смысла. Если чередовать направление последовательных просмотров, алгоритм улучшается. Такой алгоритм называют «шейкерной» сортировкой. program sortirovka_7; (*сортировка прямым обменом – шейкерная сортировка*) const N=5; type item= integer; var a: array [1..n] of item; i, j, k, L, R: integer; x: item; begin (*задание искомого массива*) for i: =1 to N do begin write ('введи элемент а [', i, '] = '); readln (a[i]); end; for i:=1 to N do begin write (a[i], ' '); end; writeln; (*алгоритм шейкерной сортировки*) L: =2; R:=n; k:=n; repeat for j:=R downto L do begin if a [j-l]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=x; k:=-j end; end; L:=k+1; for j:=L to R do begin if a [j-l]>a[j] then begin x:=a [j-l] a [j-l]:=a[j]; a[j]:=x; k:=j end; end; R:=k‑1; until L>R; (*вывод отсортированного массива*) for i:=l to N do begin write (a[i], ' '); end; readln; end. Быстрая сортировка Хотя идея Шелла значительно улучшает сортировку вставками, резервы еще остаются. Один из наиболее известных алгоритмов сортировки – быстрая сортировка, предложенная Ч. Хоаром. Метод и в самом деле очень быстр, недаром по-английски его так и величают QuickSort [6]. Этому методу требуется O (n log2n) в среднем и O(n2) в худшем случае. К счастью, если принять адекватные предосторожности, наихудший случай крайне маловероятен. Быстрый поиск не является устойчивым. Кроме того, ему требуется стек, т. е. он не является и методом сортировки на месте. Алгоритм разбивает сортируемый массив на разделы, затем рекурсивно сортирует каждый раздел. В функции Partition один из элементов массива выбирается в качестве центрального. Ключи, меньшие центрального, следует расположить слева от него, те, которые больше – справа. int function Partition (Array A, int Lb, int Ub); begin select a pivot from A[Lb]… A[Ub]; reorder A[Lb]… A[Ub] such that: all values to the left of the pivot are pivot all values to the right of the pivot are pivot return pivot position; end; procedure QuickSort (Array A, int Lb, int Ub); begin if Lb < Ub then M = Partition (A, Lb, Ub); QuickSort (A, Lb, M – 1); QuickSort (A, M + 1, Ub); end; На рисунке 1.11 (а) в качестве центрального выбран элемент 3. Индексы начинают изменяться с концов массива. Индекс i начинается слева и используется для выбора элементов, которые больше центрального, индекс j начинается справа и используется для выбора элементов, которые меньше центрального. Эти элементы меняются местами – см. рисунок 1.11 (b). Процедура QuickSort рекурсивно сортирует два подмассива, в результате получается массив, представленный на рисунке 1.11 (c). В процессе сортировки может потребоваться передвинуть центральный элемент. Если нам повезет, выбранный элемент окажется медианой значений массива, т. е. разделит его пополам. Предположим на минутку, что это и в самом деле так. Поскольку на каждом шаге мы делим массив пополам, а функция Partition, в конце концов, просмотрит все n элементов, время работы алгоритма есть O (n log2n). В качестве центрального функция Partition может попросту брать первый элемент (A[Lb]). Все остальные элементы массива мы сравниваем с центральным и передвигаем либо влево от него, либо вправо. Есть, однако, один случай, который безжалостно разрушает эту прекрасную простоту. Предположим, что наш массив с самого начала отсортирован. Функция Partition всегда будет получать в качестве центрального минимальный элемент и потому разделит массив наихудшим способом: в левом разделе окажется один элемент, соответственно, в правом останется Ub – Lb элементов. Рисунок 1.11 – Пример работы алгоритма Quicksort Таким образом, каждый рекурсивный вызов процедуры quicksort всего лишь уменьшит длину сортируемого массива на 1. В результате для выполнения сортировки понадобится n рекурсивных вызовов, что приводит к времени работы алгоритма порядка O(n2). Один из способов побороть эту проблему – случайно выбирать центральный элемент. Это сделает наихудший случай чрезвычайно маловероятным. Сортировка с помощью прямого выбора При сортировке этим методом выбирается наименьший элемент массива и меняется местами с первым. Затем выбирается наименьший среди оставшихся n – 1 элементов и меняется местами со вторым и т. д. до тех пор, пока не останется один самый больший элемент. Основной фрагмент программы может выглядеть так [11]: for i:=l to n‑1 do begin k: =i; x:=a[i]; for j:=i+1 to n do if a[j] k – величина, хранящая индекс элемента, участвующего в операции обмена. Сортировка файлов Главная особенность методов сортировки последовательных файлов в том, что при их обработке в каждый момент непосредственно доступна одна компонента (на которую указывает указатель). Чаще процесс сортировки протекает не в оперативной памяти, как в случае с массивами, а с элементами на внешних носителях («винчестере», дискете и т. п.). Понять особенности сортировки последовательных файлов на внешних носителях позволит следующий пример [9]. Предположим, что нам необходимо упорядочить содержимое файла с последовательным доступом по какому-либо ключу. Для простоты изучения и анализа сортировки условимся, что файл формируем мы сами, используя, как и в предыдущем разделе, некоторый массив данных. Его же будем использовать и для просмотра содержимого файла после сортировки. В предлагаемом ниже алгоритме необходимо сформировать вспомогательный файл, который позволит осуществить следующую процедуру сортировки. Сначала выбираем из исходного файла первый элемент в качестве ведущего, затем извлекаем второй и сравниваем с ведущим. Если он оказался меньше, чем ведущий, то помещаем его во вспомогательный файл, в противном случае во вспомогательный файл помещается ведущий элемент, а его замещает второй элемент исходного файла. Первый проход заканчивается, когда аналогичная процедура коснется всех последовательных элементов исходного файла. Ведущий элемент заносится во вспомогательный файл последним. Теперь необходимо поменять местами исходный и вспомогательный файлы. После nil проходов в исходном файле данные будут размещены в упорядоченном виде. program sortirovka_faila_1; {сортировка последовательного файла} const n=8; type item= integer; var a: array [1..n] of item; i, k: integer; x, y: item; fl, f2: text; {file of item}; begin {задание искомого массива} for i:=1 to N do begin write ('введи элемент а ['i, '] = '); readln (a[i]); end; writeln; assign (fl, 'datl.dat'); rewrite(fl); assign (f2, 'dat2.dat'); rewrite(f2); {формирование последовательного файла} for i:=1 to N do begin writeln (fl, a[i]); end; {алгоритм сортировки с использованием вспомогательного файла} for k:=1 to (n div 2) do begin {извлечение из исходного файла и запись во вспомогательный} reset(fl); readln (fl, x); for i:=2 to n do begin readln (fl, y); if x>y then writeln (f2, y) else begin writeln (f2, x); x:=y; end; end; writeln (f2, x); {извлечение из вспомогательного файла и запись в исходный} rewrite(fl); reset(f2); readln (f2, x); for i:=2 to n do begin readln (f2, y); if x>y then writeln (fl, y) else begin writeln (fl, x); x:=y; end; end; writeln (fl, x); rewrite(f2); end; (вывод результата) reset(fl); for i:=1 to N do readln (fl, a[i]); for i:=1 to N do begin write (a[i], ' '); end; close(fl); close(f2); readln; end. По сути можно в программе обойтись без массива а [1..n]. В качестве упражнения попытайтесь создать программу, в которой не используются массивы. Многие методы сортировки последовательных файлов основаны на процедуре слияния, означающей объединение двух (или более) последовательностей в одну, упорядоченную с помощью повторяющегося выбора элементов (доступных в данный момент). В дальнейшем (чтобы не осуществлять многократного обращения к внешней памяти), будем рассматривать вместо файла массив данных, обращение к которому можно осуществлять строго последовательно. В этом смысле массив представляется как последовательность элементов, имеющая два конца, с которых можно считывать данные. При слиянии можно брать элементы с двух концов массива, что эквивалентно считыванию элементов из двух входных файлов. Идея слияния заключается в том, что исходная последовательность разбивается на две половины, которые сливаются вновь в одну упорядоченными парами, образованными двумя элементами, последовательно извлекаемыми из этих двух подпоследовательностей. Вновь повторяем деление и слияние, но упорядочивая пары, затем четверки и т. д. Для реализации подобного алгоритма необходимы два массива, которые поочередно (как и в предыдущем примере) меняются ролями в качестве исходного и вспомогательного. Если объединить эти два массива в один, разумеется, двойного размера, то программа упрощается. Пусть индексы i и j фиксируют два входных элемента с концов исходного массива, k и L – два выходных, соответствующих концам вспомогательного массива. Направлением пересылки (сменой ролей массивов) удобно управлять с помощью булевской переменной, которая меняет свое значение после каждого прохода, когда элементы a1…, an движутся на место ani….a2n и наоборот. Необходимо еще учесть изменяющийся на каждом проходе размер объединяемых упорядоченных групп элементов. Перед каждым последующим проходом размер удваивается. Если считать, что количество элементов в исходной последовательности не является степенью двойки (для процедуры разделения это существенно), то необходимо придумать стратегию разбиения на группы, размеры которых q и r могут не совпадать с ведущим размером очередного прохода. В окончательном виде алгоритм сортировки слиянием представлен ниже. program sortirovka__faila_2; {сортировка последовательного файла слиянием} const N=8; type item= integer; var a: array [1..2*n] of item; i, j, k, L, t, h, m, p, q, r: integer; f: boolean; begin {задание искомого массива} for i:=1 to N do begin write ('введи элемент а [', i, '] = '); readln (a[i]); end; writeln; {сортировка слиянием} f:=true; p:=1; repeat h:=1; m:=n; if f then begin i:=1; j:=n; k:=n+1; L:=2*n end else begin k:=1; L:=n; i:=n+1; j:=2*n end; repeat if m>=p then q:=p else q:=m; m:=m-q; if m>=p then r:=p else r:=m; m:=m-r; while (q0) and (r<>0) do begin if a[i} begin a[k]:=a[i]; k:=k+h; i:=i+1; q:=q‑1 end else begin a[k]:=a[j]; k:=k+h; j:=j‑1; r:=r‑1 end; end; while r>0 do begin a[k]:=a[j]; k:=k+h; j:=j‑1; r:=r‑1; end; while q>0 do begin a[k]:=a[i]; k: – k+h; i:=i+1; q:=q‑1; end; h:=-h; t:=k; k:=L; L:=t; until m=0; f:=not(f); p:=2*p; until p>=n; if not(f) then for i:=1 to n do a[i]:=a [i+n]; {вывод результата} for i:=1 to N do begin write (a[i], ' '); end; readln; end. Рассмотренные два предыдущих примера иллюстрируют большие проблемы сортировки внешних файлов, если в них часты изменения элементов, например, удаления, добавления, корректировки существующих. В подобных ситуациях эффективными становятся алгоритмы, в которых обрабатываемые элементы представляются в виде структур данных, удобных для поиска и сортировки. В качестве структур данных можно отметить, в частности, линейные списки, очереди, стеки, деревья и т. п. О них было рассказано в предыдущем разделе. 1.3 Практическая часть 1.3.1 Содержание отчёта по практической работе Задание по варианту. Теоретическая часть (краткое описание используемого метода и необходимые пояснения для понимания функционирования приложения на Delphi). Блок-схема для процедуры, реализующей основной алгоритм. Код программы. Результаты расчёта. Примечание: а) подбор исходных данных выполнить самостоятельно; б) если в варианте не указан метод, то выбрать наиболее подходящий для решения поставленной задачи (предварительно согласовать с преподавателем). 1.3.2 Приложение на Delphi, в котором представлена работа некоторых методов сортировки и поиска Графический интерфейс представлен на рисунке 1.14. Рисунок 1.14 – Форма uses wseme1; procedure TForm1. Button16Click (Sender: TObject); begin close; end; procedure TForm1. Button1Click (Sender: TObject); var i:integer; begin // генерируем множество, состоящее из случайных чисел Randomize; for i:=0 to StringGrid1. RowCount do StringGrid1. Cells [0, i]:=IntToStr (Random(10000)+1); end; procedure TForm1. FormCreate (Sender: TObject); begin Button1. Click(); end; procedure TForm1. Edit1Exit (Sender: TObject); begin // проверяем заполнено ли поле if edit1. Text='' then begin MessageDlg ('Введите число не больше 15', mtError, [mbOk, mbCancel], 0); exit; end else StringGrid1. RowCount:=strtoint (edit1. Text); StringGrid2. RowCount:=strtoint (edit1. Text); end; procedure TForm1. Button3Click (Sender: TObject); var n, minimum, j, i, obmen:integer; a:array [1..15] of integer; begin n:=strtoint (edit1. Text); // задание массива for j:=1 to n do a[j]:=StrToInt (StringGrid1. Cells [0, j‑1]); for j:=1 to n do begin // номер минимального элемента minimum:=j; for i:=j+1 to n do if a[i] < a [minimum] then minimum:=i; // запоминание минимального элемента obmen:=a[j]; a[j]:=a[minimum]; a[minimum]:=obmen; // вывод отсортированного массива for i:=0 to n do stringgrid2. Cells [0, j‑1]:=inttostr (a[j]); end; end; procedure TForm1. Button4Click (Sender: TObject); var n, obmen, i, j:integer; a:array [1..15] of integer; colicobmen:boolean; begin n:=strtoint (edit1. Text); // задание массива for i:=1 to n do a[i]:= StrToInt (StringGrid1. Cells [0, i‑1]); // сортировка массива repeat colicobmen:=FALSE; for j:=1 to n‑1 do if a[j] > a [j+1] then begin obmen:=a[j]; a[j]:=a [j+1]; a [j+1]:=obmen; colicobmen:=TRUE; end; // вывод массива for i:=1 to n do stringgrid2. Cells [0, i‑1]:=inttostr (a[i]); until not colicobmen; stringgrid2. Cells [0, i‑1]:=inttostr (a[i]); end; procedure TForm1. Button5Click (Sender: TObject); var a:array [1..15] of integer; i, j, m, L, R, n, x:integer; begin n:=strtoint (edit1. Text); // задание массива for i:=1 to n do a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]); // алгоритм сортировки двоичным включением for i:=2 to n do begin x:=a[i]; L:=1; R:=i; while L m:=(L+R) div 2; if a[m]<=x then L:=m+1 else R:=m; end; for j:=i downto R+1 do a[j]:=a [j‑1]; a[R]:=x; end; // вывод отсортированного массива for i:=1 to n do stringgrid2. Cells [0, i‑1]:=inttostr (a[i]); end; procedure TForm1. Button6Click (Sender: TObject); const t=15; var n:integer; a:array [1..15] of integer; i, j, k, s:integer; x:integer; m:1..t; h:array [1..t] of integer; begin n:=strtoint (edit1. Text); // задание массива for i:=1 to n do a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]); // алгоритм Шелла h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=1; for m:=1 to t do begin k:=h[m]; s:=-k; // барьеры для каждого шага for i:=k+1 to n do begin x:=a[i]; j:=i-k; if s=0 then s:=-k; s:=s+1; a[s]:=x; while x j:=j-k; end; a [j+k]:=x; end; end; // вывод отсортированного массива for i:=1 to n do stringgrid2. Cells [0, i‑1]:=inttostr (a[i]); end; procedure TForm1. Button7Click (Sender: TObject); var n:integer; a:array [1..15] of integer; L, R, x, k:integer; procedure sift (L, R:integer); var i, j:integer; x, y:integer; begin i:=L; j:=2*L; x:=a[L]; if (j while (j<=R) and (x a[i]:=a[j]; a[j]:=y; a[i]:=a[j]; i:=j; j:=2*j; if (j end; end; begin n:=strtoint (edit1. Text); // задание искомого массива for k:=1 to n do a[k]:=StrToInt (StringGrid1. Cells [0, k‑1]); // алгоритм сортировки с помощью дерева // построение пирамиды L:=(n div 2)+1; R:=n; while L>1 do begin L:=L‑1; SIFT (L, R); end; // сортировка while R>1 do begin x:=a[l]; a[l]:=a[R]; a[R]:=x; R:=R‑1; SIFT (1, R); end; // вывод отсортированного массива for k:=1 to n do stringgrid2. Cells [0, k‑1]:=inttostr (a[k]); end; procedure TForm1. Button8Click (Sender: TObject); var n:integer; a:array [1..15] of integer; i, j, x:integer; begin n:=strtoint (edit1. Text); // задание искомого массива for i:=1 to n do a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]); // алгоритм пузырьковой сортировки for i:=2 to n do for j:=n downto i do begin if a [j‑1]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=x; end; end; // вывод отсортированного массива for i:=1 to n do stringgrid2. Cells [0, i‑1]:=inttostr (a[i]); end; procedure TForm1. Button9Click (Sender: TObject); var n:integer; a:array [1..15] of integer; i, j, k, L, R, x: integer; begin n:=strtoint (edit1. Text); // задание искомого массива for i:=1 to n do a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]); // алгоритм шейкерной сортировки L:=2; R:=-n; k:=n; repeat for i:=2 to n do for j:=-R downto L do begin if a [j‑1]>a[j] then begin x:=a [j‑1]; a [j‑1]:=a[j]; a[j]:=x; k:=j; end; end; L:=k+1; for i:=2 to n do for j:=L to R do begin if a [j‑1]>a[j] then begin x:=a [j‑1] end else a [j‑1]:=a[j]; a[j]:=x; k:=-j; end; R:=k‑1; until L>R; // вывод отсортированного массива for i:=1 to n do stringgrid2. Cells [0, i‑1]:=inttostr (a[i]); end; procedure TForm1. Button10Click (Sender: TObject); var n:integer; a:array [1..15] of integer; i:integer; procedure sort (L, R: integer); var i, j:integer; x, y:integer; begin i:=L; j:=R; x:=a[(L+R) div 2]; repeat while a[i] while x if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; i:=i+l; j:=j-l; end; until i>j; if L if i end; begin n:=strtoint (edit1. Text); // задание искомого массива for i:=1 to n do a[i]:=StrToInt (StringGrid1. Cells [0, i‑1]); // алгоритм быстрой сортировки // рекурсивная процедура SORT (1, n); // вывод отсортированного массива for i:=1 to n do stringgrid2. Cells [0, i‑1]:=inttostr (a[i]); end; procedure TForm1. Button17Click (Sender: TObject); begin AboutBox.showmodal; end; end. 1.3.3 Пример выполнения Задание: заданы два одномерных массива А и В, содержащие по n элементов каждый. Объединить эти два массива в один, исключив повторяющиеся элементы. Считать, что массивы А и В отсортированы по убыванию. Теоретическое описание метода Метод пузырька, как таковой, не требует глубокого рассмотрения. Смысл метода заключается в том, что мы находим в определённой области максимальный (или минимальный элемент) и помещаем его в начало исследуемой области, далее уменьшаем область поиска на 1 и повторяем те же действия, не имеет худшего случая, всегда O(n2). Рисунок 1.15 – Форма с результатами расчета Код программы на Delphi: const n=5; var a:array [1..n] of Byte; b:array [1..n] of Byte; c: array of Byte; i:byte; implementation procedure TForm1. Button1Click (Sender: TObject); var m, x:byte; begin randomize; for i:=1 to n do begin a[i]:=random(200); b[i]:=random(200); end; for m:=n downto 2 do begin for i:=1 to m‑1 do begin Рисунок 2.4 – Диаграмма Венна разности А \ В Рисунок 2.5 – Диаграмма Венна дополнения Симметрической разностью двух множеств А и В называют множество А Δ В = {х: (х Оно состоит из всех тех и только тех элементов универсального множества, которые либо принадлежат А и не принадлежат В, либо наоборот, принадлежат В, но не А. Грубо говоря, симметрическая разность состоит из элементов, лежащих либо в А, либо в В, но не одновременно. Диаграмма Венна, иллюстрирующая симметрическую разность, начерчена на рисунке 2.6. Рисунок 2.6 – Диаграмма Венна симметрической разности А Δ В 2.1.2 Представление множеств и отношений в программах В этом параграфе рассматривается представление множеств в программах. Термин «представление» (еще употребляют термин «реализация») применительно к программированию означает следующее. Задать представление какого-либо объекта (в данном случае множества) – значит, описать в терминах используемой системы программирования структуру данных, используемую для хранения информации о представляемом объекте, и алгоритмы над выбранными структурами данных, которые реализуют присущие данному объекту операции. Предполагается, что в используемой системе программирования доступны такие общеупотребительные структуры данных, как массивы, структуры (или записи) и указатели. Таким образом, применительно к множествам определение представления подразумевает описание способа хранения информации о принадлежности элементов множеству и описание алгоритмов для вычисления объединения, пересечения и других введенных операций [5]. Следует подчеркнуть, что, как правило, один и тот же объект может быть представлен многими разными способами, причем нельзя указать способ, который является наилучшим для всех возможных случаев. В одних случаях выгодно использовать одно представление, а в других – другое. Выбор представления зависит от целого ряда факторов: особенностей представляемого объекта, состава и относительной частоты использования операций в конкретной задаче и т. д. Умение выбрать наиболее подходящее для данного случая представление является основой искусства практического программирования. Хороший программист отличается тем, что он знает много разных способов представления и умело выбирает наиболее подходящий. Множества и задачи информационного поиска Наиболее продуктивный подход к разработке эффективного алгоритма для решения любой задачи – изучить ее сущность. Довольно часто задачу можно сформулировать на языке теории множеств, относящейся к фундаментальным разделам математики. В этом случае алгоритм ее решения можно изложить в терминах основных операций над множествами. К таким задачам относятся и задачи информационного поиска, в которых решаются проблемы, связанные с линейно упорядоченными множествами [1]. Многие задачи, встречающиеся на практике, сводятся к одной или нескольким подзадачам, которые можно абстрактно сформулировать как последовательность основных команд, выполняемых на некоторой базе данных (универсальном множестве элементов). Например, выполнение последовательности команд, состоящих из операций поиск, вставка, удаление и минимум, составляет существенную часть задач поиска. Об этих и других подобных командах и пойдет речь ниже [12]. Рассмотрим несколько основных операций над множествами, типичных для задач информационного поиска. • Поиск (а; S) определяет, принадлежит ли элемент а множеству S; если а ответ «нет». • Вставка (а, S) добавляет элемент а в множество S, то есть заменяет S на S U {а}. • Алгоритм правильного обхода(S) печатает элементы множества S с соблюдением порядка. • Удаление (a, S) удаляет элемент а из множества S, то есть заменяет S на S \ {а}. • Объединение (S1, S2, S3) объединяет множества S1 и S2, т. е. строит множество S3 = S1 U S2. • Минимум (S) выдает наименьший элемент множества S. Следующая операция – операция минимум(S). Для нахождения наименьшего элемента в двоичном дереве поиска Т строится путь v0, vi, …, vp, где v0-корень дерева Т, vi – левый сын вершины vi-1 (i= 1,2,…, р), а у вершины vp левый сын отсутствует. Ключ вершины vp, и является наименьшим элементом в дереве Т. В некоторых задачах полезно иметь указатель на вершину vy, чтобы обеспечить доступ к наименьшему элементу за постоянное время. Алгоритм выполнения операции минимум(S) использует рекурсивную процедуру левый сын(v), определяющую левого сына вершины v. Алгоритм и процедура выглядят следующим образом. Input двоичное дерево поиска Т для множества S begin if T = 0 then output «дерево пусто»; else вызвать процедуру левый сын(r) (здесь r – корень дерева Т); минимум:=1 (v), где v – возврат процедуры левый сын; end Output ответ «дерево пусто», если Т не содержит вершин; минимум – наименьший элемент дерева Т в противном случае. Procedure левый сын (v). begin if v имеет левого сына w then return левый сын (w) else return v end Пример 2.1 Проследите работу алгоритма минимум на дереве поиска, изображенном на рисунке 2.7. Решение. Дерево Т не пусто, следовательно, вызывается процедура левый сын (1). Вершина 1 имеет левого сына – вершину 2, значит, вызывается процедура левый сын (2). Вершина 2 имеет левого сына вершину 4, значит, вызывается процедура левый сын (4). Вершина 4 не имеет левого сына, поэтому вершина 4 и будет возвратом процедуры левый сын. Ключом вершины 4 является слово begin, следовательно, наименьшим элементом дерева Т является значение минимум= begin. Рисунок 2.7 – Дерево поиска минимума S Реализовать операцию удаление (a, S) на основе бинарных поисковых деревьев тоже просто. Допустим, что элемент а, подлежащий удалению, расположен в вершине v. Возможны три случая: • вершина v является листом; в этом случае v просто удаляется из дерева; • у вершины v в точности один сын; в этом случае объявляем отца вершины v отцом сына вершины v, удаляя тем самым v из дерева (если v – корень, то его сына делаем новым корнем); • у вершины v два сына; в этом случае находим в левом поддереве вершины v наибольший элемент b, рекурсивно удаляем из этого поддерева вершину, содержащую b, и присваиваем вершине v ключ b. (Заметим, что среди элементов, меньших а, элемент b будет наибольшим элементом дерева. Кроме того, вершина, содержащая b, может быть или листом, являющимся чьим-то правым сыном, или иметь только левое поддерево.) Ясно, что до выполнения операции удаление (а, S) необходимо проверить, не является ли дерево пустым и содержится ли элемент а в множестве S. Для этого придется выполнить операцию поиск (а, S), причем, и в случае положительного ответа необходимо выдать кроме ответа «да» и номер вершины, ключ которой совпадает с a (далее ключ вершины v будем обозначать через l(v)). Кроме этого, для реализации операции удаление (a, S) требуется знать и номер вершины w, являющейся отцом вершины v. Саму же рекурсивную процедуру удаление (а, S) можно реализовать так, как показано ниже. Procedure удаление (а, S) begin if v – лист then удалить v из Т else (2) if v имеет только левого или только правого сына u then (3) if v имеет отца w then назначить и сыном w else сделать u корнем дерева, присвоив ему номер v else найти в левом поддереве v наибольший элемент b, содержащийся в вершине у; (6) return удаление (b, S); (7) l(v):=b; end Пример 2.2 Проследите за работой алгоритма удаление (а, S) для двоичного дерева поиска S, изображенного на рисунке 2.7, если a – это слово «if ». Решение. Слово «if » расположено в корне с номером 1, у которого два сына (вершины 2 и 3), поэтому выполняем строку (5) алгоритма. Наибольшее слово, меньшее «if » (лексикографически), расположенное в левом поддереве корня и находящееся в вершине 2, – это end. Вызываем процедуру удаление (end, S). Условие строки (2) алгоритма выполняется, так как вершина 2 с ключом end имеет только левого сына. Условие строки (3) не выполняется, так как удаляемая вершина является корнем. Поэтому переходим к строке (4): делаем вершину 2 корнем, сыновьями которого становятся вершины 4 (левым) и 3 (правым). Работа процедуры удаление (end, S) закончена. Продолжаем выполнение алгоритма (выполняем строку (7)): полагаем ключ вершины 1 равным «end » (l (I):=end). Полученное в результате дерево изображено на рисунке 2.8. Заметим, что при работе рассмотренных алгоритмов необходимо находить сыновей, отца и ключ заданной вершины двоичного дерева поиска. Это можно сделать довольно просто, если дерево в памяти компьютера хранится в виде трех массивов: LEFTSON, RIGHTSON и KEY. Эти массивы устроены следующим образом: LEFTSON (i) = v *, если у вершины i левого сына нет RIGHTSONM (i) = v *, если у вершины i правого сына нет key(i) = l(i) – ключ вершины i. Рисунок 2.8 – Результат работы алгоритма удаление (а, S) для двоичного дерева поиска S Например, бинарное поисковое дерево, изображенное на рисунке 2.7, может быть представлено в виде таблицы 2.1. Таблица 2.1 – Представление бинарного поискового дерева в виде таблицы I LEFTSON RIGHTSON KEY 1 2 3 if 2 4 * end 3 * 6 then 4 * 5 begin 5 * * else 6 * * while Правила поиска сыновей и ключа заданной вершины следуют из определения массивов. Определение отца заданной вершины состоит в нахождении строки массивов LEFTSON или RIGHTSON, в которой находится номер заданной вершины. Например, отцом вершины 4 является вершина 2, так как число 4 находится во второй строке массива LEFTSON. Объединение множеств Обратимся теперь к объединению множеств, то есть к операции объединение (S1, S2, S3). Если множества S1 и S2 линейно упорядочены, то естественно требовать такого порядка и от их объединения. Один из возможных способов объединения состоит в последовательном выполнении описанной выше операции вставка для добавления каждого элемента одного множества в другое. При этом, очевидно, операцию вставка предпочтительнее выполнять над элементами меньшего множества с целью сокращения времени на объединение. Отметим, что такой способ работы подходит как для непересекающихся, так и для пересекающихся множеств. Во многих задачах объединяются непересекающиеся множества. Это упрощает процесс, так как исчезает необходимость каждый раз проверять, содержится ли добавляемый элемент в множестве, либо удалять повторяющиеся экземпляры одного и того же элемента из S3. Процедура объединения непересекающихся множеств применяется, например, при построении минимального остовного дерева в данном нагруженном графе. Рассмотрим алгоритм объединения непересекающихся множеств на основе списков. Будем считать, что элементы объединяемых множеств пронумерованы натуральными числами 1,2,…. n. Кроме того, предположим, что имена множеств – также натуральные числа. Это не ограничивает общности, поскольку имена множеств можно просто пронумеровать натуральными числами. Представим рассматриваемые множества в виде совокупности линейных связанных списков. Такую структуру данных можно организовать следующим образом. Сформируем два массива R и next размерности n, в которых R(i) – имя множества, содержащего элемент i, a next(i) указывает номер следующего элемента массива R, принадлежащего тому же множеству, что и элемент i. Если i – последний элемент какого-то множества, то положим next(i) = 0. Для указателей на первые элементы каждого множества будем использовать массив list, число элементов которого равно числу рассматриваемых в задаче множеств, и элемент которого list(j) содержит номер первого элемента множества с именем j в массиве R. Кроме того, сформируем массив size, каждый элемент которого size(j) содержит количество элементов множества с именем j. Будем различать внутренние имена множеств, содержащиеся в массиве к, и внешние имена, получаемые множествами в результате выполнения операции объединение. Соответствие между внутренними и внешними именами множеств можно установить с помощью массивов Ехт-NAME и INT-NAME. Элемент массива EXT-NAME(j) содержит внешнее имя множества, внутреннее имя которого есть j, а INT-NAME(k) – внутреннее имя множества, внешнее имя которого есть к. Пример 2.3 Используя только что определенные массивы, опишите множества {1,3,5,7}, {2,4.8}, {6} с внешними именами 1, 2, 3 и внутренними именами 2, 3, 1 соответственно. Решение. Прежде всего, отметим, что общее количество элементов всех множеств равно восьми. Поэтому размерность массивов R и next будет n = 8. Кроме того, напомним, что номера элементов массивов list, SIZE, Ехт-NAME и значения элементов массива R – это внутренние имена множеств, а массива INT-NAME внешние. Алгоритм выполнения операции объединение (S1, S2, S3) состоит в добавлении к списку элементов большего из множеств S1 и S2 элементов меньшего множества и присвоение полученному множеству внешнего имени S3. При этом вычисляется также размер построенного множества S3. Объединение (i, j, к) Input i, j – внешние имена объединяемых множеств (пусть размер i меньше размера j); массивы R, NEXT, LIST, SIZE, ЕХТ-NAME, INT-NAME; begin A:=INT-NAME(i); B:=INT-NAME(j); element:=LIST(A); while element <> 0 do begin R(element):=B; last:=element; element:=NEXT(element) end NEXT(last):=LIST(B); LIST(B):=LIST(A); SIZE(B):=SIZE(B) + SIZE(A); INT-NAME(K):=B; EXT-NAME(B):=k End Объединение множеств i, j с внешним именем k. В процессе работы алгоритм совершает следующие действия: 1) определяет внутренние имена множеств i и j; 2) определяет начало списка элементов меньшего множества; 3) просматривает список элементов меньшего множества и изменяет соответствующие элементы массива R на внутреннее имя большего множества; 4) объединяет множества путем подстановки меньшего множества перед большим; 5) присваивает новому множеству внешнее имя k. Заметим, что время выполнения операции объединения двух множеств с помощью рассмотренного алгоритма пропорционально мощности меньшего множества. 2.1.3 Алгоритмы генерации множеств Реализация операций над подмножествами заданного универсума U Пусть универсум U – конечный, и число элементов в нем не превосходит разрядности ЭВМ: мощность |U| < n. Элементы универсума нумеруются: U = {u1,…, un}. Подмножество А универсума U представляется кодом (машинным словом или битовой шкалой) С, в котором: где С(i) – это i‑й разряд кода С. Код пересечения множеств А и В есть поразрядное логическое произведение кода множества А и кода множества В. Код объединения множеств А и В есть поразрядная логическая сумма кода множества А и кода множества В. Код дополнения множества А есть инверсия кода множества А. В большинстве ЭВМ для этих операций есть соответствующие машинные команды. Таким образом, операции над небольшими множествами выполняются весьма эффективно. Если мощность универсума превосходит размер машинного слова, но не очень велика, то для представления множеств используются массивы битовых шкал. В этом случае операции над множествами реализуются с помощью циклов по элементам массива [23]. Генерация всех подмножеств универсума Во многих переборных алгоритмах требуется последовательно рассмотреть все подмножества заданного множества. В большинстве компьютеров целые числа представляются кодами в двоичной системе счисления, причем число 2k – 1 представляется кодом, содержащим k единиц. Таким образом, число 0 является представлением пустого множества 0, число 1 является представлением подмножества, состоящего из первого элемента, и т. д. Следующий тривиальный алгоритм перечисляет все подмножества n‑элементного множества (представлен в паскале-подобном коде, описание в [23]). Алгоритм 1.1: Алгоритм генерации всех подмножеств n‑элементного множества Вход: n Выход: последовательность кодов подмножеств i for i from 0 to 2n – 1 do yield i end for Обоснование: Алгоритм выдает 2n различных целых чисел, следовательно, 2n различных кодов. С увеличением числа n увеличивается количество двоичных разрядов, необходимых для его представления. Самое большое (из генерируемых) число 2n‑1 требует для своего представления ровно n разрядов. Таким образом, все подмножества генерируются, причем ровно по одному разу. Во многих переборных задачах требуется рассмотреть все подмножества некоторого множества и найти среди них то, которое удовлетворяет заданному условию. При этом проверка условия часто может быть весьма трудоемкой и зависеть от состава элементов очередного рассматриваемого подмножества. В частности, если очередное рассматриваемое подмножество незначительно отличается по набору элементов от предыдущего, то иногда можно воспользоваться результатами оценки элементов, которые рассматривались на предыдущем шаге перебора. В таком случае, если перебирать множества в определенном порядке, можно значительно ускорить работу переборного алгоритма. [5] Алгоритм построения бинарного кода Грея Данный алгоритм генерирует последовательность всех подмножеств n‑элементного множества, причем каждое следующее подмножество получается из предыдущего удалением или добавлением одного элемента. Алгоритм 1.2: Алгоритм построения бинарного кода Грея Вход: n Выход: последовательность кодов подмножеств В В: array [l..n] of 0..1 {битовая шкала для представления подмножеств} for i from 1 to n do B[i]: = 0 {инициализация} end for yield В {пустое множество} for i from I to 2n – 1 do p: = Q(i) {определение элемента, подлежащего добавлению или удалению} B[р]: = 1 – В[р] {добавление или удаление элемента} yield В {очередное подмножество} end for proc Q(i) {количество 2 в разложении i на множители + 1} q: = l; j: = i while j четно do j:=j/2; q: = q + l end while return q end proc Обоснование Для n = 1 искомая последовательность кодов суть 0,1. Пусть есть искомая последовательность кодов В1,…, Пример 2.4 Таблица 2.5 – Протокол выполнения алгоритма 1.2 для п = 3 i Р В 0 0 0 1 1 0 0 1 2 2 0 1 1 3 1 0 1 0 4 3 1 1 0 5 1 1 1 1 6 2 1 0 1 7 1 1 0 0 Представление множеств упорядоченными списками Если универсум очень велик (или бесконечен), а рассматриваемые подмножества универсума не очень велики, то представление с помощью битовых шкал не является эффективным с точки зрения экономии памяти. В этом случае множества обычно представляются списками элементов. Элемент списка при этом представляется записью с двумя полями: информационным и указателем на следующий элемент. Весь список представляется указателем на первый элемент. elem = record i: info; {информационное поле} n: elem {указатель на следующий элемент} end record При таком представлении трудоемкость операции Если элементы в списках упорядочить, например, по возрастанию значения поля i, то трудоемкость всех операций составит О(n). Эффективная реализация операций над множествами, представленными в виде упорядоченных списков, основана на весьма общем алгоритме, известном как алгоритм типа слияния. 1 1 1 1 2 1 13 3 1 14 6 4 1 Рисунок 2.9 – Иллюстрация к алгоритму слияния В этом равнобедренном треугольнике каждое число (кроме единиц на боковых сторонах) является суммой двух чисел, стоящих над ним. Число сочетаний С (m, n) находится в (m + 1) – м ряду на (n + 1) – м месте. Генерация подмножеств Элементы множества {1,…, m} упорядочены. Поэтому каждое n‑элементное подмножество также можно рассматривать как упорядоченную последовательность. На множестве таких последовательностей естественным образом определяется лексикографический порядок. Следующий простой алгоритм генерирует все n‑элементные подмножества m‑элементного множества в лексикографическом порядке. Алгоритм 1.3. Генерация n‑элементных подмножеств m‑элементного множества Вход: n – мощность подмножества, m – мощность множества, m Выход: последовательность всех n‑элементных подмножеств m‑элементного множества в лексикографическом порядке. for i from 1 to m do A[i]: = i {инициализация исходного множества} end for if m = n then yield A [1..n] {единственное подмножество} exit end if p: = n {p – номер первого изменяемого элемента} while p yield A [1..n] {очередное подмножество в первых n элементах массива А} if А[i] = m then р: = р – 1 {нельзя увеличить последний элемент} else р:=n {можно увеличить последний элемент} end if if p for i from n downto p do А[i]: = А[р]+i‑р+1 {увеличение элементов} end for end if end while Заметим, что в искомой последовательности n‑элементиых подмножеств (каждое из которых является возрастающей последовательностью n чисел из диапазона l..m) вслед за последовательностью (ai,…, an) следует последовательность (b1,…, bn) = (а1…, ap-1, ар + 1, ар + 2,…, ар + n-р +1), где р – максимальный индекс, для которого bn = ар + n - р + 1 2.1.4 Представление множеств в приложениях на Delphi Тип множество задает неупорядоченную совокупность неповторяющихся объектов. Переменная типа множество – это совокупность объектов из исходного заданного множества – может иметь значение «пусто» (пустое множество). Число элементов исходного множества ограничено – оно не может быть более 256. Для задания элементов множества может использоваться любой порядковый тип, однако порядковые номера элементов множества, т. е. значения функции ord, должны находиться в пределах от 0 до 255. Для задания типа множества используется следующее объявление [22]: Type = set of ; При задании типа элементов необходимо соблюдать ограничения, указанные выше. Type A = set of Char; A1 = set of ‘A’.’Z’; Oper = set of (Plus, Minus, Mult, Divide); Number = set of Byte; D = set of 1..20; Для переменных типа множество можно задавать типизированные константы. При этом значения задаются в виде конструктора множества. Const K:D = [5,9,11,17]; R:D = [1.. 9,13,20]; Для задания значений переменным типа множество также можно использовать конструкторы. Пусть объявлено Var AA:A;, тогда возможна запись (тип A объявлен выше) AA:=[Char(13), Char(7), ‘0’, ‘Q’]; Если требуется присвоить этой переменной значение «пусто», то используется такой конструктор: AA:= []; Операции над множествами Как и для других типов, имеется ряд встроенных операций для типа множество. Пусть заданы следующие типы и переменные: Type Mn = set of 1..50; Var A, B, C: Mn; Пусть переменным присвоены значения: A:= [3,5,9,10]; B:= [1,7,9,10]; Объединение множеств C:=A+B; {1,3,5,7,9,10} Разность (A-B <> B-A) C:=A-B; {3,5} C:=B-A; {1,7} Пересечение (умножение) C:=A*B; {9,10} Проверка эквивалентности, например в операторе IF (A = B) {False} Проверка неэквивалентности (A <> B) {True} Проверка, является ли одно множество подмножеством другого (A>=B) {False} (A<=B) {False} Проверка, входит ли заданный элемент в заданное множество (3 in A) {True} (3 in B) {False} Стандартные подпрограммы для выполнения некоторых действий над множествами Exclude (A, 3); удалить из множества A элемент 3} Include (A, 3); {вставить элемент 3 в множество A}. 2.1.5 Характеристический вектор множества Характеристическим вектором Vx множества X, заданного на универсальном множестве I, является вектор, содержащий 0 и 1. Количество элементов в векторе Vx равно количеству элементов в универсальном множестве, причём, 1 записывается в случае, если элемент присутствует и в универсальном множестве I, и в множестве X, в противном случае записывается 0. Некоторые задачи с множествами, особенно на компьютере, удобно решать, используя характеристические векторы [1]. Действия над векторами похожи на логические операции. Над характеристическими векторами выполняются поразрядно логические операции: при пересечении – логическое умножение; при объединении – логическое сложение; при нахождении дополнения – значения в исходном векторе изменяются на противоположные. При объединении множеств 2) При пересечении множеств 3) При нахождении дополнения 4) При нахождении симметричной разности Пример 2.5 Пусть I = {1, 2, 3, 4, 5, 6}, А={1, 2, 4, 5} и В={3, 5} Характеристическим вектором множества А является вектор а = (1, 1, 0, 1, 1, 0). Характеристический вектор множества В равен b = (0, 0, 1, 0, 1, 0). Вычислим характеристический вектор множества A U а или (не b) = (1, 1, 0, 1, 1, 0) или (1, 1, 0 1, 0, 1) = (1,1,0,1,1,1). Следовательно, A U Характеристический вектор множества А Δ В равен (а и (не b)) или (b и (не а)) = ((1, 1, 0, 1, 1, 0) и (1, 1, 0, 1, 0, 1)) или или ((0, 0, 1, 0, 1, 0) и (0, 0, 1, 0, 0, 1)) = (1, 1, 0, 1, 0, 0) или (0, 0, 1, 0, 0, 0) = (1, 1, 1, 1, 0, 0). Таким образом, А Δ В = {1, 2, 3, 4}. 2.2 Практическая часть 2.2.1 Задание к работе 1. Изучить теоретический материал, включая и дополнительные сведения, представленные в теоретической части. 2. Задать самостоятельно универсальное множество X, множества A, B, C (или некоторые из них, т. к. в некоторых вариантах используются только два множества). 3. Cформировать характеристические векторы для исходных множеств и получить результирующее множество (по варианту), используя характеристические вектора. 4. Вычислить элементы результирующего множества (по варианту), используя операции над множествами. 5. Вывести результаты, полученные в пункте 3 и пункте 4. 6. Сравнить эти результаты и сделать выводы. 7. Пункты 3 и 4 выполнить двумя способами: аналитически и реализовать в виде приложения на Delphi. Примечание: 1. Если в выражении используется операция разности или симметрической разности, то при выполнении действий с характеристическими векторами (пункт 3) заменить их другими операциями на множествах (использовать формулы из лекций и [23]). 2. При выполнении пункта 4 операцию симметрической разности заменить другими операциями, которые используются в Object Pascal. 3. В качестве дополнительного задания предлагается реализовать любой описанный в теоретической части алгоритм в виде приложения на Delphi. 2.2.2 Примеры выполнения Пример 1. 1) Задание по варианту I:={1,2,3,4,5,6,7} Значения векторов A, B, C берутся произвольно, но с учетом, что количество элементов не должно быть больше 7. Найти: характеристический вектор множеств A, B и C, характеристический вектор множества D – Vd, перейти от Vd к D. 2) Создать приложение в среде Delphi, которое решит данную задачу. 3) Решить задачу аналитически. 4) К защите данной работы необходимо знать теоретический материал по данной теме из лекций и методички, а также ответить на «Вопросы для самопроверки». D= Аналитическое решение: Характеристические векторы A:={1,0,1,0,1,0,1} B:={1,1,1,1,0,0,0} C:={1,0,1,1,1,0,1} Переходим от D:= Форма Рисунок 2.10 – Формы с результатами Код программы implementation procedure TForm1. Button1Click (Sender: TObject); var n, A, B, C: set of char; s, s1, s2, s3, s11, s22, s33, s4, s44, s5, s55:string; i:integer; begin s:='1234567'; n:=['1'..'7']; A:=['1', '3', '5', '7']; B:=['1', '2', '3', '4']; C:=['1', '3', '4', '5', '7']; begin for i:=1 to 7 do begin if (s[i] in A) then s1:=s1+'1' else s1:=s1+'0'; end; s11:=' {'+s1+'}'; label7. Caption:=s11; end; begin for i:=1 to 7 do begin if (s[i] in B) then s2:=s2+'1' else s2:=s2+'0'; end; s22:=' {'+s2+'}'; label12. Caption:=s22; end; begin for i:=1 to 7 do begin if (s[i] in C) then s3:=s3+'1' else s3:=s3+'0'; end; s33:=' {'+s3+'}'; label13. Caption:=s33; {Задаем характеристические векторы} end; begin for i:=1 to 7 do if((s1 [i])=(s2 [i])) and ((s3 [i])=(s2 [i])) and ((s3 [i])='1') then s4:=s4+'1' else s4:=s4+'0'; s44:=' {'+s4+'}'; label17. Caption:=s44; {Находим Характеристический вектор множества Vd} end; begin for i:=1 to 7 do if s4 [i]='1' then s5:=s5+inttostr(i); s55:=' {'+s5+'}'; label21. Caption:=s55; {Переходим от Vd к D} end; end; procedure TForm1. Button2Click (Sender: TObject); begin close; end; end. 2.2.3 Варианты заданий 1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19) 20) 21) 22) 23) 24) 25) 26) 27) 28) 29) 30) 31) 32) 33) 34) 35) 36) 37) 38) 39) 40) 41) 42) 43) 44) 45) 46) 47) 47) 49) 50) 2.3 Вопросы для самопроверки 1) Какие основные символы, используемые в теории множеств, вы знаете? 2) Перечислите основные операции над множествами и функции, применимые к множествам, которые используются в Delphi. 3) Что такое множество? Как его обозначить? Как можно задать множество? 4) Какое множество называют счетным? Какое – пустым? 5) Что такое подмножество? 6) Сформулируйте основные свойства счетных множеств. 7) Определите понятие вектора, булеана. 8) Сформулируйте основные аксиомы теории множеств. 9) Какие соотношения (действия) между множествами вы знаете, как они обозначаются? 10) Какое множество можно назвать универсальным? 11) Какие операции (из аналогичных арифметическим) нельзя производить с множествами? 12) Что такое диаграмма Эйлера-Венна? Проиллюстрируйте с помощью диаграмм Эйлера-Венна объединение и пересечение трех множеств. 13) Дайте определение декартова произведения множеств; какие теоремы о декартовом произведении Вы знаете? 14) Поясните термин «мощность множества». 15) Сформулируйте (и докажите) основные тождества алгебры множеств. 16) Дайте определение проекции вектора. 17) Что понимается под соответствием между множествами? 18) Дайте определение функции с точки зрения теории множеств. Приведите пример. 19) Дайте определение бинарного отношения, перечислите свойства. 20) Какие отношения называют рефлексивными, транзитивными? 21) Что такое «класс эквивалентности»? 22) Для чего нужна диаграмма Хассе? 23) Дайте определение нечёткого множества. 24) Какие операции допустимы над нечёткими множествами? 25) Дайте определение расстояний Хемминга и его основных свойств. 26) Перечислите основные алгоритмы генерации множеств. Практическая работа № 3. Элементы теории графов Цель работы: изучение математических структур для представления графов, изучение наиболее известных алгоритмов на графах и построение приложений на Delphi для описания графов в виде математических структур, реализации некоторых алгоритмов на графах. 3.1 Теоретическая часть В данном параграфе многие определения и рисунки взяты из [17] и [19], являются дополнительными сведениями для материала, рассматриваемого в [24]. Пусть V – конечное множество (множество вершин), А – множество упорядоченных пар вершин, элементы которого называются ребрами. Тогда графом G (V, A) называется совокупность множества вершин и множества ребер. Вершины а и с соединяются ребром, если (а, с)А. Пусть дано множество вершин V и декартово произведение VхV – множество всевозможных пар вершин. Тогда графом G является подмножество декартового произведения. Ребро графа G ориентировано, если порядок пары (a, b) существенен. Ребро графа G не ориентировано, если порядок пары (a, b) несущественен. Рисунок 3.1 – Ориентированный граф Граф называется ориентированным, если все его ребра ориентированы. Граф G называется неориентированным, если все его ребра неориентированы. Смешанным графом называется граф, у которого есть как ориентированные, так и неориентированные ребра. Каждому ребру E=a, b можно поставить в соответствие некоторое число. Граф G, каждому ребру которого присвоено число (например, расстояние) называется сетью. Пусть даны a, b – вершины графа. Ребро E их соединяет. Тогда говорят, что ребро E инцидентно вершинам a и b. И обратно – вершины a и b инцидентны ребру E. При изображении графа имеется большая свобода в размещении вершин и дуг. Рисунок 3.2 – Три изображения одного и того же графа Пусть G и G1 графы, V и V1 – множества их вершин соответственно. Графы G и G1 изоморфны, если существует взаимнооднозначное соответствие между множествами их вершин V и V1 и вершины в графе G соединены ребром в том и только том случае, если соответствующие вершины соединены ребром в графе G1. Если графы G и G1 ориентированы, то направления ребер должны соответствовать друг другу. Изоморфные графы имеют одинаковые свойства. Вершина, не инцидентная никакому ребру, называется изолированной. Граф, состоящий из изолированных вершин, называется нуль граф. Обозначается через О. Граф, любые две вершины которого соединены ребром, называется полным графом U=U(V). Петлей называется ребро L=(a, a). Петля считается неориентированным ребром. Рисунок 3.3 – Петля Пара вершин может соединяться несколькими различными ребрами. Пара ребер Ei Ej, ориентированная в противоположном направлении, эквивалентна одному неориентированному ребру. Таким образом, мы можем любой неориентированный граф превратить в ориентированный. При этом количество ребер увеличивается в 2 раза. Граф называется плоским, если может быть изображен на плоскости так, чтобы его ребра пересекались только в вершинах. Граф назовем однородным степени k, если локальные степени во всех его вершинах равны k, т. е. Рисунок 3.4 – Бесконечный однородный граф Рисунок 3.5 – Конечный однородный граф Граф H называется частью графа G, если подмножество вершин его V(H) содержится во множестве вершин V(G) и все ребра части графа H являются ребрами G и обозначается HG. Для любой части H графа G существует дополнение V2 V3 Рисунок 3.6 – Граф G Рисунок 3.7 – Часть графа G Пусть H1 и H2 – две части графа G. Сумма этих частей H1UH2 есть часть, состоящая из ребер, принадлежащих H1 или H2. Пересечение D=H1 Бинарные отношения и графы Бинарные отношения можно изобразить графом: вершины графа – элементы множества V, ребра графа соединяют вершины, которые находятся в отношении друг к другу. Любой граф определяет бинарное отношение R на множестве вершин V, если для каждого ребра (a, b) выполняется aRb. Нельзя говорить о взаимнооднозначном соответствии между графами и бинарными отношениями. Пустому бинарному отношению соответствует нуль-граф О. Универсальному бинарному отношению отвечает полный граф U. Бинарному отношению aRb, где R – отрицание R (дополнительное бинарное отношение) отвечает граф G(R)=U(V) – G(R). Обратному бинарному отношению bR*a отвечает обратный граф G (R*), т. е. граф с измененной ориентацией ребер. Операции, которые вводятся для бинарных отношений, могут быть перенесены на графы. Симметричное бинарное отношение: если aRb, то bRa. Рефлексивность: бинарное отношение aRa соответствует графу с петлей в каждой вершине. Транзитивность: если aRb и bRc, то aRc. Для графа это означает, что если существует ребро (a, b) и ребро (b, c), то существует ребро (a, c). Такой граф называется связным. Свойство связности можно рассмотреть как бинарное отношение, которое: а) рефлексивно: вершина а связана сама с собой; б) симметрично: если вершина а связана с вершиной b, то и вершина b связана с вершиной a; в) транзитивно: если вершина a связана с вершиной b, и b связана с вершиной с, то вершина a связана с вершиной c. Отношение связности есть отношение эквивалентности, т. е. оно разбивает множество вершин на попарно непересекающиеся классы. Так как каждое множество Vi – множество связанных вершин, а вершины из разных множеств Vi не связаны, то имеем разложение графа G на части, которые не пересекаются и каждая часть – связная. Подграфы G(Vi) называются связными компонентами графа G. Каждый неориентированный граф распадается единственным образом в прямую сумму всех своих связных компонент. Покрывающие деревья Граф, не содержащий циклов, называется ациклическим. Деревом называется связный граф, не содержащий циклов. Пусть VG – число элементов в множестве вершин, VL – число элементов множества ребер дерева. Рисунок 3.8 – Дерево VG =VL‑1 Добавим ребро – появляется цикл, удалим ребро – теряется связность. Лесом называется несвязный граф, компонентами которого являются деревья. Пусть VLl – число элементов в множестве ребер леса, VGl – число элементов в множестве вершин леса, k – число деревьев в лесе. VLl = VGl - k Если дерево Т имеет корень, то дерево называется деревом с корнем. Выделим в дереве Т некоторую цепь. Рисунок 3.9 – Дерево Задача. Как узнать, существуют ли циклы в графе? Для дерева связь между числом ребер и числом вершин такова Vl=VG‑1. Рассмотрим = Vl-VG+1, называется цикломатическим числом. Если граф G – дерево, то =0, если не равно нулю, то в графе G есть циклы. Алгоритм построения произвольного покрывающего дерева [20] Ограничения: в графе не должно быть петель. Букетом называется произвольное дерево в графе. Шаг 1. Выбираем произвольное ребро и помечаем его х (красим в голубой цвет). Шаг 2. Выбираем другое произвольное непомеченное ребро. Если оба конца ребра лежат в одном букете, красим ребро в красный цвет. В противном случае – в голубой. Шаг 3. Если все вершины графа вошли в один букет, то процедура заканчивается, т. к. помеченные голубым ребра образуют покрывающее дерево. В противном случае – перейти к шагу 2. Рисунок 3.10 – Граф 1 шаг: (a, d) – помечаем голубым 2 шаг: (b, e) – помечаем голубым 3 шаг: (d, e) – помечаем голубым 4 шаг: (a, b) – помечаем красным 5 шаг: (a, c) – получаем голубым Рисунок 3.11 – Дерево Алгоритм построения минимального и максимального покрывающего дерева [21] Пусть каждому ребру графа G присвоена длина (вес) l (x, y) (таблица 3.1). Весом дерева называется сумма весов ребер, входящих в дерево. Минимальным деревом называется дерево с минимальным весом. Алгоритм формируется так же, как и алгоритм построения произвольного покрывающего дерева. Но ребра просматриваются в порядке возрастания их веса. Таблица 3.1 – Веса ребер графа A b c d e a 0 5 50 85 90 b 5 0 70 60 50 c 50 70 0 8 20 d 85 60 8 0 10 e 90 50 20 10 0 Порядок просмотра (a, b) – 5 (b, e) – 50 упорядочим ребра по возрастанию (c, d) – 8 (b, d) – 60 (d, e) – 10 (b, c) – 70 (c, e) – 20 (a, d) – 85 (a, c) – 50 (a, b) – 90 1 шаг: (a, b) – помечаем голубым 2 шаг: (c, d) – помечаем голубым 3 шаг: (d, e) – помечаем голубым 4 шаг: (c, e) – помечаем красным 5 шаг: (a, c) – помечаем голубым Дерево построено! Рисунок 3.12 – Дерево Алгоритм построения максимального ориентированного дерева(алгоритм Эдмонса) [15]: Шаг 1. Последовательно в произвольном порядке просматриваем вершины графа G0. Просмотр вершины заключается в том, чтобы из дуг, заходящих в эту вершину, выбрать дугу с максимальным весом. При просмотре следующих вершин к уже отобранным ранее дугам добавляются новые дуги. Если добавление ребра не нарушает свойства букета, то добавление ребер продолжается. Если новое ребро образует контур, перейти к шагу 2. Шаг 2. В случае формирования контура строится уменьшенный граф путем стягивания дуг и вершин выявленного контура исходного графа Go в одну вершину V. В новом графе веса ребер (xi, vi) полагаются равными l (x, vi)=l (x, y)+l (r, s) – l (t, y), где К – контур, а у – вершина, принадлежащая контуру. l (x, vi) – ребро, переходящее в ребро l (x, vi) l (r, s) – ребро, имеющее в контуре минимальный вес l (t, y) – ребро, заходящее в вершину у и имеющее максимальный вес Шаг 3. Выполняется тогда, когда вершины нового графа попадают в букет, а дуги образуют дерево. Возможны 2 случая: вершина Vo является корнем дерева, тогда необходимо рассмотреть ребра букета в новом графе совместно с ребрами контура. Удалить из рассматриваемого множества ребер ребро с минимальным весом; если Vo не является корнем дерева – в букете нового графа имеется лишь одно ребро, заходящее в некоторую вершину Z и одно ребро контура, заходящее в ту же вершину. Удаляем ребро контура, заходящее в вершину Z. Пример. Рисунок 3.13 – Граф Просмотр вершин: Букет получаемых ребер a (da) b (da) (cb) c (da) (cb) (ac) d (da) (cb) (ac) (bd) Ребра (ac) (cb) (bd) (da) образуют контур. Минимальный вес ребра в контуре 2. Стягиваем контур в одну вершину и рассматриваем граф: Рисунок 3.14 – Граф l(fe)=1 l (e, Vo)=l(ea)+2–3=3+2–3=2 l (f, Vo)=l (f, a)+2–3=-1 l (f, Vo) 1=l(fd)+2‑l (b, d)=1+2–2=1 Просмотр вершин Букет ребер e (fe) f (fe) Vo (fe) (eVo) Получили множество ребер исходного графа Go такое: (fe) (ea) – образуют букет (ac) (cb) (bd) (da) – образуют контур Vo не является контуром дерева, удаляем (da), поскольку (da) – ребро из контура. Получили дерево: (fe) (ea) (ac) (cb) (bd) с весом l=1+2+3+2+2=10 Задача о кратчайших путях Пусть G – ориентированный граф, Е – ребра графа. Каждому ребру соответствует число. Рисунок 3.15 – Эйлеров цикл Задача Эйлера о Кенигсбергских мостах [19]: необходимо выйти из любой точки города и вернуться в нее, при этом пройдя по каждому мосту только один раз. Эйлер свел эту задачу к графу: существует ли в конечном графе такой цикл, в котором каждое ребро участвует только один раз? Цикл, в котором каждое ребро графа G участвует всего один раз, называется эйлеровым циклом. Граф, содержащий эйлеров цикл, называется эйлеровым. Дальнейшее развитие задачи об Эйлеровом цикле Припишем ребрам графа длину μ (ai, aj). Требуется найти путь в графе, который проходит через все ребра и имеет наименьшую длину. Пример. Рисунок 3.16 – Граф S – стартовая вершина. Из вершины S надо пройти по всем ребрам так, чтобы маршрут имел минимальную длину. Очевидно, что длина маршрута будет минимальной, если каждое ребро будет пройдено всего один раз – т. е. маршрут будет эйлеровым циклом. Все локальные степени – четные, значит граф эйлеров. Варианты прохождения по циклу: 1) (sa) (ab) (bc) (cd) (db) (ds) 2) (sa) (ab) (bd) (dc) (cb) (bs) 3) (sb) (bc) (cd) (db) (ba) (as) 4) (sb) (bd) (dc) (cb) (ba) (as) Длина эйлерова цикла – 22. Любой из вариантов 1–4 содержит каждое ребро графа, следовательно, длина одинакова для всех циклов 1–4. Длина эйлерова цикла не зависит от того, какая вершина будет выбрана за исходную. Задача поиска эйлерова цикла – это задача о: – поиске наилучшего способа прохождения бригады по дорогам; – прохождении с/х техники по полям. Впервые эта задача рассматривалась в связи с нахождением оптимального маршрута следования почтальона, который доставляет письма своим адресатам и должен при этом пройти минимальный путь. Алгоритм нахождения эйлерова цикла для неориентированного графа [19]: Дан эйлеров граф – т. е. граф с четными локальными степенями. Найдем первое ребро х, инцидентное вершине S. Затем найдем ребро, смежное с ребром х, которое не образует цикл и еще не было использовано. Продолжим этот процесс до тех пор, пока не вернемся в вершину S. Если в построенный цикл С1 вошли все ребра графа – задача решена. Если в построенный цикл С1 вошли не все ребра – строим цикл С2, состоящий из неиспользованных ребер и начинающийся с произвольного неиспользованного ребра. Таким образом, строим циклы С2, С3,….Образование циклов продолжается до тех пор, пока не будут использованы все ребра. Все циклы Сi необходимо объединить в один цикл. Условие объединения циклов С1 и С2 – наличие у них общей вершины х. Начинаем движение с любой вершины и двигаемся по циклу С1 до тех пор, пока не дойдем до х. Затем проходим ребро. С» и возвращаемся в х. Продолжаем обход по оставшимся ребрам до возвращения к исходной точке. Эта процедура легко обобщается на случай любого числа объединяемых циклов. Циклы Эйлера для ориентированного графа Алгоритм построения эйлерова цикла в эйлеровом ориентированном графе является аналогом алгоритма построения эйлерова цикла для неориентированного графа. Строятся циклы Сi с учетом ориентации ребер, и затем все циклы объединяются в один. Гамильтонов цикл (задача о коммивояжере) Простой цикл, проходящий через каждую вершину графа только один раз, называется гамильтоновым циклом. Если ребрам приписана длина, то различные варианты циклов отличаются друг от друга. Поэтому ставится задача нахождения гамильтонова цикла, имеющего минимальную длину. Гамильтонов цикл наименьшей длины называется оптимальным гамильтоновым циклом (ОГЦ) Поиск оптимального гамильтонова цикла – задача о коммивояжере, который должен посетить множество пунктов и вернуться домой, пройдя наименьший путь. Решением задачи о коммивояжере не всегда является ОГЦ. Гамильтоновы графы применяются для моделирования многих практических задач. Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра – связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим транспортные затраты, необходимые для путешествия по соответствующей дороге, например, расстояние между городами или время движения по дороге. Для решения задачи нам необходимо найти гамильтонов цикл минимального общего веса. Рисунок 3.17 – Ребра, входящие в гамильтонов цикл С К сожалению, алгоритм решения данной задачи, дающий оптимальное решение, пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно. Однако существуют алгоритмы поиска субоптимального решения [1]. Субоптимальное решение необязательно даст цикл минимального общего веса, но найденный цикл будет, как правило, значительно меньшего веса, чем большинство произвольных гамильтоновых циклов! Один из таких алгоритмов – алгоритм ближайшего соседа. Этот алгоритм выдает субоптимальное решение задачи коммивояжера, генерируя гамильтоновы циклы в нагруженном графе с множеством вершин V. Цикл, полученный в результате работы алгоритма, будет совпадать с конечным значением переменной маршрут, а его общая длина – конечное значение переменной w. begin Выбрать v € V; маршрут:=v; w:=0; v':=v; Отметить v'; while остаются неотмеченные вершины do begin Выбрать неотмеченную вершину и, ближайшую к v'; маршрут:= маршрут u; w:= w + вес ребра v'u; v':=u; Отметить v'; end маршрут:= маршрут v; w:= w + вес ребра v'v; end Пример. Примените алгоритм ближайшего соседа к графу, изображенному на рисунке 3.18. За исходную вершину возьмите вершину D. Рисунок 3.18 – Граф Таблица 3.2 – Алгоритм ближайшего соседа и маршрут w v' Исходные значения – D 0 D С dc 3 С А DCA 9 A В DCAB 14 В Последний проход В DCABD 24 В В результате работы алгоритма был найден гамильтонов цикл DCABD общего веса 24. Делая полный перебор всех циклов в этом маленьком графе, можно обнаружить еще два других гамильтоновых цикла: ABCDA общего веса 23 и ACBDA общего веса 31. В полном графе с двадцатью вершинами существует приблизительно 6,1 * 10^16 гамильтоновых циклов, перечисление которых требует чрезвычайно много машинной памяти и времени. Реализация примера данного алгоритма в Delphi: procedure TForm1. Button1Click (Sender: TObject); const mat:array [1.. 4,1..4] of byte=((0,5,6,8), (5,0,7,10), (6,7,0,3), (8,10,3,0)); Versh:array [1..4] of char=('a', 'b', 'c', 'd'); buk:char='d'; Type t=set of 'a'..'d'; Var dlina, i, j, min, n, k, s:byte; put:string; z:t; begin dlina:=0; Memo1. Lines. Clear; for i:=1 to 4 do if versh[i]=buk then begin n:=i; s:=i; include (z, buk); put:=put+buk; end; for j:=1 to 3 do begin if mat [n, 1]<>0 then begin min:=mat [n, 1]; k:=1; end else begin min:=mat [n, 2]; k:=2; end; for i:=1 to 4 do if (mat [n, i] min:=mat [n, i]; k:=i; end; dlina:=dlina+min; put:=put+versh[k]; include (z, versh[k]); n:=k; end; put:=put+'d'; dlina:=dlina+mat [k, s]; Memo1. Lines. Add ('маршрут:'+' '+put); Memo1. Lines. Add ('длина маршрута='+IntToStr(dlina)); end; end. Рисунок 3.19 – Форма с результатом 3.2 Практическая часть 3.2.1 Задание к работе 1 изучить теоретический материал по методическому пособию [24], лекциям и записям на практических занятиях; 2 получить задание по индивидуальному варианту в виде графа или матрицы смежности, в первом случае построить матрицу смежности, во втором – нарисовать граф; 3 составить подробное описание графа: ориентированный или неориентированный, количество вершин, дуг (рёбер), содержит ли циклы и какие, найти степени вершин, количество компонент связности и т. д.; 4 создать приложение на Delphi для расчёта матрицы инцидентности по известной матрице смежности (если граф достаточно сложный, то можно взять подграф этого графа); 5 в качестве дополнительного творческого задания создать приложение на Delphi для реализации алгоритма ближайшего соседа, алгоритма Прима, алгоритма Уоршелла, алгоритма Дейкстры, алгоритма определения количества компонент связности графа и других известных алгоритмов на графах. [13], [17], [18], [19], [20], [21]. 3.2.2 Примеры выполнения Пример 1: По заданной матрице смежности построить матрицу инцидентности. implementation procedure TForm1. UpDown1Click (Sender: TObject; Button: TUDBtnType); begin with UpDown1 do begin with StringGrid1 do begin RowCount:=Position; ColCount:=Position; end; StringGrid2. RowCount:=Position; end; end; procedure TForm1. BitBtn1Click (Sender: TObject); var i, j, CD, P, n:byte; MS:array of array of byte; MI:array of array of ShortInt; begin P:=StrToInt (Edit1. Text); SetLength (MS, P, P); CD:=0; for i:=0 to P‑1 do for j:=0 to P‑1 do begin MS [i, j]:=StrToInt (StringGrid1. Cells [j, i]); if MS [i, j]=1 then inc(CD); end; SetLength (MI, P, CD); for i:=0 to High(MS) do for j:=0 to CD‑1 do MI [i, j]:=0; n:=0; for i:=0 to High(MS) do for j:=0 to High(MS) do if MS [i, j]=1 then begin MI [i, n]:=1; MI [j, n]:=-1; inc(n); end; StringGrid2. ColCount:=CD; for i:=0 to High(MS) do for j:=0 to CD‑1 do StringGrid2. Cells [j, i]:=IntToStr (MI[i, j]); end; end. Рисунок 3.20 – Форма с результатом Пример 2: По заданной матрице смежности построить матрицу инцидентности. var Form1: TForm1; const maxv=4; type canh=record dinh1, dinh2:byte; dodai:real; end; dothi=record n:byte; l:array [1..maxv, 1..maxv] of real; x, y:set of 1..maxv; t:array [1..maxv] of canh; nt:byte; it:real; end; implementation {$R *.dfm} procedure TForm1. Button1Click (Sender: TObject); var g:dothi; min:real; x, y, x0, y0:1..maxv; i, j:byte; begin memo1. Clear; g.n:=maxv; edit1. Text:=inttostr(maxv); stringgrid1.cells [0,0]:=' Номер'; for i:=1 to maxv do begin stringgrid1.cells [0, i]:=inttostr(i); stringgrid1.cells [i, 0]:=inttostr(i); end; g.nt:=0; g.it:=0; g.x:=[1..g.n]; g.y:=[1]; for i:=1 to maxv do for j:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]); while g.nt min:=-1; for x:=1 to g.n do for y:=1 to g.n do if (x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then begin if (min=-1) or (min>g.l [x, y]) then begin min:=g.l [x, y]; x0:=x; y0:=y; end; end; g.y:=g.y+[y0]; g.nt:=g.nt+1; g.it:=g.it+min; with g.t [g.nt] do begin dinh1:=x0; dinh2:=y0; dodai:=min; end; end; for i:=1 to (maxv‑1) do with g.t[i] do memo1. Lines.add ('Ребро: '+inttostr(dinh1)+inttostr(dinh2)+' '+ 'Весом: '+floattostr(dodai)); end; end. Рисунок 3.21 – Форма с результатом Пример 3: Составить приложение на Delphi, реалилующее алгоритм Уоршелла. var Form1: TForm1; const maxv=4; type canh=record dinh1, dinh2:byte; dodai:real; end; dothi=record n:byte; l:array [1..maxv, 1..maxv] of real; x, y:set of 1..maxv; t:array [1..maxv] of canh; nt:byte; it:real; end; implementation {$R *.dfm} procedure TForm1. Button1Click (Sender: TObject); var g:dothi; min:real; x, y, x0, y0:1..maxv; i, j:byte; begin memo1. Clear; g.n:=maxv; stringgrid1.cells [0,0]:=' Номер'; for i:=1 to maxv do begin stringgrid1.cells [0, i]:=inttostr(i); stringgrid1.cells [i, 0]:=inttostr(i); end; g.nt:=0; g.it:=0; g.x:=[1..g.n]; g.y:=[1]; for i:=1 to maxv do for j:=1 to maxv do g.l [i, j]:=strtofloat (stringgrid1. Cells [j, i]); while g.nt min:=-1; for x:=1 to g.n do for y:=1 to g.n do if (x in g.y) and (y in (g.x-g.y)) and (g.l [x, y]>0) then begin if (min=-1) or (min>g.l [x, y]) then begin min:=g.l [x, y]; x0:=x; y0:=y; end; end; g.y:=g.y+[y0]; g.nt:=g.nt+1; g.it:=g.it+min; with g.t [g.nt] do begin dinh1:=x0; dinh2:=y0; dodai:=min; end; end; for i:=1 to (maxv‑1) do with g.t[i] do memo1. Lines.add ('Ребро: '+inttostr(dinh1)+inttostr(dinh2)+' '+ 'Весом: '+floattostr(dodai)); end; end. Рисунок 3.23 – Форма с результатом 3.2.3 Вариантв заданий 3.3 Вопросы для самопроверки 1) Какие операции над графами Вы знаете? 2) Как формируется матрица смежности? 3) Как формируется матрица весов? 4) Как формируется матрица достижимости? 5) Как формируется матрица инцидентности? 6) Перечислите основные понятия, относящиеся к графам-деревьям. 7) Приведите пример сортировки и поиска в деревьях. 8) Для чего применяется алгоритм, подобный алгоритму Дейкстры, в коммуникационных сетях? 9) Перечислите известные Вам алгоритмы обхода графов. 10) Что такое транспортная сеть? Приведите пример. 11) Какой граф называется эйлеровым? Приведите пример эйлерова графа. 12) Какой граф называется гамильтоновым? Приведите пример гамильтонова графа. 13) Какой вид отношений на графах представляет изоморфизм графов? 14) Приведите пример отношения порядка и отношения эквивалентности на графе. 15) Какие алгоритмы обхода графов Вам известны? 16) Какие виды графов Вы знаете? 17) Что понимается под степенью вершины? 18) Как определяются числа внутренней и внешней устойчивости графа? 19) Как определяются хроматическое и цикломатическое числа графа? 20) Сформулируйте транспортную задачу и связанные с ней понятия? 21) Опишите кратко алгоритм управления проектами. 22) Приведите пример построения разреза графа. 23) Приведите пример дерева с корнем. Практическая работа № 4. Элементы теории множеств и алгебры логики Цель работы: применение знаний теории множеств и алгебры логики для решения практической задачи. 4.1 Указание к выполнению Данная практическая работа сочетает в себе использование элементов теории множеств и алгебры логики. Все теоретические сведения, необходимые для выполнения данной работы, изложены в лекциях и в уже изданных методических пособиях [23], [25]. Выполнение данной работы рекомендуется выполнять по образцу, рассмотренному далее. 4.2 Задание к работе 1. Составить множества из букв Ф.И.О.. 2. Представить полученные множества на кругах Эйлера. 3. Представить буквы Ф.И.О. в двоичной системе. 4. Представить диаграмму Венна. СНДФ. 5. Перевести числа даты рождения в двоичную систему счисления. Примечание: желательно реализовать основные вычисления в приложении на Delphi. 4.3 Практическая часть Пример 1: 1 Множества из букв Ф.И.О. МОРОЗОВ ОЛЕГ ЕВГЕНЬЕВИЧ Ф = {М, О, Р, З, В}; И = {О, Л, Е, Г}; О = {Е, В, Г, Н, Ь, И, Ч}; 2 Круги Эйлера и диаграммы Венна Рисунок 4.1 – Круги Эйлера Таблица 4.1 – Буквы алфавита в двоичной системе А 00001 Л 01011 Ц 10110 Б 00010 М 01100 Ч 10111 В 00011 Н 01101 Ш 11000 Г 00100 О 01110 Щ 11001 Д 00101 П 01111 Ъ 11010 Е 00110 Р 10000 Ы 11011 Ж 00111 С 10001 Ь 11100 З 01000 Т 10010 Э 11101 И 01001 У 10011 Ю 11110 К 01010 Ф 10100 Я 11111 Х 10101 Таблица 4.2 – Буквы Ф.И.О. в двоичной системе М О Р З В О Л Е Г Е В Г Н Ь И Ч 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 3 F1 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0 8 F2 1 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 10 F3 0 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 8 0 0 0 0 1 0 1 0 0 0 1 0 1 0 1 1 6 Таблица 4.3 – СНДФ из букв Ф.И.О. x1 x2 x3 x4 F1 F2 F3 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1
.
А и х
В) или (х
В и х
А)}.
S, результат операции – ответ «да»; в противном случае –
, если v – левый сын вершины i
, если v – правый сын вершины i
0 – мощность множества
0 – мощность множества
для n = к. Тогда последовательность кодов B10,…,
0,
1, …. B11 будет искомой последовательностью для n = к + 1. Действительно, в последовательности B10,…,
0,
1,…, В11 имеется 2k+1 кодов, они все различны и соседние различаются ровно в одном разряде по строению. Именно такое построение и осуществляет данный алгоритм. На нулевом шаге алгоритм выдает правильное подмножество В (пустое). Пусть за первые 2k – 1 шагов алгоритм выдал последовательность значений В. При этом В [k + 1] = В [k + 2] = • • • = В[n] = 0. На 2 k‑ом шаге разряд В [k + 1] изменяет свое значение с 0 на 1. После этого будет повторена последовательность изменений значений В [1. k] в обратном порядке, поскольку Q (2k + m) = Q (2k – m) для
составит O(n), а трудоемкость операций
составит О(nm), где n и m – мощности участвующих в операции множеств.
n > 0.
1 do
1 then
m. Другими словами, следующая последовательность получается из предыдущей заменой некоторого количества элементов в хвосте последовательности на идущие подряд целые числа, но так, чтобы последний элемент не превосходил n, а первый изменяемый элемент был на 1 больше, чем соответствующий элемент в предыдущей последовательности. Таким образом, индекс р, начиная с которого следует изменить «хвост последовательности», определяется по значению элемента А[n]. Если А[n] < m, то следует изменять только А[n], и при этом р: = n. Если же уже А(n) = m, то нужно уменьшать индекс р: =р – 1, увеличивая длину изменяемого хвоста.
элементы характеристического вектора считают по правилу:
элементы характеристического вектора считают по правилу:
нули меняют на единицы, единицы – на нули;
, используют формулу:
. Он равен
= {1, 2, 4, 5, 6}.
к D
={1,3}
, которое состоит из всех ребер графа G, не принадлежащих H.
H2 – есть часть, состоящая из ребер, принадлежащих H1 и H2 одновременно. Две части не пересекаются по вершинам, если они не имеют общих вершин, и, следовательно, ребер. Части H1 и H2 не пересекаются по ребрам, если они не имеют общих ребер H1
H2=0. Если H1 и H2 непересекающиеся части графа G, то их сумма называется прямой и H1UH2=G.