где tлин - среднее время линейного поиска; (1)

N - размер массива.

tдв = log2 N,

где tдв - среднее время двоичного поиска; (2)

N - размер массива.

3 Алгоритмизация задачи

Решение задачи, поставленной в курсовом проекте, включает в себя следующие этапы:

Формирование исходного неупорядоченного массива и запись его в текстовый файл.

Линейный поиск заданного элемента в массиве.

Построение двоичного дерева.

Сортировка исходного массива деревом.

Двоичный поиск заданного элемента в отсортированном массиве.

Запись отсортированного массива в текстовый файл.

3.1 Ввод и вывод массива

Схема алгоритма создания неупорядоченного массива приведена в приложении В. Алгоритм реализован в виде процедуры Vvod (приложение Б).

Шаг 1. Если n?16, то переход на шаг 2, иначе шаг 4.

Шаг 2 Ввод осуществляется с клавиатуры в цикле с параметром i:

for i:=1 to n do read(A[i]).

Шаг 3. Запись каждого элемента в текстовый файл F_1 после считывания.

Шаг 4. Массив формируется с помощью датчика случайных чисел также в цикле с параметром i : for i:=1 to n do

A[i]:=random(1000);

Шаг 5. Запись сформированного массива в текстовый файл F_1, элементы которого располагаются в четырёх позициях.

Процедура Vivod выводит на экран сформированный неупорядоченный массив.

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

Схема алгоритма линейного поиска приведена в приложении В. Алгоритм реализован в виде процедуры Lin_Poisk (приложение Б).

Шаг 1. Установить счетчик количества сравнений в 0: k:=0.

Шаг 2. Последовательное сравнение элементов исходного массива с заданным элементом x в цикле с параметром i.

Шаг 3. Элемент массива равен искомому элементу: a[i]=x, то счетчику присваивается индекс искомого элемента: k:=i, а также осуществляется выход из цикла с помощью процедуры break;

Шаг 4. Если k?0, тогда шаг 5, иначе шаг 6.

Шаг 5. Вывод на экран сообщения Writeln (`Element naiden. Sravnenii-`,k).

