Курсовая работа: Анализ алгоритмов нечисленной обработки данных

- для двоичного поиска – количество сравнений и перестановок, а также индекс искомого элемента;

Все результаты приведены в приложении Г.

4.2 Руководство программиста

Программа, представленная в данном курсовом проекте, разработана на языке высокого уровня – Turbo Pascal 7.0. Она состоит из основной программы и 7 подпрограмм (процедур).

Описания процедур приведены ниже.

4.2.1 Процедура VVod

Предназначена для формирования массива длиной до 1024 элементов. Процедура использует локальную переменную i для обращения к элементам массива. Входные параметры (в скобках указан способ передачи): n – длина массива (по значению), A – формируемый массив (по ссылке).

4.2.2 Процедура Vivod

Данная процедура выводит на экран сформированный массив, используя те же входные параметры, что и процедура VVod.

4.2.3 Процедура Save_To_File

Предназначена для записи во внешний текстовый файл сортируемый массив после заданного числа перестановок. Входные параметры: текстовый файл F(по ссылке), n – длина массива, a – записываемый сортируемый массив, m – количество перестановок.

4.2.4 Процедура Lin_Poisk

Эта процедура предназначена для поиска заданного элемента методом линейного поиска. Входные параметры: n – длина массива, a – исходный массив, x – заданный элемент. Локальные переменные: i – индекс элемента, счетчик, k – количество сравнений.

4.2.5 Процедура Dv_Poisk

Данная процедура реализует двоичный поиск. Входные параметры – те же, что и в процедуре Lin_Poisk. Локальные переменные: k – количество сравнений, ni – индекс нижней границы массива, vi – индекс верхней границы массива, sri – индекс среднего элемента массива.

4.2.6 Процедура Tree

Для построения дерева из исходного массива используется процедура Tree. Она формирует дерево b из массива a. Входные параметры: a - исходный массив (по значению), n – длина массива (по значению). Выходной параметр: b – двумерный массив (дерево). Локальные переменные: i,j – индексы элемента в дереве.

4.2.7 Процедура Tree_Sort

Сортирует дерево, полученное из исходного массива. Входные параметры: b – исходное дерево (по значению), n – длина массива (по значению). Выходной параметр: b1 – результирующий массив (отсортированное дерево). Локальные переменные: k – количество узлов в дереве, m – количество перестановок, i1 – индекс элемента в дереве (массиве).

4.3 Область и условия применения программы

В данной программе были разработаны алгоритмы нечисленной обработки данных – линейный и двоичный поиск, сортировка деревом. Сортировку деревом очень удобно использовать, когда необходимо сэкономить максимально возможно количество времени, но для представления дерева требуются большие затраты дополнительной памяти.

Программа является познавательной, её целесообразно использовать в качестве обучающего примера.

5 Анализ результата

На основе проведенных тестов программы был проведен анализ алгоритмов нечисленной обработки данных на примере массива длиной в 16, 128, 512, 1024 элементов.

5.1 Линейный поиск

Для проведения анализа линейного поиска в качестве заданного элемента были взяты числа, расположенные в начале, в середине, в конце и в произвольной позиции массива. Для линейного поиска теоретическое время поиска определяется по формуле Tтеор.=[время сравнения]×N/2

Результаты приведены в нижеследующей таблице.

Таблица 2. Результаты линейного поиска

Количество элементов массива	16		128		512		1024
Позиция элемента	Искомый элемент	Количество сравнений	Искомый элемент	Количество сравнений	Искомый элемент	Количество сравнений	Искомый элемент	Количество сравнений
Первая	5	1	0	1	48	1	0	1
Средняя	15	8	85	64	894	256	465	512
Последняя	3	16	314	128	191	512	242	1024
Произвольная	4	13	272	5	747	511	425	10
Элемент отсутствует	101	16	999	128	982	512	987	1024
Среднее значение	10,8		65,2		358,4		513,6
Теоретическое значение	8		64		256		512

По данным таблицы 2 построены графики функции зависимости времени поиска от количества элементов массива (рисунок 2).