1.Алгоритмы с возвратом, их реализация с помощью рекурсий и с использованием стека. Гамильтоновы циклы.

Начало исследований так называемых гамильтоновых графов относится к графам многогранников . В 1857 г. ирландский математик Гамильтон предложил игру, названную "путешествие по додекаэдру". Игра сводилась к обходу по ребрам всех вершин правильного додекаэдра при условии, что ни в одну из вершин нельзя заходить более одного раза. Додекаэдр - это многогранник, гранями которого служат 12 правильных пятиугольников. У него 20 вершин и 30 ребер. Вершины и ребра додекаэдра составляют некоторый плоский граф. Простой цикл в графе - это замкнутый путь, все вершины которого, кроме v0 и vn, попарно различны. Гамильтонов цикл - это простой цикл, содержащий все вершины графа. Заметим, что гамильтонов цикл есть далеко не в каждом графе. Граф называется гамильтоновым, если в нем имеется гамильтонов цикл. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Ясно, что всякий гамильтонов граф является полугамильтоновым. Применим теперь алгоритм с возвратом для нахождения гамильтонова цикла в графе. Алгоритм, с помощью которого мы будем искать гамильтоновы циклы, называется поиск с возвращением. В основе его лежит понятие частичного решения. Пусть решение задачи представляется в виде некоторой последовательности. В нашем случае это просто последовательность всех вершин графа, удовлетворяющая очевидным ограничениям. Начальный отрезок последовательности, который удовлетворяет ограничениям, определяющим полное решение, называется частичным решением. Частичным решением для гамильтонова цикла является любая последовательность вершин, определяющая простой путь. Если в последовательность, представляющую частичное решение, добавить новый элемент так, что расширенная последовательность снова будет частичным решением, то новая последовательность называется продолжением частичного решения. Идея поиска с возвращением состоит в том, чтобы, начав с тривиального частичного решения, последовательно продолжать его до тех пор, пока не будет получено полное решение, либо продолжение станет невозможным.

2. Объект. Инициализация и разрушение объекта.

Объект в Delphi представляет из себя специальную структуру, которая описывает поля, свойства и методы объекта - class. Предком для всех объектов служит class Tobject. Create – это так называемый конструктор объекта; он всегда присутствует в классе и служит для создания и инициализации экземпляров. При создании объекта в памяти выделяется место только для его полей. Методы, как и обычные процедуры и функции, помещаются в область кода программы; они умеют работать с любыми экземплярами своего класса и не дублируются в памяти. После создания объект можно использовать в программе: получать и устанавливать значения его полей, вызывать его методы. Доступ к полям и методам объекта происходит с помощью уточнённых имён, например: People.GetName;

People.GetFamily; Если объект становится ненужным, он должен быть удалён вызова специального метода Destroy, например: People.Destroy; //Освобождение памяти, занимаемой объектом

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

Метод Destroy используется для разрушения объекта. Destroy является деструктором Delphi. Он используется для разрушения объекта и освобождения памяти, которая была распределена объекту. Destroy вызывается методом Free, представляющим собой функцию, которую следует вызывать для разрушения объектов, сконструированных Create.

Пример:

People := nil;

if Peopl

e <> nil then

People.Destroy;

Билет № 22