Новиков Ф.А. Дискретная математика для программистов (860615), страница 9
Текст из файла (страница 9)
i thenpb-.~pb.n{ элемент множества А, может быть, присутствуетмножестве В }elsepa: — pa ль { здесь pa л = pb.i, то есть }pb\ --pb.n { элемент множества А точно присутствует в множестве В }end ifend whilereturn pa = nil {true, если А исчерпано, false — в противном случае }вНа каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В. В первом случае текущий элемент множества А заведомоменьше, чем текущий и все последующие элементы множества В, а потому он несодержится в множестве В и можно завершить выполнение алгоритма. Во второмслучае происходит продвижение по множеству В в надежде отыскать элемент,совпадающий с текущим элементом множества А.
В третьем случае найденыОБОСНОВАНИЕ1.3. Представление множеств в программах43совпадающие элементы и происходит продвижение сразу в обоих множествах.По завершении основного цикла возможны два варианта: либо pa = nil, либора ф nil. Первый означает, что для всех элементов множества А удалось найтисовпадающие элементы в множестве В. Второй — что множество В закончилосьраньше, то есть не для всех элементов множества А удалось найти совпадающиеэлементы в множестве В.•1.3.6. Вычисление объединения слияниемРассмотрим алгоритм слияния, который вычисляет объединение двух множеств,представленных упорядоченными списками.Алгоритм 1.5 Вычисление объединения слияниемВход: объединяемые множества А и В, которые заданы указателями а и Ь.Выход: объединение С = A U В, заданное указателем с.pa:=a-,pb: = b;c: =nil; е: =nil { инициализация }while pa фт\ к pb фт\ doif pa.i < pb.i thend: = pa.i] pa: =pa.n { добавлению подлежит элемент множества А }else if pa.i > pb.i thend\ = pb.i\pb\ =pb.n { добавлению подлежит элемент множества В }elsed\=pa.i { здесь pa.i = pb.i, и можно взять любой из элементов }ра\ = pa.n\pb: =pb.n { продвижение в обоих множествах }end ifAppend(c,e,d) { добавление элемента d в конец списка с }end whileр: =nil { указатель «хвоста» }if pa Ф nil thenр \ ~ р а { нужно добавить в результат оставшиеся элементы множества А }end ifif pb ф nil thenp\~pb { нужно добавить в результат оставшиеся элементы множества В }end ifwhile р фп\\ doAppend(n,e,p.i) { добавление элемента pa.i в конец списка с }р: = р.п { продвижение указателя «хвоста» }end whileНа каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В.
В первом случае в результирующий список добавляетсятекущий элемент множества А и происходит продвижение в этом множестве, воОБОСНОВАНИЕ44Глава 1. Множества и отношениявтором — аналогичная операция производится с множеством В, а в третьем случае найдены совпадающие элементы и происходит продвижение сразу в обоихмножествах. Таким образом, в результат попадают все элементы обоих множеств,причём совпадающие элементы попадают ровно один раз. По завершении основного цикла один из указателей, ра и pb (но не оба вместе!), может быть пе равенnil. В этом случае остаток соответствующего множества без проверки добавляетсяв результат.•Вспомогательная процедура Append(c, е, d) присоединяет элемент d к хвосту есписка с.Алгоритм 1.6 Процедура Append — присоединение элемента в конец спискаВход: указатель с на первый элемент списка, указатель е на последний элементсписка, добавляемый элемент d.Выход: указатель с на первый элемент списка, указатель е на последний элементсписка.q: = new(elem); q.i: = d; q.n: =nil { новый элемент списка }if с =nil thenc:—q { пустой список }elsee.n :—-q{ непустой список }end ife: = qД О первого вызова функции Append имеем: с = nil и е = nil.
Послепервого вызова указатель с указывает на первый элемент списка, а указатель е —на последний элемент (который после первого вызова является тем же самымэлементом). Если указатели с и е не пусты и указывают иа первый и последнийэлементы правильного списка, то после очередного вызова функции Append этосвойство сохраняется. Из текста основной программы видно, что, кроме инициализации, все остальные манипуляции с этими указателями выполняются толькос помощью функции Append.•ОБОСНОВАНИЕ1.3.7. Вычисление пересечения слияниемРассмотрим алгоритм слияния, который вычисляет пересечение двух множеств,представленных упорядоченными списками.Алгоритм 1.7 Вычисление пересечения слияниемВход: пересекаемые множества А и В, заданные указателями а и Ь.Выход: пересечение С = А П В, заданное указателем с.ра: — а; pb\—b; с: = nil; е: =nil { инициализация }while pa / n i l & pb / n i l do1.3.
Представление множеств в программах45if pa.i < pb.i thenp a : = pa.n { элемент множества А пе принадлежит пересечению }else if pa.i > pb.i thenpb: —pb.n { элемент множества В не принадлежит пересечению }else{ здесь pa.i = pb.i — данный элемент принадлежит пересечению }Append(c,е,pa.i)-,pa: = pa.n\pb: =pb.n { добавление элемента }end ifend whileНа каждом шаге основного цикла возможна одна из трёх ситуаций: текущий элемент множества А меньше, больше или равен текущему элементу множества В.
В первом случае текущий элемент множества А пе принадлежитпересечению, оп пропускается и происходит продвижение в этом множестве, вовтором то же самое производится с множеством В. В третьем случае найдены совпадающие элементы, один экземпляр элемента добавляется в результати происходит продвижение сразу в обоих множествах. Таким образом, в результат попадают все совпадающие элементы обоих множеств, причём ровноодин раз.•ОБОСНОВАНИЕ1.3.8. Представление множеств итераторамиВ предыдущих подразделах рассмотрены представления, в которых структурыданных предполагаются известными и используются при программировании операций.
Иногда это бывает неудобно, поскольку, во-первых, возникают затруднения при совместном использовании нескольких альтернативных представленийдля одного типа объектов, и, во-вторых, необходимо заранее определять наборопераций, которым открыт доступ к внутренней структуре данных объектов.(Такие операции часто называют первичными.)ОТСТУПЛЕНИЕПарадигма объектио-ориеитироваипого программирования предполагает совместное согласованное определение структур данных и процедур доступа к ним (типов как множествзначений и первичных операций над значениями из этих множеств).
Мы хотим напомнить читателю, что парадигма объектно-ориентированного программирования — весьмаполезная, по отнюдь не универсальная и пе единственная парадигма программирования.Применительно к множествам следует признать, что понятие принадлежностиявляется первичным, и потому вряд ли может быть запрограммировано без использования структуры данных для храпения множеств, но остальные операциинад множествами нельзя признать первичными, и их можно запрограммировать независимо от представления множеств.
Для иллюстрации этой идеи рассмотрим один из возможных способов реализации операций над множествами,46Глава 1. Множества и отношенияне зависящий от представления множеств. Видимо, можно считать, что с программистской точки зрения для представления множества достаточно итератора — процедуры, которая перебирает элементы множества и делает с ними то,что нужно. Синтаксически понятие итератора может быть реализовано самыми различными способами в зависимости от традиций, стиля и используемогоязыка программирования.
Например, следующая программа выполняет процедуру S для всех элементов множества X (см. также доказательство теоремы 1 вподразделе 1.2.5):while X ф 0 doselect х € X { выбор произвольного элемента х из множества X }S(x) { применение процедуры S к элементу х }X : = X - х {удаление элемента х с целыо исключить его повторный выбор}end whileВ этом варианте реализации итератора исходное множество «исчезает», что невсегда желательно. Очевидно, что для всякого конкретного представления множества можно придумать такую реализацию итератора, которая обеспечиваетперебор элементов ровно по одному разу и пе портит исходного множества.Мы полагаем (здесь и >далее во всей книге), что наличие итератора позволяетнаписать циклfor х € X doS(x) { где S — любой оператор или процедура, зависящие от х }end forи этот цикл означает применение оператора S ко всем элементам множества Xпо одному разу в некотором неопределённом порядке.ЗАМЕЧАНИЕВ доказательствах цикл for х € X do S(x) end for используется и в том случае, когда== оо.
Это не означает реального процесса исполнения тела цикла в дискретные моментывремени, а означает всего лишь мысленную возможность применить оператор S ко всемэлементам множества X независимо от его мощности.В таких обозначениях итератор пересечения множеств X П У может быть заданалгоритмом 1.8.Алгоритм 1.8 Итератор пересечения множествfor х € X dofor у £ Y doif x — у thenS(x) { тело цикла }next for x { следующий x }end ifend forend for471.3. Представление множеств в программахАналогично итератор разиости множеств X\Yможет быть задан алгоритмом 1.9.Алгоритм 1.9 Итератор разности множествfor х £ X dofor у eY doif x = у thennext for x { следующий x }end ifend forS(x) { тело цикла }end forЗАМЕЧАНИЕОператор next for x — это оператор структурного перехода, выполнение которого в данном случае означает прерывание выполнения цикла по у и переход к следующему шагув цикле по х.Заметим, что A U В = {А \ В) U В и (А \ В) П В - 0 .
Поэтому достаточно рассмотреть итератор объединения дизъюнктных множеств X UK (алгоритм 1.10),где X П Y = 0 .Алгоритм 1.10 Итератор объединения дизъюнктных множествfor х € X doS(x) { тело цикла }end forfor у eY doS(y) { тело цикла }end forСтоит обратить внимание на то, что итератор пересечения реализуется вложенными циклами, а итератор дизъюнктного объединения — последовательностьюциклов.Нетрудно видеть, что сложность алгоритмов для операций с множествами прииспользовании предложенного представления, не зависящего от реализации, составляет в худшем случае 0(пт), где тип— мощности участвующих множеств, в то время как для представления упорядоченными списками сложностьв худшем случае равна 0(п + т).ЗАМЕЧАНИЕНа практике почти всегда оказывается так, что самая изощрённая реализация операции,не зависящая от представления, оказывается менее эффективной по сравнению с самойпрямолинейной реализацией, ориентированной на конкретное представление.48Глава 1.
Множества и отношенияОТСТУПЛЕНИЕПри современном состоянии аппаратной базы вычислительной техники оказывается, чтово многих задачах можно пренебречь некоторым выигрышем в эффективности, например, различием между 0(птп) и 0(п + т). Другими словами, нынешние компьютерынастолько быстры, что часто можно не гнаться за самым эффективным представлением,ограничившись «достаточно эффективным».1.4. ОтношенияОбычное широко используемое понятие «отношение» имеет вполне точное математическое значение, которое вводится в этом разделе.1.4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
