- •Билет 1
- •Билет 2
- •Способы представления графов
- •Билет 3
- •Билет 4
- •Билет 5
- •Билет 6
- •Билет 7
- •Основы визуального программирования
- •Билет 8
- •Обменная сортировка.
- •Конструкторы и деструкторы
- •Билет 9
- •Билет 10
- •Статическое и динамическое распределение памяти. Понятие указателя.
- •Процедуры и функции модуля graph.
- •Билет 11
- •Доступ к системным ресурсам в операционной системе pc-dos
- •Билет 12
- •Билет 13
- •Билет 14
- •Билет 15
- •Алгоритм генерирования перестановок с минимальным числом транспозиций
- •1. Введение в теорию графов. Способы представления графов: матрицы смежности и инцидентности, списки инцидентностей, списки ребер.
- •2. Функции библиотеки dos. Прерывания. Обработка прерываний.
- •Связные компоненты графа. Деревья. Бинарное дерево как связный граф без циклов
- •2.Сортировка вставками
- •2)Итерационные циклы
- •1.Эйлеровы пути в графе.
- •2.Ввод-вывод с помощью текстовых файлов.
- •Алгоритм Дейкстры (Dijkstra)
- •Вопрос 1.
- •Вопрос 2.
- •Создание и обработка одномерных динамических массивов.
- •Операторы цикла.
- •2.Сортировка распределением
- •1)Односвязные линейные списки
- •2) Записи. Организация, размещение. Записи с вариантами.
- •1.Алгоритмы с возвратом, их реализация с помощью рекурсий и с использованием стека. Гамильтоновы циклы.
1. Введение в теорию графов. Способы представления графов: матрицы смежности и инцидентности, списки инцидентностей, списки ребер.
Граф - это множество точек (вершин, объектов) и соединяющих их путей (линий, дуг, рёбер). Абсолютно неважно, какой вид имеют эти линии, и как точки расположены в пространстве. Идея графа — это набор каких-то объектов, с описанными связями между ними. В самом простом случае связь может быть, а может не быть.
Граф может быть ориентированным и неориентированным. В ориентированном графе пути (дуги) имеют направление, а в неориентированном - не имеют. Неориентированное ребро можно представить как две разнонаправленные дуги между
двумя вершинами. Пути в неориентированном графе называются рёбрами.
Путь в графе или орграфе - это последовательность ребер, по которым можно поочередно проходить. Другими словами, путь из вершины A в вершину B начинается в A и проходит по набору ребер до тех пор, пока не будет достигнута вершина B. Связный граф – это такой граф, что между любыми парами вершин есть хоть один путь.
Взвешенным называется такой граф, для каждого ребра (дуги) которого определена некоторая функция. Иначе говоря, к каждому ребру «привязан» вес - фиксированное число или результат какой-то функции.
Один из самых распространённых способов хранения графа - матрица смежности. Она представляет собой двумерный массив. Если в клетке i, j (i – строка, j - столбец) установлено значение пусто (как правило, это очень большая величина или величина, которой заведомо не может равняться вес ребра), то дуги, начинающейся в вершине i и кончающейся в вершине j, нет. Иначе дуга есть. Если она есть, то в соответствующую ячейку записывают ее вес. Если граф не взвешенный, то вес дуги считается равным единице.
Матрица инцидентности — одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро(дуга) и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам. Ненулевое значение в ячейке
матрицы указывает связь между вершиной и ребром (их инцидентность). В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".
Список дуг. Чаще всего это двумерный массив размером 3*E, в первой строке которого хранится информация, из какой
вершины начинается дуга, во второй - в какой кончается, а в третьей строке - вес дуги.
2. Функции библиотеки dos. Прерывания. Обработка прерываний.
Модуль Dos позволяет использовать возможности операционной системы MS DOS, не предусмотренные в стандарте языка Паскаль,
и содержит типы, константы, переменные и подпрограммы для реализации этих дополнительных возможностей.
Процедура Intr выполняет указанное программное прерывание.
Объявление:
procedure Intr(IntNo: Byte; var Regs: TRegisters);
Замечания:
Перед вызовом процедуры Intr, загрузите переменную Regs соответствующими параметрами, необходимыми для прерывания.
Переменная Regs возвращает значения регистров после вызова прерывания. Вызовы, которые используют регистры ESP и SS не
могут быть выполнены. Более подробную информацию о программных прерываниях ищите в руководствах на ваши BIOS и DOS.
Учтите, что все сегментные регистры (DS,ES,FS,GS) должны содержать допустимые значения сегментных дескрипторов или быть
установлены в ноль перед вызовом процедуры Intr. Все прерывания, вызов которых требует анализа смещения, должны
использовать 32-битное смещение.
Пример:
uses Dos;
function GetVideoMode: Byte; var Regs: Registers;
begin Regs.AX := $0F00;Regs.DS := DSeg; Regs.ES := 0;
Regs.FS := 0; Regs.GS := 0; Intr($10, Regs); GetVideoMode := Regs.Al; end.
Билет 17