Разработка системы задач (алгоритмы-программы) по дискретной математике — страница 4

  • Просмотров 3917
  • Скачиваний 207
  • Размер файла 88
    Кб

составляет С=О(N*logN). Быстрая сортировка Хоара. Метод предложен Ч.Э.Р.Хоаром в 1962 году. Идея метода. В исходном массиве А выбирается некоторый элемент Х (барьерный элемент). Основной целью алгоритма является запись Х «на свое место» в массиве, пусть это будет место k, такое, что слева от Х были элементы массива, меньшие или равные Х, а справа – элементы массива, большие Х, т.е. массив А будет иметь вид: (А[1],A[2],…,A[k-1]),A[k] (X), (A[k+1],…, A[n]). В

результате элемент A[k] находится на своем месте и исходный массив А разделен на две неупорядоченные части, барьером между которыми является элемент A[k]. Дальнейшие действия очевидны – независимо сортировать полученные части по той же логике до тех пор, пока не останутся части массива, состоящие из одного элемента, то есть пока не будет отсортирован весь массив. Графы. Представление графа в памяти компьютера Определим граф как

конечное множество вершин V и набор Е неупорядоченных и упорядоченных пар вершин и обозначим G=(V,E). Мощности множеств V и Е будем обозначать буквами N и М Неупорядоченная пара вершин называется ребром, а упорядоченная пара - дугой. Граф, содержащий только ребра, называется неориентированным; граф, содержащий только дуги, - ориентированным, или орграфом. Вершины, соединенные ребром, называются смежными. Ребра, имеющие общую вершину,

также называются смежными. Ребро и любая из его двух вершин называются инцидентными. Говорят, что ребро (u, v) соединяет вершины и и v. Каждый граф можно представить на плоскости множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам. В трехмерном пространстве любой граф можно представить таким образом, что линии (ребра) не будут пересекаться. Способы описания. Выбор соответствующей

структуры данных для представления графа имеет принципиальное значение при разработке эффективных алгоритмов. При решении задач используются следующие четыре основных способа описания графа: матрица инциденций; матрица смежности; списки связи и перечни ребер. Мы будем использовать только два: матрицу смежности и перечень ребер. Матрица смежности - это двумерный массив размерности N*N. 1, вершина с номером i смежна с вершиной с

номером j, 0, вершина с номером i не смежна с вершиной с номером j Для хранения перечня ребер необходим двумерный массив R размерности М*2. Строка массива описывает ребро. Достижимость Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей. Простой путь - это путь, в котором каждая дуга