Навигация
Анализ алгоритмов нечисленной обработки данных
32292
знака
12
таблиц
3
изображения
Аннотация
Данный курсовой проект посвящен рассмотрению и изучению алгоритмов нечисленной обработки данных – линейный и двоичный поиск, а также упорядочение массива методом сортировки деревом. Алгоритмы реализованы на языке 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 Постановка задачи
Необходимо:
1) Создать набор входных данных длиной 16, 128, 512, 1024 элементов для программ поиска и сортировки. Для массива длиной, не превышающей 16 элементов, предусмотреть ввод элементов с клавиатуры, в остальных случаях – генератором случайных чисел.
2) Разработать алгоритм и программу упорядочения методом минимальной по памяти турнирной сортировки.
3) Разработать алгоритм и программу поиска заданного элемента в неупорядоченных массивах. Метод линейного и двоичного поиска.
4) Осуществить отладку программы на тестовых примерах.
5) Оценить время сортировки и поиска информации для массивов заданной длины.
Требования к программе:
1) основные алгоритмы оформить в виде подпрограмм;
2) программа должна быть самодокументированной;
Обеспечить формирование массива:
1) путем ввода элементов с клавиатуры при n≤16;
2) с помощью генератора случайных чисел при n>16;
2 Метод решения
2.1 Сортировка двоичным деревом
2.1.1 Организация массива в виде двоичного дерева
Чтобы облегчить поиск в массиве элемента с нужным значением признака, не обязательно упорядочивать его по этому признаку в линейную последовательность. Двоичным называется ориентированное дерево, у которого в каждую вершину, кроме одной, корня дерева, заходит одна дуга и из каждой вершины исходит не более двух дуг. Ветвью дерева называют поддерево, состоящее из некоторой дуги данного дерева, ее начальной и конечной вершин, а также всех вершин и дуг, лежащих на всех путях, выходящих из конечной вершины этой дуги.
2.1.2 Простейший способ
Сначала рассматривается весьма простой метод построения дерева, организующего массив. При этом методе, в известном смысле, отдаются на волю случая. Как будет видно, можно все же получить хорошие результаты, если в исходном состоянии массива значения признака, взятые в порядке возрастания номеров элементов, образуют хорошо перемешанную последовательность.
Первый элемент массива поместим в корень дерева. Со вторым элементом поступают так. Сравнивают значение p2 признака этого элемента со значением p1 признака элемента, помещенного в корень дерева (т.е первого элемента).
Если p2<p1, то к корню пририсовывают дугу, направленную влево, и помещают второй элемент в конце этой дуги. Если же p2≥p1, то делают то же самое, но дугу направляют вправо. В общем случае, когда требуется выбрать место на дереве для i-го элемента массива (к этому моменту дерево уже содержит i- 1 вершину и i-2 дуги), поступают следующим образом. В процессе выбора просматривается некоторый путь по дереву (цепочка смежных неповторяющихся вершин и дуг), выходящий всегда из корня. Чтобы, находясь в некоторой вершине пути, определить, обрывается ли путь в этой вершине, а если нет, то какая вершина следующая, применяется один и тот же прием для каждой вершины, в том числе и для корня. Сравнивается значение pi признака размещаемого элемента со значением pk признака элемента, помещенного в данной вершине. Если pi <pk , то смотрят, исходит ли из этой вершины дуга влево. Если исходит, то вершина в конце этой дуги будет следующей вершиной пути, если нет, то достраивают эту дугу и помещают i-й элемент в ее конце. Если же pi ≥ pk , то все происходит аналогично, но с дугой, направленной вправо. Таким образом, из каждой вершины может исходить самое большее две дуги, как и полагается для двоичного дерева.
Метод организации массива в виде двоичного дерева требует несколько больших затрат как на организацию массива, так и на поиск в нем нужного элемента, чем это минимально необходимо. Впрочем, это увеличение не столь существенно. Этот метод оптимален по порядку роста трудоемкости поиска в зависимости от размера массива. Это означает, что для данного метода, так же как и для оптимального, эта зависимость имеет вид c∙log n (с точностью до величин меньшего порядка роста) и разница заключается лишь в значении коэффициента пропорциональности c.
Похожие работы
... процессов и явлений, использовать графику машины для повышения наглядности изучаемого материала. Использование пакетов прикладных учебных программ, готового программного обеспечения является одной из самых важных компонентов формирования компьютерной грамотности. При этом значительно расширяются межпредметные связи между многими учебными дисциплинами, особенно между математикой и информатикой. ...
... практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков. Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы. Преобразования циклов ...
... і слова в орфографічному словнику контроль орфографічної правильності його написання слід здійснювати за правилами орфографії. Зараз готують до затвердження наступний п’ятий правопис. Тому в процесі редагування треба враховувати динамічність правопису і слідкувати за правописними змінами. Відхилення від правильного написання допустиме лише тоді, коли в повідомленні йдеться про юридичну справу і ...
... дисциплин. Горн рассматривает эти вопросы, отталкиваясь в своих рассуждениях от профессиональных интересов ученых в этой области еще на, стадии получения ими образования: «Информационно-компьютерная наука рассматривает прагматические аспекты использования символов их пользователями и интерпретаторами в качестве еще одного центрального вопроса таким же образом, как эти аспекты должны исследоваться ...
0 комментариев