Олимпиадные задачи по программированию (стр. 4 )

Сортировка выбором. Дана последовательность чисел a1, a2, ..an. Требуется переставить элементы так, чтобы они были расположены по убыванию. Для этого в массиве, начиная с k-го, выбирается наибольший элемент и меняется местами с k-м.

Эта процедура выполняется для k= 1, 2, 3... n-1. При k=1 из всех элементов массива выбирается наибольший и меняется местами с k-м, т. е. с 1-м, таким образом, он занимает свое место. При k=2 из оставшихся (всех, кроме первого) выбирается максимальный элемент и меняется местами с k-м, т. е. со 2-м. Процедура эта повторяется, пока k не станет равно n-1. Тогда на последнем шаге из двух последних элементов выбирается максимальный, меняется местами с k-м, т. е. с (n-1)-м. После этого массив является отсортированным.

Сортировка методом «пузырька». Дана последовательность чисел a1, a2, ..an. Требуется переставить элементы так, чтобы они были расположены по возрастанию. Для этого из k элементов массива сравнивают каждую пару соседних элементов ai и ai+1. Если ai>ai+1, то их меняют местами. При первом прохождении массива самый большой элемент, как «пузырек», займет последнее место. Эта процедура выполняется для всех k = n, n-1, n-2, ...2.

Шейкер-сортировка. Эта сортировка является усовершенствованной сортировкой методом «пузырька» (внимательно прочитайте предыдущее описание). Просмотр массива осуществляется последовательно в двух направлениях. Сначала массив проходят в «прямом» направлении, сравнивают каждую пару соседних элементов и, если ai>ai+1, то их меняют местами. При этом элемент с самым большим значением перемещается вверх и занимает последнее место. Затем массив просматривается в обратном направлении, начиная уже с (n-1)-го элемента. Сравнивают каждую пару соседних элементов и, если ai<ai-1, то их меняют местами. При этом элемент с самым маленьким значением перемещается вниз и занимает первое место. Затем этот процесс повторяется, начиная со второго элемента и т. д.

Сортировка вставками. Дана последовательность чисел a1, a2, ..an. Требуется переставить элементы так, чтобы массив стал упорядоченным. Пусть k элементов массива уже являются упорядоченными. Берется следующее число ak+1 и вставляется в последовательность так, чтобы оказались упорядоченными уже k+1 элемент. Выполняем эту процедуру для k=1, 2, 3, ..., n-1. Иными словами, при k=1 считаем, что первый элемент стоит на своем месте. Берем (k+1)-й, т. е. 2-й элемент, и переставляем его так, чтобы по порядку стояли уже первые два элемента. При k=2 считаем, что два элемента стоят на своем месте. Берем (k+1)-й, т. е. 3-й элемент, и переставляем его так, чтобы первые три элемента были упорядочены. Повторяем эту процедуру, пока k не станет равно n-1. Тогда берем (k+1)-й, т. е. последний элемент, и переставляем его так, чтобы он занял свое место среди предыдущих уже упорядоченных элементов. После этого массив отсортирован.

Сортировка Шелла. Дана последовательность чисел a1, a2, ..an. Требуется переставить элементы так, чтобы они были расположены по неубыванию. Делается это следующим образом: сравниваются два соседних элемента ai и ai+1. Если ai£ai+1, то продвигаются на один элемент вперед, а если ai>ai+1, то их меняют местами и сдвигаются на один элемент назад.

Сортировка подсчетом. Дана последовательность чисел a1, a2, ..an. Требуется переставить элементы так, чтобы они были расположены по возрастанию. Выходной массив заполняется фиксированными значениями, заведомо отличными от элементов исходного массива, например, равными –1. Затем для каждого элемента исходного массива определяется его место в выходном массиве путем подсчета количества элементов строго меньших данного. Естественно, что все равные элементы попадают на одну позицию в выходном массиве, за которой будет следовать ряд значений –1. После того, как позиции всех элементов исходного массива определены, и они размещены в выходном массиве, все оставшиеся в выходном массиве элементы равные –1 заполняются копией предыдущего значения.

Иерархические структуры данных. Деревья

Деревья представляют собой иерархическую структуру некой совокупности элементов. Деревья – это одна из наиболее важных нелинейных структур, которые встречаются при работе с компьютерными алгоритмами, их используют при анализе электрических цепей, математических формул, для организации информации в системах управления базами данных и для представления синтаксических структур в компиляторах.

Дерево – это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений («родительских»), образующих иерархическую структуру узлов. Вообще говоря, древовидная структура задает для элементов дерева (узлов) отношение «ветвления», которое во многом напоминает строение обычного дерева.

