Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Результат поиска
Наименование:
Курсовик СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ ПОИСКА, РЕАЛИЗОВАННЫХ В РАЗЛИЧНЫХ ЯЗЫКАХ ПРОГРАММИРОВАНИЯ
Информация:
Тип работы: Курсовик.
Добавлен: 17.12.2013.
Год: 2011.
Страниц: 50.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
Введение 3 Глава 1 4 Линейный алгоритм поиска 4 Бинарный алгоритм поиска 5 Сортировка 7 Записи 10 GetTickCount 13 DateTime 13 Глава 2 16 Delphi. 16 C++. 20 C# 23 Глава 3 25 Заключение 28 Список литературы 29 Приложение 30
Введение
С помощью ЭВМ можно решать самые разные задачи, в том числе задачу поиска. Поиск может требоваться в различных ситуациях, например, когда нужно найти элемент в массиве. Для решения этой задачи используются алгоритмы поиска. В настоящее время довольно часто встречается задача поиска в большом массиве данных, когда необходимо определить, имеется ли данное значение в массиве. Целью поиска является нахождение данных, полностью совпадающих с заданным ключом поиска. Для решения данной задачи используются алгоритмы поиска. Их производительность при этом играет важную роль. Ведь чем меньше времени займет поиск данных, тем удобнее алгоритм поиска в использовании. На данный момент существует множество алгоритмов поиска, и какие из них лучше подходят для решения задачи поиска в массивах данных сказать очень сложно. Цель данной курсовой работы - исследовать производительность алгоритмов поиска в различных языках программирования, а также выяснить, какой из них наиболее подходит для решения задачи поиска. В работе мы выделяем две части: теоретическую и практическую. Теоретические задачи работы: · обзор известных алгоритмов поиска; · обзор реализации алгоритмов поиска в таких языках программирования, как C++, C#, Delphi. Практические задачи: · реализация алгоритмов поиска на С++, C#, Delphi; · их сравнительный анализ. Работа состоит из трех глав. В первой главе мы рассмотрим известные алгоритмы поиска, для сравнения взяты два: линейный и бинарный. Сравнивать мы их будем отдельно, так как сопоставить два этих алгоритма нерационально, потому что бинарный применим только к отсортированным массивам данных. Во второй главе исследуются используемые нами языки программирования. В третьей главе описано проведенное нами исследование. В программной части для представленной курсовой работы используется язык Delphi в среде программирования Borland Delphi 7, а также языки С++ и С# в среде программирования Microsoft Visual Studio 2010. Глава 1
В настоящее время довольно часто встречается задача поиска в большом массиве данных, когда необходимо определить, имеется ли данное значение в массиве. Для решения данной задачи используются алгоритмы поиска. Алгоритм поиска - это точное предписание поисковой машине совершить определенную последовательность действий, учесть определенные факторы для достижения наиболее релевантной выдачи за конечное число шагов. На данный момент существует множество алгоритмов поиска. Все методы можно разделить на статические и динамические. При статическом поиске массив значений не меняется во время работы алгоритма. Во время динамического поиска массив может перестраиваться или изменять размерность. Также методы поиска можно разделить на методы, использующие истинные ключи и на методы, работающие по преобразованным ключам. В данном случае "ключом" называют то значение, которое мы ищем. Основная задача поиска - найти в заданной совокупности данных элемент, который обладает заданным свойством. Большинство задач поиска сводится к поиску элемента с заданным значением в массиве. Для данной работы мы взяли два наиболее распространенных алгоритма поиска: линейный и бинарный, который также можно назвать методом деления пополам. Рассмотрим используемые нами алгоритмы более подробно.
Линейный алгоритм поиска Данный алгоритм имеет простейшую реализацию. Он не накладывает никаких ограничений на массив. Принцип работы алгоритма заключается в том, что каждый элемент массива последовательно просматривается и сравнивается с ключом поиска. Если совпадение найдено поиск считается завершенным. Как правило, поиск происходит слева направо, то есть от меньших значений аргумента к большим. Исследования начинаются с первого элемента массива. Если искомое значение не равно значению данного элемента массива, то осуществляется переход к следующему элементу массива. Таким образом в результате каждой проверки область поиска уменьшается на один элемент. Так как массив неупорядочен, то не исключено, что искомое значение окажется первым элементом массива. Также не исключено, что искомое значение может оказаться последним. В этом случае алгоритм просматривается полностью. Таким образом, число сравнений зависит от того, на каком месте в массиве находится искомый элемент. В среднем количество сравнений можно вычислить по формуле (N + 1) Div 2, где N - количество элементов в массиве. Если искомого элемента в массиве нет, то число сравнений равно N. Эффективность алгоритма поиска O(N). Линейный алгоритм поиска не требует дополнительной памяти или обработки массива , и поэтому может работать в потоковом режиме при непосредственном получении данных из любого источника. Данный алгоритм часто используется в виде линейных алгоритмов поиска максимума или минимума. Реализация линейного алгоритма поиска осуществляется следующим образом: For i := 1 To N Do If A[i] = x Then k := i; Метод линейного поиска лучше всего использовать в небольших или в несортированных массивах. В иных случаях он малоэффективен.
Бинарный алгоритм поиска Еще его называют двоичным поиском, дихотомическим поиском, методом деления пополам, а также другими терминами, обозначающими эту идею. В отличие от линейного поиска, бинарный применим только к отсортированным массивам данных. Идея бинарного алгоритма поиска проста: мы делим массив пополам и сравниваем ключ поиска с элементом, который находится на границе получившихся половин. Отсортированность массива позволяет нам исключить из рассмотрения одну из половин, в соответствии с результатом сравнения. Принцип работы данного алгоритма заключается в следующем. В первом цикле делим весь наш исходный отсортированный массив пополам и сравниваем ключ поиска со средним значением, по которому делили массив. Если равенство соблюдается, то ключ поиска найден, иначе, если ключ поиска меньше этого среднего значения, то продолжим поиск в первой половине массива, в обратном случае, во второй части. В следующем цикле выбранную часть массива также делим пополам и, как и в предыдущем цикле, выполняем сравнение. В случае если ключ поиска не совпал с центральным элементом, выбираем нужную часть, и в следующем цикле будем работать уже с ней. Таким образом, после каждого сравнения отсекается ровно половина массива, сокращая тем самым область поиска. Так продолжается до тех пор, пока значение центрального элемента не совпадет с ключом поиска, либо не исчерпаются все элементы в получаемых подмассивах. Каждое сравнение уменьшает диапазон поиска приблизительно в два раза. Общее количество сравнений можно вычислить по формуле N * logN, где N - количество элементов в массиве. Реализация бинарного алгоритма поиска осуществляется следующим образом: Procedure Search; Var i, j, m: Integer; f: Boolean; Begin i := 1; j := N; f := False; While (i ‹= j) And Not f Do Begin m := (i + j) Div 2; If A[m] = x Then f := True Else If A[m] ‹ x Then i := m + 1 Else j := m - 1; End; End; На первом шаге мы рассматриваем весь массив. F показывает найден элемент или нет. m := (i + j) Div 2 можно заменить на m := i + (j - i) Div 2, так как i + (j - i) Div 2 = (2 * i + (j - i)) Div 2=(i + j) Div 2. Так как бинарный алгоритм поиска может быть применен только к отсортированному массиву, то предварительно массив нужно отсортировать.
Сравнивать данные алгоритмы мы будем по отдельности. Как было сказано ранее, нужно отсортировать массив, а для этого надо добавить сортировку в программный код. Рассмотрим алгоритм сортировки более подробно.
Сортировка Сортировка - это упорядочивание чисел в массиве, в котором первоначально элементы расположены в случайном порядке. Сортировка может быть выполнена: · по возрастанию - каждый следующий элемент больше предыдущего; · по убыванию - каждый следующий элемент больше предыдущего; · по невозрастанию - каждый следующий элемент не больше предыдущего, то есть меньше или равен ему; · по неубыванию - каждый следующий элемент не меньше предыдущего, то есть больше или равен ему. Сортировка важна и часто применяется в базах данных, так как поиск информации в упорядоченном массиве происходит гораздо быстрее. Алгоритмы сортировки отличаются друг от друга степенью эффективности, под которой понимается количество сравнений и количество обменов, происходящих в результате сортировки. Так как в задачах поиска операцию сортировки нужно выполнять для достаточно больших объёмов данных, то критическое значение имеет время сортировки. Поэтому эффективность алгоритма сортировки имеет очень большое значение. Разработано множество алгоритмов сортировки, отличающихся эффективностью в тех или иных наборах данных. Так как массив чисел у нас достаточно большой, то сортировка пузырьком и сортировка вставками нам ...
