Навигация
Метод оценки времени поиска
32292
знака
12
таблиц
3
изображения
2.4 Метод оценки времени поиска
Для сравнительной оценки быстроты поисков, введем условную единицу времени, равную времени, затраченному на сравнение двух элементов. Для теоретической оценки средней быстроты поиска используем формулы:
tлин = 
,
где 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. Запись отсортированного массива (дерева) в файл.
Похожие работы
... процессов и явлений, использовать графику машины для повышения наглядности изучаемого материала. Использование пакетов прикладных учебных программ, готового программного обеспечения является одной из самых важных компонентов формирования компьютерной грамотности. При этом значительно расширяются межпредметные связи между многими учебными дисциплинами, особенно между математикой и информатикой. ...
... практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков. Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы. Преобразования циклов ...
... і слова в орфографічному словнику контроль орфографічної правильності його написання слід здійснювати за правилами орфографії. Зараз готують до затвердження наступний п’ятий правопис. Тому в процесі редагування треба враховувати динамічність правопису і слідкувати за правописними змінами. Відхилення від правильного написання допустиме лише тоді, коли в повідомленні йдеться про юридичну справу і ...
... дисциплин. Горн рассматривает эти вопросы, отталкиваясь в своих рассуждениях от профессиональных интересов ученых в этой области еще на, стадии получения ими образования: «Информационно-компьютерная наука рассматривает прагматические аспекты использования символов их пользователями и интерпретаторами в качестве еще одного центрального вопроса таким же образом, как эти аспекты должны исследоваться ...
0 комментариев