Формально дерево (tree) определяется как конечное множество T одного или более узлов со следующими свойствами:

? Существует один выделенный узел, а именно – корень (root) данного дерева;

? Остальные узлы (за исключением корня) распределены среди m≥0 непересекающихся множеств T1, T2, …. Tm, и каждое из этих множеств, в свою очередь, является деревом; деревья T1, T2, ... Tm называются поддеревьями данного корня.

Как видите, это определение является рекурсивным: дерево определено на основе понятия дерево. Рекурсивный характер деревьев можно наблюдать и в природе, например, почки молодых деревьев растут и со временем превращаются в ветви (поддеревья), на которых снова появляются почки, которые также растут и со временем превращаются в ветви (поддеревья) и т. д. Можно привести еще одно формальное определение дерева:

? Один узел является деревом. Этот же узел также является корнем этого дерева.

? Пусть n – это узел, а T1, T2, ... Tm – деревья с корнями n1, n2, … nm соответственно. Можно построить новое дерево, сделав n родителем узлов n1, n2, … nm. В этом дереве n будет корнем, а T1, T2, ... Tm – поддеревьями этого корня. Узлы n1, n2, … nm называются сыновьями узла n.

Из приведенных выше определений следует, что каждый узел дерева является корнем некоторого поддерева данного дерева. Количество поддеревьев узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом или листом. Неконцевой узел называется узлом ветвления. Каждый узел имеет уровень, который определяется следующим образом: уровень корня дерева равен нулю, а уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева, содержащего данный узел.

Рассмотрим эти понятия на примере дерева с семью узлами (см. рисунок). Узлы часто изображаются буквами, они так же, как и элементы списков могут быть элементами любого типа.

Узел A является корнем, который имеет два поддерева {B} и {C, D, E, F, G}. Корнем дерева{C, D, E, F, G} является узел C. Уровень узла C равен 1 по отношению ко всему дереву. Он имеет три поддерева {D}, {E}и {F, G}, поэтому степень узла C равна 3. Концевыми узлами (листьями) являются узлы B, D, E, G.

Путем из узла n1 в узел nk называется последовательность узлов n1, n2, … nk, где для всех i, 1≤i≤k, узел ni является родителем узла ni+1. Длиной пути называется число, на единицу меньшее числа узлов, составляющего этот путь. Таким образом, путем нулевой длины будет путь из любого узла к самому себе. Например, на рисунке путем длины 2 будет путь от узла A к узлу F или от узла C к узлу G.

Если существует путь из узла a в узел b, то в этом случае узел a называется предком узла b, а узел b – потомком узла a. Отметим, что любой узел одновременно является предком и потомком самого себя. Например, на рисунке предками узла G будут сам узел G и узлы F, C и A. Потомками узла C будут являться сам узел C и узлы D, T, F, G. В дереве только корень не имеет предков, а листья не имеют потомков.

Предок узла, имеющий уровень на единицу меньше уровня самого узла, называется родителем. Потомки узла, уровень которых на единицу больше относительно самого узла, называются сыновьями или детьми. Узлы, являющиеся сыновьями одного родителя, принято называть братьями.

Высотой узла дерева называется длина самого длинного пути от этого узла до какого-либо листа. Глубина узла определяется как длина пути от корня до этого узла.

Лес – это множество (обычно упорядоченное), содержащее несколько непересекающихся деревьев. Узлы дерева при условии исключения корня образуют лес.

Порядок узлов

Если в определении дерева имеет значение порядок поддеревьев T1, T2, ... Tm, то дерево является упорядоченным.

Сыновья узла обычно упорядочиваются слева направо. Поэтому деревья, приведенные на рисунке, являются различными.

Если порядок сыновей игнорируется, то такое дерево называется неупорядоченным. Далее будем неявно предполагать, что все рассматриваемые деревья являются упорядоченными, если явно не указано обратное.

Обходы дерева

Существует несколько способов обхода всех узлов дерева. Три наиболее часто используемых способа обхода называются прямой, обратный и симметричный обходы. Все три способа можно рекурсивно определить следующим образом:

? Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;

? Если дерево T состоит из одного узла, то в список обхода записывается этот узел;

? Пусть дерево T имеет корень n и поддеревья T1, T2, ... Tm, как показано на рисунке

Тогда для различных способов обхода имеем следующее:

1.  Прямой обход. Сначала посещается корень n, затем в прямом порядке узлы поддерева T1, далее все узлы поддерева T2 и т. д. Последними посещаются в прямом порядке узлы поддерева Tm.