Анализ алгоритмов нечисленной обработки данных (стр. 1 из 4)
Аннотация
Данный курсовой проект посвящен рассмотрению и изучению алгоритмов нечисленной обработки данных – линейный и двоичный поиск, а также упорядочение массива методом сортировки деревом. Алгоритмы реализованы на языке Turbo Pascal 7.0.
Содержание
1 Постановка задачи. 3
2 Метод решения. 4
2.1 Сортировка двоичным деревом. 4
2.1.1 Организация массива в виде двоичного дерева. 4
2.1.2 Простейший способ. 4
2.1.3 Описание построения дерева. 5
2.1.4 Описание сортировки деревом. 6
2.2 Линейный поиск. 7
2.3 Двоичный поиск. 8
2.4 Метод оценки времени поиска. 10
3 Алгоритмизация задачи. 11
3.1 Ввод и вывод массива. 11
3.2 Линейный поиск. 12
3.3 Построение двоичного дерева. 12
3.4 Сортировка двоичным деревом. 13
3.5 Двоичный поиск. 14
3.6 Запись в файл. 15
4 Инструкции по пользованию программой. 16
4.1 Руководство пользователя. 16
4.2 Руководство программиста. 16
4.2.2 Процедура Vivod. 17
4.2.3 Процедура Save_To_File. 17
4.2.4 Процедура Lin_Poisk. 17
4.2.5 Процедура Dv_Poisk. 17
4.2.6 Процедура Tree. 18
4.2.7 Процедура Tree_Sort 18
4.3 Область и условия применения программы.. 18
5 Анализ результата. 19
5.1 Линейный поиск. 19
5.2 Двоичный поиск. 20
5.3 Анализ сортировки деревом. 22
Заключение. 24
Список литературы.. 25
Приложение А.. 26
Приложение Б. 29
Необходимо:
1) Создать набор входных данных длиной 16, 128, 512, 1024 элементов для программ поиска и сортировки. Для массива длиной, не превышающей 16 элементов, предусмотреть ввод элементов с клавиатуры, в остальных случаях – генератором случайных чисел.
2) Разработать алгоритм и программу упорядочения методом минимальной по памяти турнирной сортировки.
3) Разработать алгоритм и программу поиска заданного элемента в неупорядоченных массивах. Метод линейного и двоичного поиска.
4) Осуществить отладку программы на тестовых примерах.
5) Оценить время сортировки и поиска информации для массивов заданной длины.
Требования к программе:
1) основные алгоритмы оформить в виде подпрограмм;
2) программа должна быть самодокументированной;
Обеспечить формирование массива:
1) путем ввода элементов с клавиатуры при n≤16;
2) с помощью генератора случайных чисел при n>16;
2.1 Сортировка двоичным деревом
2.1.1 Организация массива в виде двоичного дерева
Чтобы облегчить поиск в массиве элемента с нужным значением признака, не обязательно упорядочивать его по этому признаку в линейную последовательность. Двоичным называется ориентированное дерево, у которого в каждую вершину, кроме одной, корня дерева, заходит одна дуга и из каждой вершины исходит не более двух дуг. Ветвью дерева называют поддерево, состоящее из некоторой дуги данного дерева, ее начальной и конечной вершин, а также всех вершин и дуг, лежащих на всех путях, выходящих из конечной вершины этой дуги.
Сначала рассматривается весьма простой метод построения дерева, организующего массив. При этом методе, в известном смысле, отдаются на волю случая. Как будет видно, можно все же получить хорошие результаты, если в исходном состоянии массива значения признака, взятые в порядке возрастания номеров элементов, образуют хорошо перемешанную последовательность.
Первый элемент массива поместим в корень дерева. Со вторым элементом поступают так. Сравнивают значение p2 признака этого элемента со значением p1 признака элемента, помещенного в корень дерева (т.е первого элемента).
Если p2<p1, то к корню пририсовывают дугу, направленную влево, и помещают второй элемент в конце этой дуги. Если же p2≥p1, то делают то же самое, но дугу направляют вправо. В общем случае, когда требуется выбрать место на дереве для i-го элемента массива (к этому моменту дерево уже содержит i- 1 вершину и i-2 дуги), поступают следующим образом. В процессе выбора просматривается некоторый путь по дереву (цепочка смежных неповторяющихся вершин и дуг), выходящий всегда из корня. Чтобы, находясь в некоторой вершине пути, определить, обрывается ли путь в этой вершине, а если нет, то какая вершина следующая, применяется один и тот же прием для каждой вершины, в том числе и для корня. Сравнивается значение pi признака размещаемого элемента со значением pk признака элемента, помещенного в данной вершине. Если pi <pk , то смотрят, исходит ли из этой вершины дуга влево. Если исходит, то вершина в конце этой дуги будет следующей вершиной пути, если нет, то достраивают эту дугу и помещают i-й элемент в ее конце. Если же pi ≥ pk , то все происходит аналогично, но с дугой, направленной вправо. Таким образом, из каждой вершины может исходить самое большее две дуги, как и полагается для двоичного дерева.
Метод организации массива в виде двоичного дерева требует несколько больших затрат как на организацию массива, так и на поиск в нем нужного элемента, чем это минимально необходимо. Впрочем, это увеличение не столь существенно. Этот метод оптимален по порядку роста трудоемкости поиска в зависимости от размера массива. Это означает, что для данного метода, так же как и для оптимального, эта зависимость имеет вид c∙log n (с точностью до величин меньшего порядка роста) и разница заключается лишь в значении коэффициента пропорциональности c.
2.1.3 Описание построения дерева
Пусть каждый элемент исходного массива a состоит из двух полей: признака a[i,1] и собственно значения элемента a[i,2], где i – номер элемента в исходном массиве. Чтобы описать массив, упорядоченный в виде дерева, каждый элемент надо снабдить ещё, по меньшей мере двумя полями, содержащими номера элементов, расположенных в конце левой и правой дуг, исходящих из вершины, в которую помещён данный элемент. Этих двух дополнительных полей достаточно для построения дерева и для поиска в нем. Однако для других операций с деревом желательно иметь ещё одно поле, содержащее номер того элемента, к которому подвешен (безразлично, слева или справа) данный элемент. Пусть исходный массив уже содержит все необходимые поля, то есть, описан как
mas=array [1..n, 1..5] of integer,
но значения дополнительных полей a[i,3], a[i, 4] и a[i,5] перед началом работы алгоритма не определены. Называются эти поля соответственно левым, правым и обратным указателем. Если после окончания работы алгоритма левый (правый) указатель какого-либо элемента содержит нуль, это означает, что из вершины, в которую помещён данный элемент, не исходит левая (правая) дуга. Обратный указатель содержит нуль только для первого элемента, который помещён в корне дерева. Остальные детали процедуры ясны из приведённого в начале этого раздела словесного описания алгоритма.
2.1.4 Описание сортировки деревом
Имеются два массива: a – исходный и b – отсортированный. В массиве b элементы массива a расположены в порядке возрастания значения признака. Если у элемента есть левая ветвь, то элемент с наименьшим значением признака разыскивается на этой ветви. Если у элемента левой ветви нет, то он переносится в массив b, так как в массиве нет элемента с меньшим значением признака. После этого очередной элемент разыскивается в правой ветви, если она есть, или возвращается по обратному указателю. После возвращения к какому-либо элементу по левой или правой ветви дальнейшие действия идут так, как будто у этого элемента соответствующей ветви нет.
Для неупорядоченного исходного массива единственным способом нахождения заданного элемента в этом массиве является линейный поиск. Этот метод состоит в последовательном сравнении каждого элемента массива с заданным для поиска элементом. При линейном поиске иногда просматривается половина, а то и больше элементов исходного массива. Этот метод удобен и прост для массивов с меньшей длиной. Для массивов большей длины это метод вызывает затруднения, так как время поиска будет очень медленным.
Применим метод линейного поиска на примере поиска в неупорядоченном массиве A элемента X=11. Дан массив A, который состоит из 10 элементов.
Таблица 1 – Линейный поиск
| № Элемента | Сравнение | № Проверки |
| 1 | 5  11 | 1 |
| 2 | 12≠11 | 2 |
| 3 | 68≠11 | 3 |
| 4 | 0≠11 | 4 |
| 5 | 92≠11 | 5 |
| 6 | 87≠11 | 6 |
| 7 | 7≠11 | 7 |
| 8 | 32≠11 | 8 |
| 9 | 11=11 | 9 |
| 10 | 24 |
Из таблицы 1 видно, что для нахождения элемента X=11 пришлось выполнить 9 сравнений. Если бы элемента 11 не оказалось под номером 9, то поиск выполнялся бы до его нахождения, либо до окончания массива.
2.3 Двоичный поиск
Одним из эффективных методов поиска в больших отсортированных массивах является двоичный, другое название бинарный, поиск. Так называемый, поиск методом деления пополам. Вместо просмотра подряд всех элементов массива делим его пополам. Так как массив отсортирован, то, сравнивая искомый элемент со значением среднего элемента массива, можно сделать вывод, о том, что может ли быть элемент с таким значением в массиве и в какой половине он находиться, то есть, определить область дальнейшего поиска. Затем делится пополам та часть массива, в которой находится элемент, и так до тех пор, пока рассматриваемая часть массива получится состоящей из одного элемента.
Допустим, есть упорядоченный по возрастанию массив из целых чисел. Необходимо определить, содержит ли этот массив некоторое число (образец).
Алгоритм двоичного поиска:
1. Сначала образец сравнивается со средним (по номеру) элементом массива
- если образец равен среднему элементу, то задача решена;
- если образец больше среднего элемента, то это значит, что искомый элемент расположен, ниже среднего элемента (между элементами с номерами sre+1), и за новое значение verhe принимается sre+i, а значение nize не меняется;