АиСД-Часть 1-осень


МИНОБРНАУКИ РОССИИ
–––––––——————————–––––––
Санкт-Петербургский государственныйэлектротехнический университет «ЛЭТИ»
————————————————————
АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ
Методические указания к лабораторным работам,практическим занятиями курсовому проектированию
Стандарт третьего поколения
Санкт-ПетербургИздательство СПбГЭТУ «ЛЭТИ»2013
УДК 004.424:004.422.63(075.8)
Алгоритмы и структуры данных: Методические указания к лабораторным работам, практическим занятиям и курсовому проектированию. Стандарт третьего поколения / Сост.: П. Г. Колинько. –– СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2013. — PAGEREF конец \h 62 с.: ил.
Описывается цикл лабораторных работ и практических занятий в компьютерном классе. Содержатся материалы для курсовой работы.
Пособие предназначено для студентов-бакалавров по направлению 230100.62 «Информатика и вычислительная техника» дневной, очно-заочной и заочной форм обучения.
Утвержденоредакционно-издательским советом университета в качествеметодических указаний
© П. Г. Колинько, 2012–2013
© СПбГЭТУ «ЛЭТИ», 2013
ВВЕДЕНИЕЦель практикума — развитие навыков программирования, полученных студентами на первом курсе. Основное внимание уделяется изучению способов реализации в ЭВМ абстрактных данных и вытекающих из этих способов свойств алгоритмов обработки этих данных. В качестве примеров рассматриваются популярные алгоритмы на ненагруженных и нагруженных графах, жадные алгоритмы, эмпирические алгоритмы для переборных задач. Изучаются способы организации данных в реальных задачах, когда одному и тому же набору данных могут применяться одновременно несколько абстрактных моделей.
Практикум покрывает первый семестр двухсеместрового курса «Алгоритмы и структуры данных» и состоит из трёх разделов. Тема первого раздела — «множества» — является вводной. В ней показывается, что абстрактные данные могут быть реализованы в программе разными способами и что от способа реализации зависит существенная характеристика алгоритма — его временная сложность. Вводится понятие объекта как естественного расширения языка С++ для поддержки пользовательских типов данных.
Изучение темы разбито на этапы по схеме от простого — к сложному. На усмотрение преподавателя — объединить некоторые этапы для сильных студентов или ограничиться их частью для слабых. Практические занятия состоят в изучении учебных примеров, имеющихся в пособии или прилагаемых к нему, а также в постановке опытов с программным кодом и исследовании алгоритмов.
Вторая тема — «деревья» — акцентирует внимание студентов на свойствах рекурсивного определения данных и рекурсивных алгоритмов. Она предусматривает также освоение техники работы с объектами: создание и уничтожение, копирование объектов, совместное использование в программе объектов разных типов (дружественные функции) и т. п. Вводится понятие шаблона функции и класса, в качестве иллюстрации для применения которого используются абстрактные данные «очередь» и «стек».
Третья тема — «графы» — выносится на курсовое проектирование для закрепления навыков, полученных при изучении двух первых тем.
Объём теоретических сведений об абстрактных данных и алгоритмах в пособии минимален. Предполагается, что студенты могут взять недостающее из параллельно изучаемого курса «Дискретная математика», а также из рекомендованной литературы.
Предполагается, что студенты уже знакомы с такими элементарными структурами данных, как массивы, списки, очереди и стеки.
Все примеры, имеющиеся в пособии, проверены в оболочке Visual C++ 2005. В Borland C++ 3.1 они могут быть использованы после небольшой модификации. Для обучения могут быть использованы любые программные оболочки с поддержкой С++, причём рекомендуются такие, которые поддерживают стандарт языка C99: Borland C++ Builder 6.0, Microsoft Visual С++ 2003 и более современные, в том числе свободно распространяемые компиляторы (DEV C++ и т. п.), а также компиляторы в ОС Linux.
1. МНОЖЕСТВАМножество — абстрактная структура данных, для которой определена операция принадлежности. Новые множества создаются из существующих с помощью операций объединения, пересечения, разности, симметрической разности.
Представление множества набором элементовОдним из способов задания множества является простое перечисление входящих в него элементов. В памяти ЭВМ элементы такого множества могут быть расположены в последовательности ячеек, т. е. образуют массив. Это — самый экономный способ хранения множества в тех случаях, когда мощность множества известна, а его элементы — данные одного типа (во всех случаях, когда это не так, элементы множества можно расположить в памяти произвольным образом и работать с ними через указатели). Память под массив удобно выделить статически. В этом случае её можно сразу инициализировать.
Пример. Объявление и инициализация массива для множества десятичных цифр.
сonst int Nmax = 10;
char A[Nmax+1] = {'1', '3', '4', '7', '\0'};
В память, выделяемую под универсум, помещено множество-константа. Множество символов предполагается обрабатывать как строку, поэтому пришлось позаботиться об ограничивающем нуле. Если множество расширяться не будет, размер памяти можно не указывать:
char A[ ] = {"1347"};
Выделяется память под множество из четырёх элементов и ограничивающий нуль.
Мощность, множества, заданного константой, рекомендуется вычислять:
int nA = strlen(A);
Если множество создаётся в результате вычислений, его мощность может быть неизвестна. Поскольку память под массив должна быть выделена до начала работы с ним, приходится делать это с запасом. Проще всего выделить память сразу под универсум, а если универсум слишком велик, то под множество максимальной мощности, которое может быть реально получено. Если же память оказалась исчерпана до окончания вычислений, можно попытаться заказать область памяти большего размера и перенести в неё накопленные элементы множества. Это — дорогая операция, поскольку приходится полностью копировать множество. Она может быть невыполнима, если в памяти нет непрерывного участка достаточного размера. Освобождаемый участок памяти тоже не всегда можно использовать. Если же оценка мощности результата слишком пессимистична, память под множество используется нерационально. Так, её приходится выделять даже для результата — пустого множества.
Этих проблем нет, если для представления множества в памяти используется односвязный список. Память в этом случае выделяется под каждый элемент множества отдельно, и её ровно столько, сколько необходимо. Так, под пустое множество-список память вообще не выделяется. Память от удаляемых элементов списка легко использовать под вновь создаваемые элементы. Перенос элемента из одного множества в другое вообще не требует дополнительной памяти.
Главный недостаток способа — необходимость хранить с каждым элементом множества указатель на следующий элемент и тратить время на работу с ним. Так, создание копии списка в другом месте памяти требует не только отдельной обработки каждого элемента множества, но и создания вновь всех указателей. Имеются и скрытые потери: минимальная область, выделяемая в динамической памяти, часто больше, чем требуется для хранения одного элемента множества вместе с указателем.
Реализация алгоритмов для работы с множествами, представленным массивами или списками, отличается только способом перебора этих структур данных. Подтвердим это примером реализации операции принадлежности элемента множеству десятичных цифр.
Для массива используем объявление из предыдущего примера. Множество-список объявим так:
struct Set{ char el;
Set * next;
}
Set *LA;// Указатель на начало списка для множества A.
Результатом вычислений будет значение булевской переменной b.
bool b = false;
char s = getche(); // Символ вводится с клавиатуры
for (int i = 0; i <nA; i++) // Вариант 1: перебор элементов массива
if (A[i] == s) b = true;
for (Set * p = LA; p; p = p->next) //Вариант 2: просмотр списка
if (p->el == s) b = true;
Очевидно, что оба варианта реализации имеют линейную временную сложность по мощности множества: O(nA). Оценка не меняется и в том случае, если при обнаружении элемента в множестве цикл прерывается.
Практикум по темеСоставить и отладить программу, реализующую обработку множеств по предложенному заданию.
Уточнить задание: записать его в виде формулы для получения пятого множества по заданным четырём, используя знаки операций над множествами. Результат может выглядеть так:
E = A ⋃ B ⋂ C \ D
Предложить контрольный тест в соответствии с заданным типом универсума
A = {1, 2, 3, 4, 5}
B = {2, 4, 6}
C = {4, 6, 7, 8}
D = {1, 3, 9}
E = ? (вычислить результат!)
Составить программу для вычисления пятого множества по четырём заданным, используя для представления множеств в памяти массивы символов. Для задания исходных множеств использовать инициализацию. Добиться прохождения теста.
Добавить в программу ввод исходных множеств и протестировать её на нескольких тестах: на пустых, полных, не пересекающихся, совпадающих множествах и т. п. Рекомендуется использовать для ввода символов функцию gets( ), а для определения мощности множества — функцию strlen( ).
Дополнить программу так, чтобы исходные множества из массивов преобразовывались в линейные списки, и получение результата достигалась обработкой этих списков.
Варианты индивидуальных заданий к теме «Множества»№ вари-анта Универсум Что надо вычислить
1 десятичные цифры множество, содержащее цифры, общие для множеств A и B, а также все цифры из множества C и из множества D
2 прописные латинские буквы множество, содержащее все символы из множества A, за исключением символов, содержащихся в B или в C, а также все символы множества D
3 шестнадцатеричные цифры множество, содержащее цифры, имеющиеся в любом из множеств A, B, C, и D
4 строчные латинские буквы множество, содержащее все буквы, общие для множеств A и B, за исключением букв, содержащихся в C, а также все буквы из D
5 десятичные цифры множество, содержащее все цифры множества A, за исключением цифр из B и из C, а также все цифры из D
6 русские буквы множество, содержащее все буквы множеств A и B, за исключением букв, содержащихся в C, а также все буквы из D
7 шестнадцатеричные цифры множество, содержащее цифры, имеющиеся в каждом из множеств A, B, C, а также все цифры из D
8 латинские буквы множество, содержащее буквы, имеющиеся во множестве A, но не являющихся общими для B и C, и все буквы из D
9 десятичные цифры множество, содержащее все цифры из A, все цифры, общие для множеств B и C, а также все цифры из D
10 прописные латинские буквы множество, содержащее буквы, имеющиеся в A или B, но отсутствующие в C, и, кроме того, обязательно встречающиеся также и в D
11 шестнадцатеричные цифры множество, содержащее цифры, имеющиеся во множествах A или C, но отсутствующие в B или D
12 строчные латинские буквы множество, содержащее буквы, имеющиеся в любом из множеств A, B, C, но отсутствующие в D
13 десятичные цифры множество, содержащее цифры, общие для множеств A и B, но не встречающиеся ни в C, ни в D
14 прописные русские буквы множество, содержащее все буквы множества A, которых нет во множествах B, C, или D
15 шестнадцатеричные цифры множество, содержащее цифры, имеющиеся в A или в B, но отсутствующие и в C, и в D
16 строчные русские буквы множество, содержащее буквы, общие для множеств A, B, C и не встречающиеся D
17 десятичные цифры множество, содержащее цифры из A, не являющиеся общими для множеств B и C и не встречающиеся в D
18 русские буквы множество, содержащее буквы, имеющиеся в A или общие для B и C, но не встречающиеся в D
19 шестнадцатеричные цифры множество, содержащее все цифры, общие для A и B, а также все цифры, являющиеся общими для C и D
20 латинские буквы множество, содержащее буквы из множества A, не содержащиеся в B, а также все общие для C и D
21 десятичные цифры множество, содержащее цифры, имеющиеся в A или в B или являющиеся общими для C и D
22 прописные русские буквы множество, содержащее буквы, общие для A и B, но не являющиеся общими для C и D
23 шестнадцатеричные цифры множество, содержащее цифры из A, не встречающиеся в B и не являющиеся общими для C и D
24 строчные русские буквы множество, содержащее все буквы из A и все буквы из B, но не содержащего букв, являющихся общими для C и D
25 десятичные цифры множество, содержащее цифры, имеющиеся в каждом из множеств A, B, C, и D
26 прописные латинские буквы множество, содержащее все буквы из A, не являющиеся общими для B, C и D
27 шестнадцатеричные цифры множество, содержащее цифры, имеющиеся в A и все цифры, являющиеся общими для B, C и D
28 строчные латинские буквы множество, содержащее буквы, общие для множества A и любого из множеств B, C и D
29 десятичные цифры множество, содержащего цифры, общие для цифр из A, не встречающихся в B, с одной стороны, и любых цифр из C и D – с другой
30 цвета радуги множества, содержащего цвета, имеющиеся в A, также одновременно в B и C и все цвета из D
31 шестнадцатеричные цифры множество, содержащее цифры, имеющиеся во множествах A или C, но отсутствующие в B или D
32 русские буквы множество, содержащее буквы, имеющиеся в любом из множеств A, B, C, но отсутствующие в D
33 десятичные цифры множество, содержащее цифры, общие для множеств A и B, но не встречающиеся ни в C, ни в D
34 латинские буквы множество, содержащее все буквы множества A, которых нет во множествах B, C, или D
35 шестнадцатеричные цифры множество, содержащее цифры, имеющиеся в A или в B, но отсутствующие и в C, и в D
36 строчные русские буквы множество, содержащее буквы, общие для множеств A, B, C и не встречающиеся в D
37 десятичные цифры множество, содержащее цифры из A, не являющиеся общими для множеств B и C и не встречающиеся в D
38 прописные русские буквы множество, содержащее буквы, имеющиеся в A или общие для B и C, но не встречающиеся в D
39 шестнадцатеричные цифры множество, содержащее все цифры, общие для A и B, а также все цифры, являющиеся общими для C и D
40 латинские буквы множество, содержащее буквы из множества A, не содержащиеся в B, а также все общие для C и D
41 десятичные цифры множество, содержащее цифры, имеющиеся в A или в B или являющиеся общими для C и D
42 русские буквы множество, содержащее буквы, общие для A и B, но не являющиеся общими для C и D
43 шестнадцатеричные цифры множество, содержащее цифры из A, не встречающиеся в B и не являющиеся общими для C и D
44 латинские буквы множество, содержащее все буквы из A и все буквы из B, но не содержащего букв, являющихся общими для C и D
45 десятичные цифры множество, содержащее цифры, имеющиеся в каждом из указанных множеств
46 строчные латинские буквы множество, содержащее все буквы из A, не являющиеся общими для B, C и D
47 шестнадцатеричные цифры множество, содержащее цифры, имеющиеся в A и все цифры, являющиеся общими для B, C и D
48 прописные латинские буквы множество, содержащее буквы, общие для множества A и любого из множеств B, C и D
49 десятичные цифры множество, содержащего цифры, общие для цифр из A, не встречающихся в B, с одной стороны, и любых цифр из C и D – с другой
50 цвета радуги множества, содержащего цвета, имеющиеся в A, также одновременно в B и C и все цвета из D
Контрольные вопросыКакой объём памяти нужно выделить под массив-результат?
Почему не рекомендуется выделять под результат минимальную память и заказывать её заново при добавлении в множество каждого очередного элемента?
Можно ли сэкономить память, если обрабатывать множества не попарно, а все четыре сразу?
Какова временная сложность получения результата одновременной обработкой четырёх множеств?
Какая временная сложность получилась у вас? Можно ли считать ваш алгоритм оптимальным?
Представление множества отображением на универсумЕсли элементы универсума упорядочить, т. е. представить в виде последовательности U = <u0,u1, u2… um-1>, то любое его подмножество A ⊆ U может быть задано вектором логических значений C = <c0, c1, c2 … cm-1>, где ci = {ui ∈ A}, или вектором битов
ci = 1, ui∈A0, ui∉AТакой способ представления множеств в памяти имеет практическое значение, если мощность универсума m = |U| не очень велика и существует простая функция f: U → [0 … m-1] отображения элемента множества в соответствующий ему порядковый номер бита.
Так, например, если U — множество десятичных цифр, подходящей функцией будет f(a) = a – '0', где a — символьная переменная с кодом цифры, поскольку известно, что коды цифр образуют монотонную последовательность. Аналогично, для множества прописных латинских букв можно взять f(a) = a – 'A'. Для шестнадцатеричных цифр, коды которых образуют два интервала, функция будет сложнее: f(a) = a ≤ '9' ? a –'0' : a – 'A' + 10. В общем случае можно работать с полным множеством символов, положив m = 256 и f(a) = a.
Операции над множествами в форме вектора битов сводятся к логическим операциям над соответствующими битами множеств. Для вычисления объединения A ∪ B следует выполнить a[i] || b[i], для пересечения A ∩ B — a[i] && [b[i], для разности A \ B — a[i] && !b[i] для всех битов от i = 0 до i = m–1. Следовательно, временная сложность двуместной операции с множествами A и B в форме вектора битов будет O(m), что при фиксированном m соответствует O(1), т. е. не зависит от мощности этих множеств.
Для получения вектора битов bA из строки символов A следует заполнить вектор bA нулями, а затем установить в 1 биты, соответствующие каждому символу из A:
for (i = 0; i < strlen(A); i++) bA[f(A[i]) = 1.
Обратное преобразование очевидно:
for (i = k = 0; i < m; i++) if (bA[i]) A[k++] = f-1(i),
где f-1(i) — функция, обратная для f(a). Так, если f(a) = a – '0', то f-1(i) = i + '0'.
Использование массива битов в качестве промежуточной памяти при работе с элементами множества — самый простой способ устранить дубликаты.
Вектор битов может быть представлен в памяти в компактной форме — форме машинного слова, в качестве которого на языке С++ могут использоваться переменные типа int или long. Для таких переменных в языке предусмотрены поразрядные логические операции:
логическое сложение (поразрядное «ИЛИ») A | B, реализующее объединение множеств A ∪ B;
логическое умножение (поразрядное «И») A & B — пересечение A ∩ B;
поразрядное сложение по модулю 2 (исключающее «ИЛИ», сравнение кодов) A ^ B — симметрическая разность A ⊕ B = (A ∪ B) \ (A ∩ B);
инвертирование ~A, соответствующее Ā — дополнению до универсума.
Операции над множествами в форме машинного слова выполняются за один шаг алгоритма независимо от мощности множеств, т. е. имеют временную сложность O(1). Например, вычисление E = (A ∪ B ∩ C) \ D реализуется оператором wE = (wA | wB & wC) & ~wD, где wA, wB, wC, wD — машинные слова, хранящие соответствующие множества.
Способ применим, если размер универсума m не превосходит разрядности переменной (8 для char, 16 для short, 16 или 32 для int, 32 для long). Если m > 32, можно использовать несколько слов. Если m не равно 32 (16 или 8), часть битов слова не используется. Обычно это не вызывает проблем. Исключение: если переменная сравнивается с нулём для выявления пустого множества, нужно, чтобы неиспользуемые биты содержали 0.
Недостаток способа — в отсутствии удобного доступа к каждому биту машинного слова, как к элементу массива. Вместо этого приходится генерировать множество из одного элемента {a} сдвигом 1 на f(a) битов влево. Далее с помощью поразрядного «ИЛИ» можно добавить элемент в множество, а с помощью поразрядного «И» — проверить его наличие в нём. Так, для преобразования множества из строки символов в машинное слово можно использовать алгоритм
wA = 0;
for ( i = 0; i < strlen(A); i++ ) wA |= (1 ≪f(A));
Примечание: если программа пишется в оболочке Borland C++ 3.1, где разрядность данных int — 16, а мощность универсума больше (переменная wA имеет тип long), вместо константы 1 следует использовать 1L.
Для обратного преобразования — из машинного слова в строку символов — удобнее использовать сдвиг слова вправо и умножение на 1:
for ( i = k = 0; i < m; i++) if ( (wA ≫ i) & 1) A[k++] = f-1(i).
Отметим, что элементы массива битов нумеруются справа налево, а биты машинного слова — слева направо. Поэтому, если для массива битов и для машинного слова используется одна и та же функция отображения f(a), порядок битов в этих структурах данных будет противоположный.
Практикум по темеСоставить и отладить программу, реализующую обработку множеств, представленных в виде отображения на универсум.
Реализовать обработку множеств, представленных массивами битов. Можно использовать ранее созданную программу, добавив в неё преобразование множеств из строк символов в массивы битов, обработку этих массивов и выдачу результата. Результат должен быть выдан в форме набора элементов множества.
Реализовать обработку множеств с использованием машинных слов.
Контрольные вопросы
Какова временная сложность обработки множеств в случае представления их массивами битов?
Отличается ли от неё оценка временной сложности обработки машинных слов?
Можно ли получить выгоду, обрабатывая множества попарно?
Можно ли считать отображение на универсум универсальным приёмом, применимым для любых задач?
1.3. Генерация тестовГенерация последовательности всех подмножеств заданного множестваПодача на вход алгоритма последовательности всех подмножеств некоторого множества X может потребоваться для полного тестирования алгоритма или для решения задачи полным перебором в случаях, когда эффективного алгоритма не существует. Если мощность множества |X| = n, мощность множества всех его подмножеств — булеана (общее количество тестов) |2X| = 2n.
Если n ≤ 32, последовательность подмножеств проще всего получить в форме машинных слов по очевидному алгоритму:
for ( w = 0; w < 2n; w++) yield(w).
Здесь и далее yield(w) — некоторая функция, использующая множество w.
Для практических целей часто бывает удобнее, чтобы каждое подмножество в последовательности отличалось от предыдущего появлением или исчезновением ровно одного элемента (n-битный код Грея). Такую последовательность можно получить небольшой модификацией указанного выше алгоритма:
for ( i = 0; i < 2n; i++) { w = i ^ (i ≫ 1); yield(w); }.
Генерация перестановокНекоторые алгоритмы требуют подачи на вход полного множества X в виде последовательности, отличающейся порядком расположения элементов. Пример такого алгоритма — проверка двух графов одинаковой мощности на изоморфизм, заключающаяся в подборе такой нумерации вершин второго графа, чтобы его рёбра совпали с рёбрами первого графа. Функция Neith()генерирует все перестановки множества чисел от 1 до n в виде последовательности, в которой на каждом шаге меняются местами два смежных элемента.
inline void Swap( int &p, int &q) { int r = p; p = q; q = r; }
void Neith( int n)
{ int *X = new int[n], *C = new int[n], *D = new int[n], i, j, k, x;
for (i = 0; i < n; i++) // Инициализация
{ X[i] = i + 1; C[i] = 0; D[i] = 1; }
yield (X);
C[n – 1] = –1; i = 0;
while ( i < n – 1 ) // Цикл перестановок
{i = 0; x = 0;
while (C[i] == (n – i – 1))
{ D[i] = !D[i]; C[i] = 0; if (D[i]) x++; i++; }
if (i < n – 1) // Вычисление позиции k и перестановка смежных{ k = D[i]? C[i] + n : n – i – C[i] + x – 2; Swap( X[k], X[k + 1]); }
yield (X);
C[i]++;
}
}.
Генерация случайного подмножестваЕсли тестирование алгоритма ведётся вручную, его выполняют не полным перебором, а подачей на вход алгоритма некоторого разумного количества случайных тестов, генерацию которых тоже можно поручить машине. Для получения случайного машинного слова можно использовать функцию rand() из стандартной библиотеки stdlib. Функция возвращает псевдослучайное целое в интервале 0…32767. Случайное слово из n битов можно получить, выделив его из возвращаемого значения:
w = rand()%2n
или просто положить w = rand() и игнорировать лишние биты.
Для получения слова типа long можно использовать функцию дважды и объединить возвращаемые значения:
w = (long) (rand() ≪ 16) | rand().
Массив случайных битов получить ещё проще:
for ( i = 0; i < n; i++) X[i] = rand() % 2.
Следует отметить, что датчик rand() даёт не случайные, а псевдослучайные числа. При каждом новом запуске программы последовательность этих чисел будет повторяться. Это очень удобно для отладки, но когда отладка закончена, в начало функции main() нужно вставить строку srand(time(NULL)), которая обеспечит запуск датчика со случайной точки, зависящей от текущего времени. Время запрашивается функцией time() из стандартной библиотеки time.h.
Получить случайную строку тоже проще всего генерированием последовательности битов:
int k = 0;
for ( i = 0; i < m; i++) if (rand()%2) S[k++] = f(i).
Результат — строка символов S — множество со случайной мощностью k ∈ [0…m – 1].
Все рассмотренные генераторы создают множества, в которых каждый элемент универсума появляется с вероятностью 0,5. Может получиться и пустое, и полное множество, но в среднем мощность получается близкой к m/2. Если требуется получать множества почти пустые или почти полные, нужно сделать так, чтобы вероятности появления 0 или 1 различались. Так, в общем случае генератор массива битов может выглядеть так:
for ( i = 0; i < m; i++) X[i] = (rand()%p > q).
В этом генераторе вероятность появления 1 зависит от соотношения значений констант p и q. Так, например, при p = 5 датчик будет давать с равной вероятностью элементы множества {0, 1, 2, 3, 4}, и при q = 3 вероятность генерации 1 будет 0,2, а при q = 0— 0,8.
Случайное подмножество заданной мощностиВсе рассмотренные ранее датчики генерировали множество случайной мощности. Если же требуется случайное подмножество заданной мощности k, например, в форме массива, его иногда пытаются получить следующим алгоритмом:
for ( i = 0; i < k; i++ ) X[i] = rand() % m.
Этот способ не годится, потому что он даёт не множество, а последовательность, в которой возможны повторы, и их будет много, если k близко к m, т. е. фактическая мощность множества будет меньше заданного k.
Можно усовершенствовать этот алгоритм: повторять генерацию очередного элемента множества до тех пор, пока не кончатся совпадения с уже имеющимися. Способ рекомендуется при больших m(k ≪ m). Если же m не намного больше k, то с ростом k вероятность получить новый элемент множества очень быстро уменьшается, а при k = m алгоритм может вообще никогда не остановиться.
Способ, рекомендуемый для небольших m: сформировать в памяти для результата массив — универсум, на каждом шаге убирать сгенерированный элемент множества в его начало и разыгрывать оставшиеся. Результат будет получен за время O(k).
for ( i = 0; i < m; i++ ) X[i] = i + 1; // Формирование универсума {1 … m}
for ( i = 0; i < k; i++) // Генерация подмножества мощностью k
{ p = rand() % (m – i); // Случайный выбор среди оставшихсяif (p) Swap ( X[ i + p ], X [ p] ); } // Если p ≠ 0, обменять местами.
Результат — первые k элементов массива X. Способ легко приспособить для генерации последовательности подмножеств нарастающей мощности: использовать массив X в качестве теста после каждого добавления в него очередного элемента. Если взять k = m–1, получается алгоритмгенерации случайной перестановки. Без ограничения общности он может использовать очередную перестановку для генерации следующей, не требуя в этом случае для новой перестановки обязательного перезапуска датчика случайных чисел.
Практикум по теме
Преобразовать ранее созданные программы так, чтобы исходные множества генерировались автоматически.
Контрольные вопросыМожно ли применить для тестирования вашего алгоритма генератор множества всех подмножеств?
Какой из способов генерации случайного множества вы считаете самым удобным?
Целесообразно ли для вашего варианта обработки множеств применять несимметричный генератор тестов?
Можно ли применять для генерации подмножества заданной мощности генерацию случайных битов с остановкой по достижении нужного их количества?
1.4. Измерение времени решения задачи с помощью ЭВМИзмерение времени решения задачи для разных объёмов исходных данных — важная составляющая процедуры тестирования любой программы. Для измерения времени можно применять специальные приборы (секундомер) или средства, предоставляемые системой программирования (профайлер). Но для исследования алгоритма удобнее всего организовать измерение времени в самой программе тестирования, используя для этого средства, предоставляемые системой программирования.
Использование функции clock()Функция clock( ) возвращает значение счётчика тиков внутренних часов ПЭВМ как 32-битное целое типа clock_t, что соответствует unsignedlong. Для измерения времени обработки множеств нужно вызвать функцию clock () в момент, когда в памяти готовы исходные данные, и в момент, когда получен результат, а затем найти разность двух отсчётов.
Каждый тик соответствует 1/50 с, т. е. 0,017 мс, следовательно, о какой-либо точности измерения времени функцией clock( ) можно говорить, если измеряемый интервал времени — порядка нескольких секунд. Чтобы добиться этого, измеряемый процесс приходится многократно повторять (до 1 000 000 раз и даже более). Полученную разность отсчётов времени можно затем разделить на количество повторений.
Чтобы измерить время таким способом, важно приспособить процесс вычислений к многократному повторению, выполнив два условия:
исходные множества не должны искажаться, их память нельзя использовать для получения результата вычислений;
не должно быть «утечки памяти» — выделения в динамической памяти большего объёма, чем освобождается после вычислений. Так, в варианте со списками до начала вычислений следует освобождать память из-под всех результатов, полученных предыдущим проходом.
Другие функции стандартной библиотеки time.h (например, функциюtime( ) и т. п.) использоватьнетсмысла, поскольку источник информации о времениу них всех один, и точность измерения у них не больше, чем у clock( ).
Для измерения времени обработки множеств нужно вызвать функцию clock()в момент, когда в памяти готовы исходные данные, и в момент, когда получен результат, а затем найти разность двух отсчётов.
Практикум по темеДобавить в ранее созданные программы с генерацией исходных данных измерение времени вычисления множества по четырём исходным отдельно для каждого из способов представления множеств в памяти. Измерить время и зафиксировать результат для отчёта.
Контрольные вопросыКак правильно организовать эксперимент для сравнения фактического быстродействия разных способов представления множеств?
Сколько раз нужно повторять тест при измерении времени его выполнения функцией clock( )?
1.5. Множество как объектЕсли некоторая структура данных, например, массив, используется как реализация множества, это означает, что программист просто устанавливает для себя некоторые правиладля работы с этим массивом и последовательно их придерживается. Часто большего и не требуется. Однако можно рассматривать множество как абстрактную структуру данных — область памяти, доступ к которой возможен только через некоторый интерфейс, т. е. набор функций, специально созданных для работы с этой памятью. Язык С++ поддерживает работу с абстрактными данными через механизм классов: абстрактная структура данных определяются как класс, в котором задаются как данные, так и связанные с ними операции. Определение класса позволяет расширить язык C++, включив в него множество как пользовательский тип данных.
Рассмотрим пример — класс для работы с множеством, представленным массивом символов (строкой):
class Set {private: // Закрытая часть класса — данные
static int N; // мощность универсума
int n; // мощность множества
char S, *A; // тег и память для множества
public: // Открытая часть — функции для работы с множеством
Set operator |(const Set&) const; // объединение
Set operator &(const Set&) const; // пересечение
Set operator ~() const; // дополнение до универсума
void Show(); // вывод множества на экран
int power(){ return n; } // получение мощности
Set(char); // конструктор множества
Set(); // ещё конструктор — по умолчанию
Set(const Set&); // конструктор копии
Set operator = (const Set&); // оператор присваивания
~Set(){ delete [ ]A; } // деструктор
};
Имя класса Set — это имя нового типа данных. С его помощью мы будем объявлять в программе множества-объекты.
Память для множества находится в закрытой части класса и доступна через член A — указатель на символы. Размер памяти не определён. Кроме этого, в закрытую часть помещены вспомогательные переменные-члены: мощность универсума N, текущая мощность множества n и символ-тег S, с помощью которого мы сможем различать объекты-множества. Мощность универсума N объявлена со спецификатором «static». Это означает, что все объекты класса Set будут использовать единственную копию этой переменной. Переменная N быть дополнительно объявлена вне всех функций, чтобы ей была выделена память. При этом рекомендуется установить и её значение:
int Set ∷ N = 26; // Мощность универсума для множества латинских букв.
В открытой части класса объявлены функции-члены, с помощью которых в программе-клиенте можно работать с множеством. Каждая функция-член имеет в качестве обязательного аргумента объект, для которого она вызывается. Данные-члены из закрытой части класса доступны в ней как обычные глобальные переменные, и их тоже не нужно передавать как аргументы. Всё это позволяет свести количество аргументов функций-членов к минимуму или даже совсем от них отказаться, не засоряя при этом пространство глобальных имён.
Для работы с множествами-массивами предполагается использовать такой же синтаксис, как для машинных слов. С этой целью функции объединения, пересечения и дополнения множеств объявлены с именами, содержащими ключевое слово «operator», после которого следует знак соответствующей операции. Операции языка С++ «|», «&» и «~» определены так, чтобы их можно было использовать в выражениях, состоящих из данных типа Set. Такой приём называется перегрузкой операций. Чтобы эти операции действительно можно было использовать в выражениях, функции объявлены так, чтобы была обеспечена совместимость со встроенными операциями языка С++: все функции возвращают объект типа Set, а двуместные операции в качестве аргумента (второго, потому что первый — это сам объект) имеют константную ссылку на объект типа Set. Функции не меняют объект, для которого вызываются. Для контроля за этим в каждом из объявлений после списка параметров помещён спецификатор «const».
Вот так может выглядеть определение двуместной операции «пересечение»:
Set Set :: operator &(const Set& B) const
{ Set C;
for(int i = 0; i < n; i++) {
for (int j = 0; j < n.B; j++)
if (A[i] == B.A[j]) C.A[n.C++] = A[i];
}
C.A[n.C] = 0; // ограничитель строки
return C;
}
Функции объявляется множество «C», которое конструктор по умолчанию оставляет пустым. Затем в нём формируется результат пересечения основного объекта и множества «B». Поскольку для этого используется двойной цикл по мощности множеств, временная сложность операции — квадратичная.
Операция объединения множеств «|» реализуется похожим алгоритмом.
Set Set :: operator |(const Set & B)const
{ Set C;
memcpy(C.A, A, n); C.n = n;
for(int i = 0; i < B.n; i++) {
int f = 1;
for (int j = 0; j < n; j++)
if(B.A[i] == A[j]) f = 0;
if(f) C.A[C.n++] = B.A[i];
}
C.A[C.n] = 0;
return C;
}
В результат копируются элементы исходного множества, затем в него добавляются недостающие элементы из «B».
Операция вычисления дополнения может быть реализована так:
Set Set :: operator ~ ( ) const
{ Set C;
for (char c = 'A'; c <= 'Z'; c++) {
int f = 1;
for (int j = 0; j < n; j++)
if (c == A[j]) { f = 0; break; }
if (f) C.A[C.n++] = c;
}
C.A[C.n] = 0;
return C;
}
Здесь в качестве одного из операндов выступает множество-универсум. Результат — элементы универсума, которых нет в исходном множестве.
Поскольку количество повторений цикла по элементам универсума постоянно, временная сложность операции — O(n). Однако, если учесть, что мощность универсума не может быть меньше мощности его подмножеств: |U|  ≥ n,более точной будет оценка O(|U|.n), более пессимистическая по сравнению с O(n2).
Разумеется, нельзя обойтись без функции Show() для вывода множества на экран: это единственный способ увидеть результат обработки, поскольку сами множества из вызывающей программы недоступны.
void Set :: Show()
{ cout << endl << S << " = [" << A << "]"; }
Для определения мощности множества нужна специальная функция power(). Эта функция просто возвращает значение закрытой переменной n, в которой другие функции поддерживают значение текущей мощности множества. Поскольку функция не только объявлена, но и определена внутри класса, она по умолчанию является встроенной. К объявлению функции неявно добавляется спецификатор «inline». Это означает, что никакой функции не создаётся, вместо этого в каждую точку вызова просто подставляется значение закрытой переменной n. Таким образом, запрет на доступ к n обходится без всяких дополнительных расходов на вызов функции.
Все функции-члены, кроме перечисленных выше, объявлять и определять не обязательно, компилятор делает это автоматически. Но в данном случае автоматически определяемые функции не подходят.
Так, при создании объекта класса Set выделяется память, после чего вызывается функция-конструктор Set(). По умолчанию эта функция — пустая, она ничего с памятью не делает, и использовать такой объект невозможно. Поэтому конструктор надо определить явно. Сделаем так, чтобы он создавал пустое множество латинских букв, представленное строкой символов:
Set :: Set(): n(0), S = '0'
{ A = new char[N+1]; A[0] = 0; }
В этом примере одни переменные инициализируются в заголовке, другие — в теле конструктора. Оба способа можно комбинировать произвольным образом, но нужно учитывать, что порядок инициализации переменных полностью определяется порядком их объявления в классе и не может быть изменён. В данном примере значение переменной N используется для создания строки A, поэтому важно, что переменная N объявлена в классе раньше, чем указатель A. Массив символов объявляется на 1 символ длиннее мощности универсума, чтобы резервировать место под ограничивающий нуль. Поскольку строка должна быть пустой, ограничивающий нуль записывается в её начало. Инициализировать остальную часть массива не обязательно.
Если требуется иметь несколько способов создания объекта, для каждого способа объявляется свой конструктор, отличающийся от других типом и/или количеством аргументов. В примере объявлен конструктор с одним символьным аргументом. Это может быть конструктор, генерирующий случайную строку латинских букв. Аргумент используется для инициализации тега. С помощью датчика случайных чисел генерируется N битов, и для каждого единичного бита соответствующий ему элемент добавляется в множество. Одновременно подсчитывается фактическая мощность множества n. По окончании генерации в строку добавляется ограничитель. Сгенерированное множество выводится на экран.
Set :: Set(char s): S(s), n(0)
{ A = new char[N+1];
for (int i = 0; i < N; i++)
if (rand() % 2) A[n++] = i + 'A';
A[n]=0;
cout << endl << S << " = [" << A << "]";
}
Следующие две функции-члена — конструктор копирования и перегрузку присваивания — определяют редко. Дело в том, что обе эти функции по умолчанию копируют один объект в другой по принципу «байт в байт». Если ничего другого не требуется, определять эти функции не нужно, т. к. компилятор наверняка сделает это лучше. В нашем же случае такое копирование не годится, потому что в классе есть указатель на дополнительную память, и копирование приведёт к тому, что указатели A в обоих объектах будут указывать на одну и ту же строку.
Конструктор копирования имеет единственный аргумент — константную ссылку на объект того же класса. Определить конструктор можно так:
Set :: Set(const Set & B)
{ N = B.N; S = B.S; n = B.n;
A = new char[N+1];
memcpy(A, B.A, N+1);
}
Здесь переменные N, S и n копируются обычным способом, а для указателя A создаётся новая строка, куда затем копируется содержимое старой.
Функция-член для перегрузки присваивания отличается от копирования тем, что объект в левой части оператора уже существует. Более того, он может совпадать с аргументом (самоприсваивание). Поэтому первое, что функция должна сделать — проверить это. Затем текущий объект уничтожается и создаётся новый. В нашем случае это делать не надо, можно ограничиться просто переносом содержимого строки в имеющуюся память. Поскольку результат операции присваивания может быть использован в выражении, например, в цепочке присваиваний, функция должна возвращать значение объекта, для которого она вызвана. Это делается с помощью встроенного указателя «this». Копировать тег нет смысла: устанавливается некоторое условное значение «R» (от слова «result»).
Set Set :: operator = (const Set& B)
{ if (this != &B)
{ N = B.N; memcpy(A, B.A, N+1); S = 'R'; }
return *this;
}
Конструктор копирования используется при инициализации объекта содержимым другого объекта в момент объявления, а также при передаче аргумента в функцию как параметра по значению и при возврате объекта как результата работы функции. Функция перегрузки присваивания вызывается соответствующим оператором. Бывают ситуации, когда эти функции в программе не нужны. Чтобы исключить трудно выявляемую ошибку в программе из-за использования функций по умолчанию, рекомендуется объявить ненужные функции в закрытой части класса. Можно даже не определять их. Невольное создание в программе ситуации, когда такая функция вызывается, будет ошибкой, выявляемой компилятором.
Последняя функция-член в объявлении класса — это деструктор, который автоматически вызывается при уничтожении объекта. В нём указано дополнительное действие, которое нужно выполнить перед освобождением памяти из-под объекта: уничтожить строку A. Поскольку деструктор определён внутри класса, он, как и power(), тоже является встроенной функцией. Впрочем, для деструктора это не важно. Его всё равно нельзя использовать как обычную функцию, например, получить его адрес. Деструктор вызывается явно в операторе «delete» или неявно — при выходе из блока, в котором объект был определён. Объекты уничтожаются в порядке, обратном порядку их создания.
Программа, использующая объекты класса Set (программа-клиент), может выглядеть так:
#include <string.h>
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;
#include "Set.h"
int Set ∷ N = 26; // определение статического члена класса
const long q0 = 100000; // количество повторений цикла времени
void main()
{ srand(time(NULL));
Set A('A'), B('B'), C('C'), D('D'), E;
clock_t begin = clock();
for(long q =0; q < q0; q++)
{ E = (A | B) & (C & ~D); }
clock_t end = clock();
E.Out();
cout << " Middle power =" <<
(A.power() + B.power() + C.power() + D.power() + E.power())/5<<
" Time=" << end – begin<< " / " << q0;
_getch();
}
В программе определяются пять множеств. Для исходных множеств A, B, Cи D используется конструктор, генерирующий случайное множество с выводом на экран результата. Множество E генерируется конструктором по умолчанию как пустое. Затем множество вычисляется с использованием перегруженных операций, и результат выводится на экран. Далее вычисляются и выводятся средняя мощность всех множеств и время решения задачи.
Объявление класса Set и определения всех функций-членов находятся в подключаемом модуле «Set.h». Определение статического члена — переменной N — помещено сразу после модуля. На самом деле оно является его частью. В самой программе никакой информации об устройстве модуля «Set.h» не имеется. Чтобы использовать другой способ хранения множеств в памяти, достаточно просто подменить модуль.
Вычисление множества E выполняется одним оператором присваивания, как в варианте для машинных слов. Но временная сложность этого вычисления не будет константной, она определяется функциями, реализующими операции над множествами и, следовательно, по-прежнему зависит от способа их хранения в памяти.
Результат работы программы может выглядеть так:

Практикум по темеПреобразовать ранее созданные программы так, множества были объектами некоторого класса, а операции над ними — методами этого класса.Сделать по крайней мере два варианта программы с разными способами представления множеств в памяти, например, с помощью массивов элементов и с помощью списков. Добиться, чтобы функция main( ) во всех вариантах была одинакова.
Контрольные вопросыКакую выгоду можно получить от применения объектов в программе обработки множеств?
Как влияет применение объектов на время выполнения программы
Отчёт по темеПо теме должен быть оформлен сводный отчёт следующего содержания:
Задание на обработку множеств.
Формализация задания.
Контрольные тесты.
Временная сложность (ожидаемая и фактическая) для четырёх способов представления множеств.
Результаты измерения времени обработки каждым из способов, с пометкой, наблюдалась ли зависимость времени обработки от исходных данных.
Выводы о результатах испытания способов представления множеств в памяти и рекомендации по их применению в программах для ЭВМ.
Список использованных источников.
Приложение: исходные тексты всех созданных программ (на машинном носителе).
2. ДЕРЕВЬЯДерево в общем случае — это связный граф без циклов, абстрактная структура данных, представляющая собой множество вершин, или узлов, на которых определены попарные связи — рёбра. Мы будем рассматривать частный случай — корневые упорядоченные деревья. У таких деревьев рёбра становятся ориентированными, поскольку у любой последовательности попарно связанных вершин — пути, включающем корень, появляется направление от корня или к корню. Для некоторогоузла v все вершины дерева на пути в корень, находящиеся ближе к корню, называется предками, а дальше от корня — потомками. Из пары узлов, связанных ребром, узел ближе к корню — отец, дальше от корня — сын. У каждогоузла может быть несколько сыновей, которые называются братьями, но только один отец. Корень — это единственный в дереве узел, у которого нет отца. Узлы, у которых нет сыновей, называются листьями.
Количество ребёр на пути из корня в узел дерева называется глубиной узла, количество ребёр на самом длинном пути в лист — высотой. Высота дерева — это высота его корня. Разность между высотой дерева и глубиной узла — это уровень узла.
Дерево упорядочено, если упорядочены сыновья любого его узла. Из корневых упорядоченных деревьев наиболее часто используются двоичные, или бинарные. Каждый узел двоичного дерева может иметь не более двух сыновей — левого и правого, причём единственный сын узла — обязательно левый или правый. Более сложный вариант — троичное дерево, где у каждого узла — не более трёх сыновей: левый, средний, правый — в любой комбинации. Каждый из сыновей может рассматриваться как корень соответствующего поддерева, возможно, пустого.
Для представления дерева в памяти можно предложить естественный способ — разветвляющийся список. Узлы дерева — объекты, связи между которыми осуществляются через указатели. Для создания дерева достаточно объявить класс «узел дерева», членами которого должны быть указатели на узлы того же типа: «левый» и «правый» (у троичного дерева — «левый», «средний» и «правый»). В узле могут быть и другие данные-члены. Минимально необходимым является тег — метка или номер узла, с помощью которого можно различать узлы в процессе их обработки. Однако для работы с деревом в целом удобнее иметь особый класс «дерево», в котором собираются данные, относящиеся к дереву в целом и функции-члены для работы с деревом. Чтобы эти функции имели доступ к данным узла, достаточно объявить класс «дерево» дружественным для класса «узел».
//Класс «узел дерева»
class Node { char d; //тег узла
Node * lft;// левый сын
//Node * mdl;средний сын (если нужно)
Node * rgt;// правый сын
public:
Node(){ lft=0; rgt=0; } // конструктор узла
~Node(){ if(lft) delete lft; // деструктор (уничтожает поддерево)
if (rgt) delete rgt; }
friend class Tree;// дружественный класс «дерево»
} ;
// Класс «дерево в целом»
class Tree
{Node * root;// указатель на корень дереваchar num, maxnum;//счётчик тегов и максимальный тег
int maxrow, offset;//максимальная глубина, смещение корня
char ** SCREEN;// память для выдачи на экран
void clrscr();// очистка рабочей памяти
Node* MakeNode(int depth);// создание поддерева
void OutNodes(Node * v, int r, int c); // выдача поддерева
Tree (const Tree &);// фиктивный конструктор копии
Tree operator = (const Tree &) const;// фиктивное присваивание
public:
Tree(char num, char maxnum, int maxrow);//конструктор пустого дерева
~Tree();
void MakeTree() // ввод — генерация дерева
{ root = MakeNode(0); }
bool exist() { return root != NULL; } // проверка «дерево не пусто»
int DFS();// обходы дерева
int BFS();
void OutTree();// выдача на экран
};
Кроме данных, в классе Tree объявлены скрытые функции-члены. Это — вспомогательные функции, которые не входят в интерфейс и предназначены только для вызова из других функций-членов. А конструктор копирования и перегрузка присваивания сделаны скрытыми умышленно: попытка создать в программе ситуацию, в которой эти функции могут быть вызваны, приведут к ошибке на этапе компиляции «нарушение защиты».
Конструктор дерева инициализирует параметры разметки и создаёт рабочую память — матрицу символов, необходимую для выдачи изображения дерева на экран.
Tree ::Tree(char nm, char mnm, int mxr):
num(nm), maxnum(mnm), maxrow(mxr), offset(40), root(NULL)
{ SCREEN = new char * [maxrow];
for(int i = 0; i < maxrow; i++) SCREEN[i] = new char[80]; }
Деструктор дерева уничтожает матрицу символов и запускает деструктор узла для корня.
Tree :: ~Tree( ) { for(int i = 0; i < maxrow; i++) delete [ ]SCREEN[i];
delete [ ]SCREEN; delete root; }
Обратите внимание на то, как создаётся и уничтожается матрица.
2.1. Обходы дерева как рекурсивной структуры данныхЧтобы обработать каким-либо образом множество узлов дерева, дерево нужно обойти. Каждый узел дерева является корнем поддерева, а его сыновья — тоже корнями поддеревьев. Поэтому алгоритм обхода, запускаясь для узла, должен обработать информацию в узле и запустить такой же алгоритм для каждого из непустых поддеревьев. Существуют три способа сделать это, отличающиеся лишь порядком шагов.
Прямой обход
Обработать узел.
Посетить в прямом порядке каждого сына.
Обратный обход
Посетить в обратном порядке каждого сына.
Обработать узел.
Внутренний, или симметричный обход
Посетить во внутреннем порядке левого сына.
Обработать узел.
Посетить во внутреннем порядке правого сына (остальных сыновей).
Минимальная обработка узла может состоять в присвоении соответствующему полю номера в порядке посещения (разметка), или, если номера уже имеются, в выдаче их на экран или в формировании последовательности из номеров посещённых узлов. Очевидно, что не существует иных способов отличить один порядок обхода узлов от другого.
При разметке дерева в прямом порядке номер любого узла — наименьший, а при обратном — наибольший в соответствующем поддереве, а диапазон использованных номеров равен мощности поддерева. При разметке внутренним способом номер узла больше любого номера в левом поддереве и меньше любого номера в правом.
2.3. Создание дереваДля создания дерева в памяти тоже применяется алгоритм обхода. Первым шагом этого алгоритма является проверка необходимости создания узла.
Если ответ положительный, узел создаётся, и в нём заполняются информационные поля. В частности, может быть выполнен шаг разметки. Далее заполняются поля указателей на каждого сына: для получения значения указателя алгоритм запускается рекурсивно. Результат — указатель на вновь созданный узел или нуль, если узел не создан.
Проверка необходимости создания узла может быть выполнена тремя способами:
Запрос на ввод с клавиатуры. Приглашение ко вводу может содержать какую-либо информацию о месте предполагаемого узла в дереве. Ожидаемый ответ — «да» или «нет» (1 или 0, Y или N, и т. п.). Вместо ответа «да» можно вводить информацию для размещения в узле, особый ввод, например, пустой, может означать «нет».
Чтение очередного элемента заранее заготовленной последовательности из массива, линейного списка или файла. Такая последовательность сама по себе тоже является способом размещения дерева в памяти, а алгоритм ввода просто преобразует её в форму разветвляющегося списка.
Обращение к датчику случайных чисел с целью генерации дерева. Датчик должен быть управляемым. Простой датчик с равновероятной выдачей 0 или 1 будет создавать пустые или очень маломощные деревья — из 1, 2, 3 узлов, т. к. вероятность того, что узел будет создан, очень быстро падает с ростом его глубины: для корня она составляет всего 0.5, для сыновей — 0.25 (0.52) и т. д. Нужен датчик, который бы обеспечивал вероятность создания корня близкую к 1 и уменьшал её с ростом глубины узла.
Пример такого датчика:
Y = depth < rand() % 6 + 1,
где depth — глубина узла: для корня она 0, для произвольного узла — на 1 больше, чем у отца. Очевидно, что для корня Y = 1, а для узла на глубине больше 5 — всегда 0.
Функция-член для генерации случайного дерева может выглядеть так:
Node * Tree :: MakeNode(int depth)
{ Node * v = NULL;
int Y = (depth < rand()%6+1)&&(num <= 'z');
// Вариант: cout ≪ "Node (" ≪ num ≪ ',' ≪ depth ≪ ")1/0: "; cin ≫ Y;
if (Y) {// создание узла, если Y = 1 v = new Node;
v->d = num++; // разметка в прямом порядке (= «в глубину»)
v->lft = MakeNode(depth+1);
// v->d = num++; //вариант — во внутреннем v->rgt = MakeNode(depth+1);
// v->d = num++;// вариант — в обратном }
return v;
}
Эта функция запускается из встраиваемой функции-члена MakeTree(), результат её работы присваивается полю root.
Вместо генерации случайного значения Y можно организовать ввод его с клавиатуры. Соответствующая альтернатива помещена в комментарий.
Функция создаёт дерево прямымобходом по той простой причине, что невозможно создать узел дерева, если не создан его отец. Но вот считать узел «пройдённым» можно когда угодно. Поэтому для разметки узлаа валгоритме можно использовать три точки (две из них закомментированы): до обхода поддеревьев, после левого поддерева и перед правым, и по окончании обхода поддеревьев. Нужный вариант разметки можно обеспечить, включив инициализацию в соответствующей точке и выключив — в остальных.
Значение глубины узла depth, необходимое для датчика, известно при входе в функцию и может быть использовано в любом месте. А вот данные, зависящие от поддеревьев: высота узла, количество листьев, количество потомков и т. п., могут быть известны только тогда, когда оба поддерева уже обработаны, т. е. они доступны только при обратном обходе.
2.2. Вывод изображения дерева на экран монитораЧтобы получить наглядное представление о способе разметки дерева, нужно вывести его на экран в виде диаграммы. Можно обойтись для этого текстовым режимом, если принять следующее соглашение. В середине первой строки текста вывести метку корня дерева. В следующей строке — расположить метки левого и правого сыновей в серединах левой и правой половины строки и т. д. Если дерево — троичное, метку среднего сына можно разместить прямо под корнем, и т. д., уменьшая смещение сыновей относительно корня в два раза по отношению к предыдущему ряду. Удобно воспользоваться рекурсивной функцией обхода дерева, которая выдаёт метку узла в некоторой точке экрана (r, c), а для сыновей добавляет 1 к номеру ряда и смещения к номеру столбца. Смещение удобно вычислять сдвигом некоторой константы offset на номер ряда, который совпадает с глубиной узла.
Для выдачи метки в нужную точку экрана можно использовать функцию позиционирования курсора gotoxy(r, c) из библиотеки conio.h, предварительно очистив экран функцией clrscr(). Но поскольку эти функции есть не во всех оболочках, можно обойтись без них, использовав промежуточную буферную память в виде матрицы символов, как это сделано ниже в примере.Для того, чтобы понять разметку дерева, достаточно вывести узлы 5–6 верхних уровней. Для улучшения читабельности картинки рекомендуется вместо числовых меток использовать буквы латинского алфавита.Функция-член для вывода изображения дерева на экран может выглядеть так:
void Tree :: OutTree()
{clrscr();
OutNodes(root, 1, offset);
for(int i=0; i<maxrow; i++)
{ SCREEN[i][79] = 0;
cout << endl << SCREEN[i];
}
cout << endl;
}
Она запускает закрытую функцию член clrscr(), которая готовит матрицу символов, заполняя её точками.
void Tree :: clrscr()
{ for(int i = 0; i < maxrow; i++)
memset(SCREEN[i],'.',80);
}
Далее выполняется закрытая функция OutNodes(), расставляющая метки вершин дерева в матрице символов.
void Tree :: OutNodes(Node * v, int r, int c)
{ if(r && c && (c<80)) SCREEN[r-1][c-1] = v->d; // вывод метки
if (r < maxrow) {
if (v->lft) OutNodes(v->lft, r+1, c-(offset>>r)); //левый сын
// if (v->mdl) OutNode(v->mdl, r+1, c);— средний сын (если нужно)
if (v->rgt) OutNodes(v->rgt, r+1, c+(offset>>r)); //правый сын
}
}
Затем матрица символов построчно выводится на экран.
2.4. Шаблоны классов для очереди и стека и нерекурсивные алгоритмы обхода дереваШаблон для класса «стек»
template <class Item> class STACK
{ Item * S; int t;
public:
STACK(int maxt)
{ S = new Item[maxt]; t = 0; }
int empty() const { return t==0; }
void push(Item item) { S[t++] = item; }
Item pop() {return (t? S[--t] : 0); }
};
Шаблон для класса «очередь»
template <class Item> class QUEUE
{Item * Q; int h, t, N;
public:
QUEUE(int maxQ): h(0), t(0), N(maxQ) { Q = new Item[maxQ+1]; }
int empty()const { return (h % N) == t; }
void put(Item item) { Q[t++] = item; t %= N; }
Item get() { h %= N; return Q[h++]; }
};
Нерекурсивный обход дерева способом «в глубину»
int Tree :: DFS()
{ const int MaxS=20; //максимальный размер стека
int count = 0;
STACK <Node *> S(MaxS); //создание стека указателей на узлы
S.push(root); // QUEUE <- v
while (!S.empty()) //Пока стек не пуст…
{ Node * v = S.pop(); // поднять узел из стекаcout << v->d<< '_'; count++; // выдать тег, счёт узлов
if (v->rgt) S.push(v->rgt); // STACK <- (правый сын)
if (v->lft) S.push(v->lft); // STACK <- (левый сын)
}
return count;
}
Замена стека очередью — нерекурсивный обход «в ширину»
int Tree :: BFS()
{ const int MaxQ=20; //максимальный размер очереди int count = 0;
QUEUE <Node *> Q(MaxQ); //создание очереди указателей на узлы
Q.put(root); // QUEUE <- root поместить в очередь корень дерева
while (!Q.empty()) //пока очередь не пуста
{ Node * v = Q.get();// взять из очереди,cout << v->d<< '_'; count++; // выдать тег, счёт узлов
if (v->lft) Q.put(v->lft); // QUEUE <- (левый сын)
if (v->rgt) Q.put(v->rgt); // QUEUE <- (правый сын)
}
return count;
}
Пример программы для создания случайного дерева, выдачи его на экран и обхода двумя способами с подсчётом мощности дерева
void main()
{ int n = 0;
Tree Tr('a', 'z', 8);
srand(time(NULL));
setlocale(LC_ALL, "Russian");
Tr.MakeTree();
if(Tr.exist()) {
Tr.OutTree();
cout << endl << "Обход в глубину: ";
n = Tr.DFS();
cout << " Пройдено узлов = " << n;
cout << endl << "Обход в ширину: ";
n = Tr.BFS();
cout << " Пройдено узлов = " << n;
}
else cout << "Дерево пусто!";
cout << endl << "=== Конец ===";
_getch();
}
Результат работы программы может выглядеть так:

Практикум по темеНаписать и отладить программу для работы с деревьями по предложенному преподавателем варианту индивидуального задания. Программа должна выводить на экран изображение дерева с разметкой его вершин, сделанной заданным способом, а под ним — последовательность меток вершин при обходе дерева и результат вычисления заданного параметра. Можно взять за основу учебный пример.
Сделать узел дерева и дерево в целом объектами соответствующих классов, а обходы дерева — методами для этого класса.
Объявить в классе «дерево» деструктор и все конструкторы, поддерживаемые по умолчанию. Сделать невозможным использование тех конструкторов, которые на самом деле не нужны. Сделать в тексте программы временные дополнения и убедиться, что это действительно так.
Варианты индивидуальных заданий к теме «Деревья»№ вари-анта Виддерева Разметка Способ обхода Что надо вычислить
1 двоичное обратная в глубину высоту дерева
2 двоичное прямая в ширину количество листьев
3 троичное обратная внутренний количество вершин, имеющих хотя бы одного потомка
4 троичное прямая в ширину общее количество вершин
5 двоичное симметричная в ширину количество вершин, имеющих не более одного потомка
6 двоичное обратная внутренний количество вершин на глубине больше 2
7 троичное ширинная в глубину количество вершин, имеющих ровно одного потомка
8 троичное обратная в ширину количество вершин, имеющих хотя бы одного потомка
9 двоичное прямая внутренний количество вершин на уровне не больше 2
10 двоичное симметричная в глубину количество вершин, имеющих не более одного потомка
11 троичное прямая в ширину высоту дерева
12 троичное обратная внутренний количество правых листьев
13 двоичное симметричная в глубину количество вершин на глубине не более 2
14 двоичное симметричная в глубину количество потомков у каждой из вершин
15 троичное прямая внутренний количество вершин, имеющих не более двух потомков
16 троичное обратная внутренний высоту левого поддерева для корня
17 двоичное обратная в глубину количество левых листьев
18 двоичное ширинная внутренний количество вершин на самом нижнем уровне
19 троичное глубинная внутренний количество вершин не на самом нижнем уровне
20 троичное обратная в глубину количество вершин, имеющих не более трёх потомков
21 двоичное прямая внутренний высоту правого поддерева для корня
22 двоичное обратная внутренний количество листьев на самом нижнем уровне, имеющем листья
23 троичное симметричная в глубину количество средних листьев
24 троичное прямая в ширину количество предков для каждой из вершин
25 двоичное обратная внутренний количество вершин, имеющих не более двух потомков
26 троичное симметричная в глубину количество листьев не на самом нижнем уровне, имеющем листья
27 троичное прямая в ширину высоту среднего поддерева для корня
28 двоичное обратная внутренний количество предков для каждой из вершин
29 двоичное обратная в глубину количество вершин на глубине не более 3
30 троичное симметричная в ширину количество вершин, имеющих не более двух потомков
31 двоичное симметричная в глубину количество вершин на глубине не более 2
32 двоичное симметричная в ширину количество потомков у каждой из вершин
33 троичное прямая в ширину высоту дерева
34 троичное обратная внутренний количество правых листьев
35 двоичное обратная прямой количество левых листьев
36 двоичное симметричная в ширину количество вершин на самом нижнем уровне
37 троичное глубинная внутренний количество вершин, имеющих не более двух потомков
38 троичное обратная внутренний высоту левого поддерева для корня
39 двоичное прямая в ширину высоту правого поддерева для корня
40 двоичное обратная внутренний количество листьев на самом нижнем уровне
41 троичное глубинная внутренний количество вершин на самом нижнем уровне
42 троичное обратная в глубину количество вершин, имеющих не более трёх потомков
43 двоичное обратная внутренний количество вершин, имеющих не менее одного потомка
44 троичное симметричная в глубину количество листьев не на самом нижнем уровне
45 троичное симметричная в глубину количество средних листьев
46 троичное прямая в ширину количество предков для каждой из вершин
47 двоичное обратная в глубину количество вершин на глубине не более 3
48 троичное симметричная в ширину количество вершин, имеющих не менее двух потомков
49 троичное прямая в ширину высоту среднего поддерева для корня
50 двоичное обратная в глубину количество вершин на глубине не более 4
Контрольные вопросыЧем отличаются алгоритмы для разных способов обхода деревьев?
Нужно ли сочетать ввод данных для построения дерева с клавиатуры с его обходом?
Можно ли считать применённые вами алгоритмы обхода дерева эффективными?
Нужно ли создавать отдельные классы для узла и для дерева в целом, или можно ограничиться одним универсальным, рассматривая любой узел как корень некоторого поддерева?
Отчёт по темеПо теме должен быть оформлен сводный отчёт следующего содержания:
Задание на работу с деревьями.
Обоснование выбора способа представления деревьев в памяти ЭВМ.
Тестовый пример: изображение дерева и порядок его ввода с клавиатуры.
Результаты прогона программы с генерацией случайного дерева (скриншоты).
Оценки временной сложности для каждой функции обхода дерева, использованной в программе: создание дерева, обработка, вывод.
Выводы о результатах испытания алгоритмов обхода деревьев.
Приложение: исходный текст программы для работы с деревьями (на машинном носителе).
3. ГРАФЫГраф — это пара множеств G = <V, E>, где V — произвольное множество, а E = {{u, v}: u, v ∈ V, u ≠ v} — множество пар из элементов множества V. Если пара {u, v} представляет собой множество мощностью 2, граф называется неориентированным, а если это последовательность <u, v> — ориентированным. Мы будем обозначать мощность множества вершин |V| = n, а мощность множества рёбер |E| = m. Очевидно, что справедливо ограничение m = O(n2).
Вершины {u, v}, образующие ребро, называются смежными, а само ребро — инцидентным по отношению к образующим его вершинам, а вершины, в свою очередь, инцидентны ребру. Количество рёбер, инцидентных вершине, называется её степенью. Вершина, не входящая ни в одно ребро, имеет степень 0 и называется изолированной. В ориентированном графе различают также количество рёбер, входящих в вершину — полустепень захода — и количество выходящих рёбер — полустепень выхода.
Последовательность попарно смежных вершин образует путь в графе. Длина пути равна количеству входящих в него рёбер. Если в последовательности, образующей путь, все вершины различны, путь называется элементарным. Путь, начало и конец которого совпадают, называется циклом. Связный граф без циклов называется деревом, несвязный — лесом.
Если любая пара вершин графа связана путём, граф называется связным. Если для любой пары вершин находятся по крайней мере два пути, множества вершин которых не пересекаются, граф — двусвязный.
В ориентированном графе путь между некоторыми вершинами может быть только в одну сторону. Если же любая пара вершин орграфа связана путями в обе стороны, такой граф называется сильно связным.
Граф с пустым множеством вершин называется пустым, а граф, в котором имеются все возможные рёбра — полным графом или кликой.
Граф, множество вершин которого можно разбить на два непустых непересекающихся подмножества таким образом, что концы любого ребра будут принадлежать разным подмножествам, называется двудольным.
Если граф каким-либо из перечисленных свойств не обладает, можно ставить задачу отыскания компонент — максимальных подграфов, обладающего нужным свойством, например, компонент связности, двусвязности, максимальных клик и т. п.
Графы G = <V, E> и G' = <V', E'> называются изоморфными, если существует биекция f: E→E' такая, что для любой пары вершин {u, v} ∈ E ⬄ {f(u), f(v)} ∈ E'.
На свойстве изоморфизма строятся все возможные способы хранения графа в памяти. Перечислим наиболее употребительные из них.
Вершины хранятся в массиве, каждый элемент которого — множество рёбер в форме вектора битов. Единичные биты соответствуют рёбрам, инцидентным данной вершине. Альтернатива — массив рёбер, каждое из которых задано вектором инцидентных вершин, которых может быть ровно две. Это — матрица инциденций размером m × n. Это расточительный способ, потому что матрица большей частью состоит из нулей. Но он достаточно компактен и удобен для некоторых задач, например, для отыскания вершинного или рёберного покрытия. Способ является естественным для неориентированного графа. Для орграфа нужно различать начала и концы рёбер, например, так: «–1» — ребро выходит из вершины, «+1» — ребро входит, «2» — и входит, и выходит (петля).
Вершины хранятся в массиве, каждый элемент которого — множество смежных вершин в форме вектора битов. Это — матрица смежности, её размер n × n, и она может содержать 0 и 1 в любой пропорции. Так, полному графу соответствует единичная матрица. Способ удобен для орграфов. Неориентированные графы хранятся как дважды ориентированные, т. е. их матрица смежности всегда симметрична; она может храниться только верхним треугольником.
Вершины хранятся в массиве, каждый элемент которого — множество смежных вершин в форме списка. Каждый элемент списка содержит поле с номером смежной вершины — индексом массива вершин. Это — списки смежности. Они удобны, если количество рёбер в графе не очень велико, и требуют памяти порядка O(n + m).
Массив рёбер, каждое из которых задано парой номеров инцидентных вершин — массив пар. Требует 2 × m ячеек памяти.
Разветвляющийся список из вершин, в котором рёбра реализованы посредством указателей. Этот способ применяется главным образом для ациклических орграфов (деревьев), а в общем случае малопригоден без каких-либо дополнений.
3.1. Обходы графовОбход вершин графа может быть выполнен теми же способами, что и обход дерева. Однако следует учитывать, что граф общего вида отличается тем, что он может быть не связен и может содержать циклы. Поэтому создавать дополнительную структуру данных — массив битов — и отмечать в нём пройдённые вершины. Если по завершении алгоритма обхода часть осталась не пройдённой, алгоритм перезапускается до тех пор, пока таковых не останется. Количество запусков алгоритма равно количеству компонент связности графа.
3.2. Некоторые задачи на графахНиже приводится демонстрационная программа для нахождения компонент двусвязности в неориентированном графе, использующая алгоритм обхода в глубину. Для представления вершины графа и графа в целом используются объекты. Вершины графа размечаются латинскими буквами.
Для каждой вершины графа вводится строка латинских букв — меток смежных вершин, т. е. исходное представление графа — набор множеств смежности в виде массивов. Пустая строка завершает ввод.
Далее из введённых массивов формируется матрица смежности. Она делается симметричной с нулевой главной диагональю. Тем самым устраняется дублирование и возможная неполнота ввода.
Затем с помощью функции make() матрица смежности преобразуется в списки смежности, которые и поступают на обработку в функцию DBL().
В процессе обхода графа делается контрольный вывод содержимого стека рёбер — после добавления очередного ребра-ветви, после обнаружения хорды и при определении точки сочленения. В последнем случае выводятся текущие значения массивов глубинных номеров NUM и параметров L, а также множество рёбер, образующих компоненту двусвязности, взятую из стека.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <iostream>
using namespace std;
class Node { int d;
Node * next;
public:
Node(){ next = NULL; }
~Node(){ if (next) delete next;}
friend class GR;
};
const int MaxN = 700, MaxV = 26;
char Ch(int s) {return s+'a'; }
class GR {
Node ** LIST;
int num, * NUM, * L, * STACK, ust, n, m;
public:
void DBL (int v, int p);
void Make(int [MaxV][MaxV]);
void DBL_Exec();
GR(int);
~GR();
};
GR :: GR(int MaxV) : num(0), ust(0), n(0), m(0)
{LIST = new Node * [MaxV]; NUM = new int[MaxV];
L = new int[MaxV]; STACK = new int[MaxV];}
GR :: ~GR()
{ delete []STACK; delete []L; delete []NUM; delete []LIST; }
void GR :: DBL_Exec()
{
for(int i=0; i<n; i++) { NUM[i] = 0; L[i] = 0; }
num = 0; ust = 0;
for(int i=0; i<n; i++)
if(NUM[i] == 0)
DBL(i, -1);
cout << endl << "NUM="; for(int i=0; i<n; i++) cout << NUM[i] << " ";
cout << endl << " L="; for(int i=0; i<n; i++) cout << L[i] << " ";
}
void GR :: DBL (int v, int p)
{ Node * u;
int e1, e2;
NUM[v] = L[v] = ++num;
for (u = LIST[v]; u ; u = u->next)
{ if(NUM[u->d] == 0)
{ STACK[ust++] = u->d; STACK[ust++] = v;
cout << endl << "st1:"; for(int i=0; i<ust; i++) cout << Ch(STACK[i]); _getch();
DBL(u->d, v);
L[v] = L[u->d]<L[v]?L[u->d]:L[v];
if(L[u->d] >= NUM[v])
{
cout << endl << "NUM="; for(int i=0; i<n; i++) cout << NUM[i] << " ";
cout << endl << " L="; for(int i=0; i<n; i++) cout << L[i] << " ";
cout << endl << " ребро <" << Ch(v) << '-' << Ch(u->d) << "> замыкает компоненту [";
do {
e1 = STACK[--ust];
e2 = STACK[--ust];
cout << Ch(e1) << '-' << Ch(e2) << ';';
} while (((e1 != v)||(e2 != u->d))&&(ust));
cout << "]";
cout << endl << "st3:"; for(int i=0; i<ust; i++) cout << Ch(STACK[i]); _getch();
}
}
else if ((u->d != p) && (NUM[u->d] < NUM[v]))
{ STACK[ust++] = u->d; STACK[ust++] = v;
cout << endl << "st2:"; for(int i=0; i<ust; i++) cout << Ch(STACK[i]); _getch();
L[v] = NUM[u->d]<L[v]? NUM[u->d] : L[v];
}
}
cout << " < " << v << '=' << NUM[v] << '/' << L[v];
}
void GR :: Make(int G[MaxV][MaxV])
{ int ls = 0, f;
n = m = 0;
for(int i=0; i<MaxV; i++)
{ LIST[i] = 0;
G[i][i] = 0;
f = 0;
cout << endl << Ch(i) << ": ";
for (int j=0; j<MaxV; j++)
if(G[i][j])
{ f++;
Node *v = new Node;
v->d = j; v->next = LIST[i]; LIST[i] = v;
cout << Ch(j);
}
else cout << "-";
if(f) n++;
m+=f;
if(!((++ls)%10)) _getch();
}
cout << endl << "|V|=" << n << " |E|=" << m/2;
}
void main()
{ int i, j, f, n = 0, G[MaxV][MaxV];
char s[80];
setlocale(LC_ALL, "Russian");
for(i=0; i<MaxV; i++)
for(j=0; j<MaxV; j++) G[i][j] = 0;
cout << endl << "DBL test ====================== (C)lgn, 10.10.03;14.01.13" <<
endl << " Введите списки смежности (строки букв a до z)..." << endl;
do{
cout << "v[" << Ch(n) << "]=";
cin >> s;
cout << endl << "[" << s << "]" << strlen(s); _getch();
for (int i = 0; i < strlen(s); i++)
if (isalpha(s[i])){ j = tolower(s[i]) - 'a';
G[n][j] = G[j][n] = 1;
}
n++;

} while((strlen(s)>0) && (n < MaxV));
//Преобразование строк в матрицу, затем - в списки смежности,
//подсчёт мощностей и контрольный вывод
GR Gr(MaxN);
Gr.Make(G);
//Тестирование функции DBL
Gr.DBL_Exec();
printf("\n ===== Конец =====\n");
_getch();
}
3.3. Переборные алгоритмы на графахДля решения задачи, для которой нет эффективного алгоритма, можно применить следующие подходы:
Задача, решением которой является некоторая перестановка элементов полного множества. Примеры: проверка графов на изоморфизм, отыскание гамильтонова цикла и т. п. Решение такой задачи может быть сведено к генерации перестановок и проверке каждой перестановки, не является ли она решением. Альтернатива — генерация случайных перестановок до тех пор, пока решение не будет обнаружено или не закончится отведённое для этого время.
Задача, решением которой является подмножество. Здесь можно использовать генератор всех подмножеств.
В обоих случаях можно попытаться применить алгоритм перебора с возвратом, который, начиная с пустого вектора, пытается расширить его до решения, отбрасывая заведомо негодные альтернативы.
Пример 1. Программа отыскания гамильтонова цикла. Она отлажена в оболочке Borland C++ 3.1 без использования объектов. Для разметки вершин исходного графа используется множество десятичных цифр. С клавиатуры для каждой вершины вводятся множества смежности.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
const int nmax = 100;
struct Node{ int d;Node * next; };
Node * LIST[nmax];
int NEW[nmax], L[nmax], X[nmax], n=0, m=0;
void GAM (int k)
{ Node * u;
if(k == n)
{ printf("<");
for (int i=0; i<k; i++) printf("%2d", X[i]);
printf(">\n"); getch();
}
else
{ for (u = LIST[X[k-1]]; u ; u = u->next)
{ if(NEW[u->d])
{ NEW[u->d] = 0;
X[k] = u->d;
GAM(k+1);
NEW[u->d] = 1;
}
}
}
}
void main()
{ int i, j, f, G[10][10];
Node * v;
char s[20];
for(i=0; i<10; i++)
for(j=0; j<10; j++) G[i][j] = 0;
printf("\nGAM test ====================== (C)lgn, 16.10.03"
"\n Ввод списка смежности (строки цифр от 0 до 9)...\n");
do{ printf( "v[%2d]=", n);
gets(s);
for (i=0; i<strlen(s); i++)
{ j = s[i] - '0';
G[n][j] = G[j][n] = 1;
}
n++;
} while(strlen(s)&&(n < 10));//Формирование и вывод исходных данных
n=0;
for(i=0; i<10; i++)
{ LIST[i] = 0;
G[i][i] = 0;
f = 0;
printf("\n%2d:", i);
for (j=0; j<10; j++)
if(G[i][j])
{ f++;v = new Node;
v->d = j; v->next = LIST[i]; LIST[i] = v;
printf(" %2d", j);
}
else printf(" -");
if(f) n++;
m+=f;
}
printf("\n|V|=%2d, |E|=%2d", n, m/2);
//Тестирование функции GAM
for(i=0; i<n; i++) NEW[i] = 1;
printf("\nГамильтонов путь: ");
X[0] = 0; NEW[0] = 0; GAM(1);
printf("\n ===== Конец =====\n"); getch();
}
Перебор с возвратом работает значительно быстрее полного перебора, но временная сложность алгоритма всё равно остаётся экспоненциальной.
Поэтому на практике часто используются приближённые алгоритмы полиномиальной сложности, которые теоретически не могут дать точного решения. Проверить этот факт можно прямым сравнением алгоритмов на опыте.
Пример 2. Испытания эмпирического алгоритма отыскания максимальной клики в произвольном неориентированном графе. Исходный граф представлен матрицей смежности, заполняемой с помощью датчика случайных чисел таким образом, чтобы граф получался плотным. Мощность множества вершин графа задана константой в программе. Если её значение невелико, матрица смежности выводится на экран для возможности визуального контроля результата.
Испытания программы показывают, что эмпирический алгоритм почти всегда находит решение, только если количество вершин не очень велико. Алгоритм перебора с возвратом всегда находит все решения.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
using namespace std;
const int N=10;//Количество вершин
int a[N][N], i, j, maxv = 0, k, st, ans[N], i1, num, K[N+1], U[N];
void G(int k) //Перебор с возвратом
{ int i, i0;
if(k == 1) i0 = 0; else i0 = K[k-2] + 1;
for(i=i0; i<N; i++)
if (U[i]) {
K[k-1] = i; j = 0;
while((j < k) && a[K[j]][i]) j++;
if(j+1 == k) { //Найдена клика...
if(k > maxv) { //больше предыдущей, зафиксировать решение
maxv=k;
for(i1 = 0; i1 < k; i1++)
ans[i1] = K[i1] + 1;
}
if(k == maxv) { //... и выдать
cout << endl << " max=" << maxv << " : ";
for(i1 = 0; i1 < maxv; i1++)
cout << (K[i1] + 1) << " ";
_getch();
}
U[i] = 0; //Вершина (i) теперь занята
G(k+1); // Попробовать расширить решение
U[i] = 1; //Возврат: (i) снова свободна }
}
}
void main(void)
{
setlocale(LC_ALL, "Russian");
srand(time(NULL));
//Генерация матрицы смежности неорграфа
for(i = 0; i < N; i++)
{ U[i] = 1;
for(j = i; j < N; j++)
if(j == i)
a[i][j] = 0;
elsea[i][j] = a[j][i] = rand() % 15 > 2;
}
if (N<21) { //Вывод на экран, если влезает
cout << endl << "Матрица смежности";
cout << endl << " 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20";
cout << endl << "-----------------------------------------------------------------";
for(i = 0; i < N; i++)
{ cout << endl << " "<< i+1 << " |";
for(j = 0; j < N; j++)
cout << " " << a[i][j] << " ";
}
}
//Эмпирический алгоритм - полиномиальной сложности
for(i = 0; i < N; i++)
{ K[0] = i;
for(st = i + 1; st < N; st++)
if(a[i][st])
{ k = 1;
for(j = st; j < N; j++)
{num = 1;
while((a[K[num-1]][j]) && (num <= k)) num++;
if((num - 1) == k)
{ k++; K[k-1]=j; }
}
if(k > maxv) //Зафиксировать решение
{ maxv = k;for(i1 = 0; i1 < k; i1++) ans[i1] = K[i1] + 1;
}
if(k == maxv) {//... и выдать
cout << endl << " max=" << maxv << " : ";
for(i1 = 0; i1 < maxv; i1++)
cout << (K[i1] + 1) << " ";
_getch();
}
}
}
cout << endl << " Клика мощностью " << maxv <<" из вершин: ";
for(i = 0; i < maxv; i++)
cout << ans[i] << " ";
cout << endl << " Контроль перебором";
maxv = 0;
G(1);
cout << endl << "ИТОГ: мощность " << maxv <<", вершины: ";
for(i = 0; i < maxv; i++)
cout << ans[i] << " ";
_getch();
}
Результаты работы программы
Вариант 1. Граф из 9 вершин. Результаты работы двух алгоритмов совпадают.

Вариант 2. Количество вершин увеличено до 20. Эмпирический алгоритм начинает проигрывать.



Полный перебор нашёл целых 13 клик мощностью 9.

Практикум по темеВыполнить курсовую работу по предложенному преподавателем индивидуальному заданию. Детальную постановку задачи взять из курса лекций и уточнить по рекомендованным литературным источникам. Реализовать алгоритм на языке С++.
Выбрать оптимальную структуру данных для представления графа в памяти ЭВМ. Реализовать граф как объект, а обработку — как метод для него. Результат обработки может быть или не быть частью объекта, способ его представления выбирается особо.
Для объекта должны быть объявлены все вспомогательные методы (методы по умолчанию) — конструкторы, деструктор и т. п. Использование ненужных методов блокируется на уровне компиляции или выполнения.
Стек и очередь (если нужны) реализуются как вспомогательные объекты. Рекомендуется использовать шаблоны классов.
Интерфейс программы должен быть удобен для испытаний алгоритма. Следует предусмотреть ввод заранее заготовленных и генерацию произвольных тестовых данных.
Дополнительное требование: оценить возможный объём исходных данных для решения поставленной задачи для следующих ограничений:
— возможность вывода данных на экран;
— доступный объём памяти;
— получение решения за разумное время.
Содержание пояснительной записки к курсовой работеЗадание.
Выбор и обоснование способа представления данных.
Описание алгоритма и оценка его временной сложности.
Набор тестов и результаты проверки алгоритма на ЭВМ.
Выводы.
Список использованных источников.
Приложение: исходный текст программы для ЭВМ (на машинном носителе).
Защита курсовой работыК защите допускаются отчёты, имеющие все перечисленные рубрики, с приложением текста программы на машинном носителе в виде, пригодном для компиляции. На защите следует продемонстрировать работу программы, обосновать решения, принятые при реализации алгоритма и выводы о его временной сложности.
Варианты индивидуальных заданий к теме «Графы»№ вари-анта Алгоритм для исследования
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 Нахождение минимального множества вершин неориентированного графа, разрезающих циклы
48 Нахождение минимального множества рёбер неориентированного графа, разрезающих циклы
49 Проверка неориентированного графа на планарность
50 Построение множества точек сочленения неориентированного графа
Приложение. Оценка временной сложности алгоритмовПри проектировании алгоритмов нас, как правило, не интересует точное число шагов, необходимых для решения задачи на конкретном наборе данных. Гораздо важнее знать, как будет изменяться время решения задачи T, если размер входа n растёт.
Класс алгоритмов, время работы которых растёт по крайней мере так же быстро, как некоторая функция f(n), обозначается как Ω(f(n)). Это означает, что при всех n, превышающих порог n0, T(n) ≥ C.f(n) для некоторого положительного числа C. Оценка времени работы снизу может представлять интерес только как теоретическая нижняя граница эффективности любого алгоритма для некоторой задачи, которую преодолеть невозможно.
Класс алгоритмов, время работы которых растёт не быстрее функции f(n), обозначается O(f(n)), что означает существование положительных чисел n0 и c таких, что при n > n0 T(n) ≤ C.f(n). Этот класс — важнейшая характеристика алгоритма, его временная сложность. По скорости роста этого времени в зависимости от размера входа алгоритмы делятся на следующие классы временной сложности:
алгоритмы константной сложности — T(n)∈O(1);
логарифмической сложности — T(n)∈O(log n);
линейной сложности — T(n)∈O(n);
квадратичной сложности — T(n)∈ O(n2);
кубической сложности — T(n)∈O(n3);
полиномиальной сложности — T(n)∈O(nk), где k = const; k = 0, 1, 2 или 3 — это частные случаи классов полиномиальной сложности;
экспоненциальной сложности — T(n)∈O(an).
Очевидно, что классы в этом перечне упорядочены по возрастанию мощности. Так, класс O(1) является подмножеством любого из остальных классов. Задача программиста — найти или разработать алгоритм класса минимально возможной мощности и реализовать его так, чтобы оценка временной сложности не ухудшилась.
Алгоритм, для которого оценки Ω(f(n) и O(f(n)) совпадают, называется оптимальным.Так, очевидно, что алгоритм, имеющий на входе некоторое множество, будет оптимальным, если его временная сложность O(1). Такой алгоритм можно попытаться найти, если задача не требует рассмотреть множество целиком. Если же требуется что-то сделать с каждым элементом множества мощностью n, оптимальный алгоритм будет иметь сложность O(n). Если имеется два множества, и нужно обработать все возможные пары их элементов, можно ожидать сложности O(n2), для трёх множеств, если обрабатываются все тройки — O(n3), и т. д.
Если же для получения результата необходимо рассмотреть все подмножества исходного множества или все перестановки его элементов — это задача на полный перебор, принадлежащая классу экспоненциальной сложности. В таких случаях говорят об отсутствии эффективного алгоритма.
Время работы программы часто зависит не только от мощности входных данных, но и от того, какие именно данные поступили на вход. В таких случаях делаются две оценки временной сложности:
— для самого неудобного набора данных — сложность «в худшем случае»;
— для типового набора данных — сложность «в среднем».
Тривиальные входные данные («лучший случай») обычно интереса не представляют.
Для оценки временной сложности по реализации алгоритма (тексту программы) можно руководствоваться следующими соображениями:
— операции присваивания (копирования) и проверки условия для базовых типов данных выполняются за константное время. Если при этом вызывается функция, сложность шага алгоритма определяется сложностью функции (в операциях с объектами функции могут вызываться неявно);
— сложность алгоритма, состоящего из последовательности шагов, определяется по самому сложному шагу;
— сложность выбора по условию определяется по самой сложной из альтернатив. В порядке исключения можно не принимать во внимание альтернативы, выбираемые очень редко. Можно учесть такие альтернативы, как «худший случай»;
— если какие-то шаги являются внутренней частью цикла с количеством повторений, зависящим от размера входа n, в оценку сложности циклического шага добавляется множитель n. Если же количество повторений не зависит от n, цикл игнорируется, поскольку его можно рассматривать просто как повторение некоторого количества одинаковых шагов алгоритма;
— рекурсия рассматривается как тот же цикл. Её сложность определяется как произведение сложности одного вызова функции на количество вызовов.
Примеры
Вычислить b = (a ∈ A), где множество A мощностью nA представлено массивом целых чисел.
Решение: b = false; for(i = 0; !b && (i < nA); i++) b |= (a == A[i]);
Временная сложность алгоритма — O(nA). Если элемент a найден, алгоритм прекращает работу, выполнив от 1 до nA шагов. В среднем количество шагов будет nA/2, в худшем случае (a ∉ A) — nA.
Вычислить C = A ⋂ B для множеств, представленных неупорядоченными массивами.
Решение: проверяем все возможные пары элементов двух множеств и отбираем совпадения.
for(i = k = 0; i < nA; i++)
for (j = 0; j < nB; j++) if (A[i] == B[j]) C[k++] = A[i];
Проверка на совпадение и присваивание выполняются за константное время, поэтому сложность алгоритма — O(nA×nB), или O(n2), где n — средняя мощность множеств.
Вычислить D = A ⋂ B ⋂ C.
Очевидное решение
for(i = k = 0; i < nA; i++)
for(j = 0; j < nB; j++)
for(r = 0; r <nC; r++)
if((A[i] == B[j]) && (A[i] == C[r])) D[k++] = A[i];
имеет временную сложность O(n3), поскольку перебираются все возможные тройки.Однако перебирать все тройки никакой необходимости нет. Модифицируем алгоритм:
for(i = k = 0; i < nA; i++)
for(j = 0; j < nB; j++)
if(A[i] == B[j]) for(r = 0; r <nC; r++)
if(A[i] == C[r]) D[k++] = A[i];
В алгоритме по-прежнему три вложенных цикла, но внутренний цикл теперь зависит от условия A[i] == B[j], которое проверяется n2 раз, но удовлетворяется не более чем n раз, т. е. рассматриваются только такие тройки, у которых первые два элемента совпадают. Проверка A[i] == C[r] выполняется, таким образом, не более n2 раз, и общая сложность алгоритма — O(n2).
Вычислить C = A ⋂ B для множеств, представленных строками символов.
Решение:
for(i = k = 0; i <strlen(A); i++)
for (j = 0; j <strlen(B); j++) if (A[i] == B[j]) C[k++] = A[i];
По аналогии с примером 2 можно оценить сложность как O(n2). Однако это неверно, так как в обоих циклах по n раз вычисляется функция определения длины строки strlen(), которая, очевидно, подсчитывает в строке количество символов до ближайшего нуля перебором, т. е. имеет линейную сложность. Вычисление этой функции — один из шагов внутренней части обоих циклов. Таким образом, внутренняя часть вложенного цикла состоит из трёх шагов, двух константных (проверка и присваивание) и линейного (вычисление функции). С учётом n повторений сложность всего цикла — O(n2). Внешний цикл добавляет сюда ещё шаг вычисления функции сложностью O(n). Сложность его внутренней части — O(n2), а всего алгоритма — O(n3)! Это — цена экономии двух целых переменных. На самом деле нужно вычислить nA = strlen(A); nB = strlen(B), а затем использовать алгоритм из примера 2.
Список литературыСеджвик Р. Алгоритмы на С++.: Пер. с англ. — М.: ООО «И. Д. Вильямс», 2011. — 1156 с.: ил.
Новиков Ф. А. Дискретная математика: Учебник для вузов, 2-е изд. Стандарт третьего поколения. — СПб.: Питер, 2013. — 432 с.: ил.
Седжвик Р. Фундаментальные алгоритмы С++. — М., 2002. — 484 с.
С/С++. Программирование на языке высокого уровня / Т. А. Павловская.— СПб.: Питер, 2013. — 461 с.: ил.
Страуструп Б. Программирование: принципы и практика использования С++, испр. изд.: Пер. с англ. — М.: Издательский дом «Вильямс», 2013. — 1248 с.: ил.
Макконелл Дж. Основы современных алгоритмов. — Изд. 2-е. — М., 2004. — 368 с.
Ахо Дж., Хопкрофт А., Ульман Дж. Структуры данных и алгоритмы. — СПб., 2001. — 382 c. (доп. тир. 2003, 2007).
Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е изд.: Пер. с англ. — М., 2005. — 1296 с.: ил.
Липский В. Комбинаторика для программистов. — М., 1978. — 213 с.
Вирт Н. Алгоритмы и структуры данных. — СПб., 1989 (доп. тир. 2001).
Ахо Дж., Хопкрофт А., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М., 1979.
 Страуструп Б. Язык программирования С++. Второе дополненное издание. — М., 2001. – 1098 с. (доп. тир. 2002, 5, 6, 7).
 Шилдт Г. Искусство программирования наС++. — СПб., 2005. — 474 с.
 Шилдт Г. Самоучитель C++. 3-е изд. — СПб., 2000. — 683 с. (доп. тир. 2002, 2004, 2005, 2006 г.).
Новиков Ф. А. Дискретная математика для программистов. — СПб.: Питер, 2000. — 304 с.: ил.
 Гери М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. — М.: Мир, 1982. — 419 с.
СОДЕРЖАНИЕ
TOC \o "1-3" ВВЕДЕНИЕ PAGEREF _Toc347359310 \h 3
1. МНОЖЕСТВА PAGEREF _Toc347359311 \h 5
1.1.Представление множества набором элементов PAGEREF _Toc347359312 \h 5
Практикум по теме PAGEREF _Toc347359313 \h 7
Варианты индивидуальных заданий к теме «Множества» PAGEREF _Toc347359314 \h 7
Контрольные вопросы PAGEREF _Toc347359315 \h 10
1.2.Представление множества отображением на универсум PAGEREF _Toc347359316 \h 11
Практикум по теме PAGEREF _Toc347359317 \h 13
1.3. Генерация тестов PAGEREF _Toc347359318 \h 13
Генерация последовательности всех подмножеств заданного множества PAGEREF _Toc347359319 \h 13
Генерация перестановок PAGEREF _Toc347359320 \h 14
Генерация случайного подмножества PAGEREF _Toc347359321 \h 15
Случайное подмножество заданной мощности PAGEREF _Toc347359322 \h 16
Контрольные вопросы PAGEREF _Toc347359323 \h 17
1.4. Измерение времени решения задачи с помощью ЭВМ PAGEREF _Toc347359324 \h 17
Использование функции clock() PAGEREF _Toc347359325 \h 17
Практикум по теме PAGEREF _Toc347359326 \h 18
Контрольные вопросы PAGEREF _Toc347359327 \h 18
1.5. Множество как объект PAGEREF _Toc347359328 \h 18
Практикум по теме PAGEREF _Toc347359329 \h 26
Контрольные вопросы PAGEREF _Toc347359330 \h 26
Отчёт по теме PAGEREF _Toc347359331 \h 26
2. ДЕРЕВЬЯ PAGEREF _Toc347359332 \h 27
2.1. Обходы дерева как рекурсивной структуры данных PAGEREF _Toc347359333 \h 29
2.3. Создание дерева PAGEREF _Toc347359334 \h 30
2.2. Вывод изображения дерева на экран монитора PAGEREF _Toc347359335 \h 32
2.4. Шаблоны классов для очереди и стека и нерекурсивные алгоритмы обхода дерева PAGEREF _Toc347359336 \h 33
Практикум по теме PAGEREF _Toc347359337 \h 35
Варианты индивидуальных заданий к теме «Деревья» PAGEREF _Toc347359338 \h 35
Контрольные вопросы PAGEREF _Toc347359339 \h 37
Отчёт по теме PAGEREF _Toc347359340 \h 38
3. ГРАФЫ PAGEREF _Toc347359341 \h 39
3.1. Обходы графов PAGEREF _Toc347359342 \h 41
3.2. Некоторые задачи на графах PAGEREF _Toc347359343 \h 41
3.3. Переборные алгоритмы на графах PAGEREF _Toc347359344 \h 45
Практикум по теме PAGEREF _Toc347359345 \h 53
Содержание пояснительной записки к курсовой работе PAGEREF _Toc347359346 \h 53
Защита курсовой работы PAGEREF _Toc347359347 \h 53
Варианты индивидуальных заданий к теме «Графы» PAGEREF _Toc347359348 \h 54
Приложение. Оценка временной сложности алгоритмов PAGEREF _Toc347359349 \h 55
Список литературы PAGEREF _Toc347359350 \h 59

Редактор Г. Г. Петров
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
Подписано в печать . Формат 60×84 1/16.
Бумага офсетная. Печать офсетная. Печ. л. .Гарнитура « ». Тираж экз. Заказ
––––––––––––––––––––––––––––––––––––––––––––––––––––––––––
Издательство СПбГЭТУ «ЛЭТИ»
197376, С.-Петербург, ул. Проф. Попова, 5

Приложенные файлы

  • docx 8818455
    Размер файла: 545 kB Загрузок: 1

Добавить комментарий