Шаг 6.Вывод на экран сообщения Writeln (`Element ne naiden').

3.3 Построение двоичного дерева

Процедура Tree представляет исходный массив A в виде дерева B. Формирование двоичного дерева выполняется следующим образом:

Шаг 1. Обнуляются поля первого элемента, содержащего левый, правый и обратный указатели b[1,3]:=0; b[1,4]:=0; b[1,5]:=0.

Шаг 2. Записываются элементы массива в получаемое дерево. В дереве b заполняются первые 2 поля - поле значения и признака. Первый элемент является корнем дерева

Шаг 3. Цикл организации двоичного дерева. Для каждого элемента массива (дерева), начиная со второго, необходимо выполнять следующие действия:

Шаг 3.1. Просмотр начинается со сравнения i-го элемента с корнем дерева, т.е. индекс k устанавливается в единицу k:=1.

Шаг 3.2. Сравнение: если i-й элемент массива меньше корня дерева, тогда его необходимо записать в левую ветвь j:=3, иначе - в правую ветвь j:=4.

Шаг 3.3. Проверка: если у k-го элемента есть левый или правый потомок, то переход на Шаг 3.4, иначе - переход на Шаг 3.5.

Шаг 3.4. За индекс k необходимо взять значение переменной s, которое содержит указатель правого или левого потомка k-го элемента и переход на Шаг 3.2.

Шаг 3.5. В поле указателя левого или правого потомка k-го элемента записывается значение индекса i. Поля i-го элемента, содержащие указатели левого, правого потомков и предка, обнуляются.

Данный алгоритм реализован в виде процедуры Tree (Приложение Б). Схема алгоритма процедуры Tree представлена в Приложении В.

3.4 Сортировка двоичным деревом

Идея сортировки деревом заключается в следующем. Если у элемента есть левая ветвь, то элемент с наименьшим значением признака надо искать на этой ветви. Если у элемента левой ветви нет, то он должен быть перенесён в результирующий массив b1. После этого очередной элемент разыскивается в правой ветви, если она есть, или возвращается по обратному указателю. После возвращения к какому-либо элементу по левой или правой ветви дальнейшие действия идут так, как будто у этого элемента соответствующей ветви нет. И так до тех пор, пока все элементы исходного массива, образующие двоичное дерево, не будут упорядочены по возрастанию.

Алгоритм сортировки деревом приведен ниже:

Шаг 1. Записываются элементы исходного массива (дерева) в результирующий массив (сортируемое дерево). Просмотр дерева начинается с первого элемента i:=1. Устанавливается счетчик, индекс для просмотра сортируемого дерева k:=0.

Шаг 2. Проверяется i-й элемент массива (дерева) на наличие левого потомка. Если он имеется, то за i-й элемент берется левый потомок и повторяется Шаг 2. Увеличивается счетчик количества перестановок m:=m+1.

Шаг 3. Увеличение счетчика k, в сортируемом массиве берется следующий элемент k:=k+1 и вместо него записывается i-й элемент.

Проверяется i-й элемент массива (дерева) на наличие правого потомка. Если он имеется, то за i-й элемент берется правый потомок и повторяется Шаг 2. Увеличивается счетчик количества перестановок m:=m+1.

Шаг 4. Индексу j присваивается значение индекса i j:=i, за индекс i берется обратный указатель (предок) i:=b[i,5], и если предок существует, то происходит следующая проверка: если предок (i-й элемент) больше своего потомка (j-й элемент), то повторить Шаг 3, иначе повторить Шаг 4.

Шаг 5. Увеличение счетчика перестановок m:=m+1.

Шаг 6. Запись отсортированного массива (дерева) в файл.

3.5 Двоичный поиск

Схема алгоритма двоичного поиска приведена в приложении В. Алгоритм реализован в виде процедуры Dv_Poisk (приложение Б).

Шаг 1. Установить начальные значения верхнего и нижнего индекса, счетчика сравнений k и : vi:=N, ni:=1, k:=0 и f:=false,так как элемент ещё не найден.

Шаг 2. Нахождение среднего элемента массива: sri:=((ni+vi) div 2).

Шаг 3. Увеличение счетчика k на единицу: k:=k+1;

Шаг 4. Если средний элемент равен искомому: a[sri]=x, то элемент найден: f:=true;

Шаг 5. Если x>a[sri] переход на шаг 6, иначе на шаг 7.

Шаг 6. За новое значение ni принимается sri+1, а значение vi не меняется.

Шаг 7. За новое значение vi принимается sri-1, а значение ni не меняется.

Шаг 8. Повторение цикла до тех пор, пока счетчик не станет больше максимального количества сравнений: k>log2n , либо элемент не будет найден.

Шаг 9. Если f:=true, то выполняется шаг 10, иначе шаг 11.

Шаг 10. На экран выводится: (`Element naiden, Index=', sri,'. Sravnenii `,k).

Шаг 11.На экран выводится: (`Element ne naiden').

3.6 Запись в файл

Схема алгоритма записи в файл упорядоченного массива приведена в приложении В. Алгоритм реализован в виде процедуры Save_To_File (приложение Б).

Шаг 1. При n?16 массив записывается в файл после каждой перестановки.

Шаг 2. При n?128 массив записывается в файл через каждые 10 перестановок.

Каждый элемент отсортированного массива располагается в четырёх позициях.

4 Инструкции по пользованию программой

4.1 Руководство пользователя

Программа, реализованная в соответствии с задачей, поставленной на курсовом проекте, написана на языке Turbo Pascal 7.0. Для запуска программы необходимо иметь компилятор Turbo Pascal 7.0. После запуска программы следует нажать комбинацию клавиш Ctrl+F9. В появившемся окне будет сообщение с просьбой ввести число элементов. Введите целое число n от 16 до 1024 элементов (можно и меньше 16), а затем нажмите клавишу Enter. Если введено n?16, то ввод элементов надо осуществить с клавиатуры, то есть вручную. Каждый вводимый элемент должен быть положительным и меньше 1000.

Если введено n>16, то программа сформирует массив самостоятельно при помощи датчика случайных чисел;

Дальше потребуется ввести элемент для поиска - x. Затем нажать Enter.

В дальнейшем программа автоматически выведет результаты поисков: линейного и двоичного. Результат включает в себя:

- для линейного поиска - количество сравнений;

- отсортированный массив, где все элементы расположены по возрастанию значений;

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

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

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. Результаты линейного поиска

Страницы: 1, 2, 3