Алгоритмы поиска. Поиск наибольшего числа в массиве. Поиск заданного числа в массиве.
Алгоритмы поиска. Поиск с порогом. Двоичный поиск.
Двоичный поиск т массивами так: есть упорядоченный массив, берем число из середины массива, сравниваем с искомым. Если оно оказалось больше, значит искомое число в первой половине массива, если меньше — во второй. Продолжаем делить оставшуюся половину, когда находим нужное число возвращаем его индекс, если не находим возвращаем null.
Алгоритмы на графах. Граф – совокупность точек и линий, в которой каждая линия соединяет 2 точки. Точки называются вершинами, а линии – ребрами. Вершины, соединенные ребрами называются смежными. Число ребер, инцидентных вершине называют степенью вершины. Граф, содержащий кратные ребра называют мультиграфом. Если 2 вершины соединяют 2 ребра то они называются кратными. Ребро, соединяющее 2 вершины может иметь направление от одной вершины к другой. В этом случае это ребро называется направленным или ориентированным. Ребра орграфа называются дугами. Маршрут (путь) – последовательность ребер в неориентированном графе в котором конец каждого ребра совпадает с началом следующего. Число ребер маршрута называется длинной.Основные задачи, решаемые в теории графов: Поиск в ширину. Отправляясь из в. А мы обходим все смежные вершины, каждая вершина становится источником. Поиск в глубину. Идея поиска в глубину заключается в след.: отправляясь от текущей вершины мы находим новую смежную с ней вершину, которую помечаем как пройденную и объявляем текущей. После этого процесс возобновляется, если новой смежной вершины нет (тупик), то возвращаемся к той вершине, из которой попали в текущую и повторяем попытку. Если т.о. доходим до конечной точки, т.е. есть путь. Если все вершины исчерпаны и нет результата, то такого пути не существует. Особенностью является то, что найденный путь не обязательно является кратчайшим. Эйлеровы циклы. Необходимо найти циклы, походящие по каждой дуге только один раз. Эта задача выполнима, если: 1) граф должен быть связным (для любых 2х вершин существует соединяющий их путь); 2) для неорграфа число ребер в каждой вершине должно быть четким; 3) задача Прима-Каскала. Суть: дан граф с N вершинами, длины ребер заданы матрицей, необзодимо найти дерево минимальной длины. Как известно, дерево с N вершинами имеет (N-1) ребер. Для решения задачи каждое ребро надо выбирать жадно (лишь бы не возникло циклов). Т.о. (N-1) раз выбираем самое короткое ребро из еще не выбранных ребер при условии, что они не образуют цикла с уже выбранными. Алгоритм Дейтстры Основная задача: дана дорожная сеть, где города и развилки будут вершинами, а дороги ребрами. Требуется найти кратчайший путь м-ду вершинами. Необходимо иметь 3 массива из N чисел каждый: Содержит метки с 2мя значениями False (вершины еще не рассмотрены) и true. Содержит расстояние – текущее кратчайшее состояние от начальной точки до соответствующей вершины. Содержит номера вершин. Матрица состояния.