Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритмы поиска: последовательный, двоичный, метод золотого сечения, интерполяционный.
а)Последовательный 1)i=1 2)Смотрим i-й элемент. То, что нужно? 3)Если нет то i=i+1 и возвращаемся к пунтку 2 Время работы последовательного поиска пропорционально длинне самого массива, предварительная сортировка не обязательна. б)Двоичный: Проверяем средний элемент, если не подходит, то отбрасываем половину массива.. Проверяем средний элемент в оставшейся половине, если не подходит то отбрасываем половину от оставшихся… в)Метод золотого сечения: f(x):[a;b]→min, f(x)ϵC([a;b]) Делим отрезорк двумя симметричными точками и вычисляем в них функцию. Отбрасываем тот отрезок Где значение функции максимально по модулю На оставшемся отрезке нужно добавить только одну точку Продолжаем…
г) Интерполирующий Public int interpolationSearch (int [] SortedArray, int toFind) { //Возвращает индекс элемента со значением toFind //иначе возвращает -1 Int mid; Int low=0; Int high = SortedArray.Length-1; While (sortedArray[low]<toFind && sortedArray[high]>toFind) { Mid = low + ((toFind – sortedArray[low])*(high-low))/(sortedArray[high]-sortedArray[low]) If (sortedArray[mid]<toFind) Low =mid+1; Else if(sortedArray[mid>toFind]) High=mid-1; Else return mid; } If (sortedArray[low]==toFind) Return low; Else if (sortedArray[high]==toFind) Return high; Else return -1; }
Алгоритмическая сложность в среднем O(log(log N)) В худшем случае O(N) Вообщем принцип работы такой, в цикле мы проверяем нахождения нашего элемента с значением toFind, но рассматриваем не весь массив а только массив лежащий в границах low и high постепенно мы сужаем эти границы и так доходим до этого элемента, но в основном цикле мы не рассматриваем элемента которые лежат на границе массива, поэтого после его завершения если ничего мы не нашли то мы проверяем самый первый и самый последние элемента, если находим то возвращаем его индекс, если не находим то возвращаем -1
Сортировки: пузырьковая, расчёской.
1)Пузырьковая: В сортировке пузырьком, когда сравниваются два элемента, промежуток (расстояние друг от друга) равен 1. Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²). Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Сортировка расчёской Сортировка расчёской — это довольно упрощённый алгоритм сортировки.Сортировка расчёской улучшает сортировку пузырьком, и конкурирует с алгоритмами, подобными быстрой сортировке. Основная идея — устранить черепах, или маленькие значения в конце списка, которые крайне замедляют сортировку пузырьком (кролики, большие значения в начале списка, не представляют проблемы для сортировки пузырьком). Основная идея сортировки расчёской в том, что этот промежуток может быть гораздо больше, чем единица.
Void sort (data* array, dword size) { Dword jump = size; Bool swapped = =true; While (jump>1 || swapped) { If(jump > 1) Jump = (dword)(jump/1.25); Swapped = false; For (dword i =0; i+jump < size; i++) If (array[i] > array[i+jump]) Swap(array,i,i+jump), swapped = true } }
Сортировка слиянием. Для решения задачи сортировки эти три этапа выглядят так: Сортируемый массив разбивается на две части примерно одинакового размера; Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом; Два упорядоченных массива половинного размера соединяются в один.
1) Рекурсивное разбиение задачи на меньшие происходит до тех пор, пока размер массива не достигнет единицы (любой массив длины 1 можно считать упорядоченным).
2.1 Cоединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем два подмассива. Пусть также, элементы подмассивов в каждом из этих подмассивов отсортированы по возрастанию. Тогда: 2.2. Слияние двух подмассивов в третий результирующий массив.
На каждом шаге мы берём меньший из двух первых элементов подмассивов и записываем его в результирующий массив. Счетчики номеров элементов результирующего массива и подмассива из которого был взят элемент увеличиваем на 1. 2.3. "Прицепление" остатка. Когда один из подмассивов закончился, мы добавляем все оставшиеся элементы второго подмассива в результирующий массив.
Быстрая сортировка. Быстрая сортировка часто называемая qsort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков. Краткое описание алгоритма: 1)выбрать элемент, называемый опорным. 2)сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие. 3)повторить рекурсивно для «меньших» и «больших». Примечание: на практике обычно разделяют сортируемое множество не на три, а на две части: например, «меньшие опорного» и «равные и большие». Такой подход в общем случае оказывается эффективнее, так как для осуществления такого разделения достаточно одного прохода по сортируемому множеству и однократного обмена лишь некоторых выбранных элементов. /* сортирует v[0]..v[n-1] по возрастанию */ Void quicksort (int v[], int n) { Int i, last; If (n <= 1) //ничего не делать Return; Swap (v,0,rand()%n);//разделить Last=0; For (i=1; i<n; i++) If (v[i] < v[0]) Swap(v,++last,i); Swap(v,0,last) //сохранить разделитель Quicksort (v,last); //рекурсивно отсортировать Quicksort (v+last+1,n-last-1)//каждую часть}
|
||||||
Последнее изменение этой страницы: 2017-02-05; просмотров: 752; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.117.162 (0.016 с.) |