Аннотация
Данный курсовой проект посвящен рассмотрению и изучениюалгоритмов нечисленной обработки данных – линейный и двоичный поиск, а такжеупорядочение массива методом сортировки деревом. Алгоритмы реализованы на языке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
Метод организации массива в виде двоичного дерева требуетнесколько больших затрат как на организацию массива, так и на поиск в немнужного элемента, чем это минимально необходимо. Впрочем, это увеличение нестоль существенно. Этот метод оптимален по порядку роста трудоемкости поиска взависимости от размера массива. Это означает, что для данного метода, так жекак и для оптимального, эта зависимость имеет вид 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, так как в массиве нет элемента с меньшим значениемпризнака. После этого очередной элемент разыскивается в правой ветви, если онаесть, или возвращается по обратному указателю. После возвращения к какому-либоэлементу по левой или правой ветви дальнейшие действия идут так, как будто уэтого элемента соответствующей ветви нет.
2.2 Линейный поиск
Для неупорядоченного исходного массива единственнымспособом нахождения заданного элемента в этом массиве является линейный поиск.Этот метод состоит в последовательном сравнении каждого элемента массива сзаданным для поиска элементом. При линейном поиске иногда просматриваетсяполовина, а то и больше элементов исходного массива. Этот метод удобен и прост длямассивов с меньшей длиной. Для массивов большей длины это метод вызываетзатруднения, так как время поиска будет очень медленным.
Применим метод линейного поиска на примере поиска внеупорядоченном массиве 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не меняется;
— если образец меньше среднего элемента, то это значит,что искомый элемент расположен выше среднего элемента (между элементами сномерами verhe и sre-1), и за новое значение nize принимается sre-1, а значениеverhe не меняется.
2. После того как определена часть массива, в которойможет находиться искомый элемент, вычисляется новое значение sredе и поискпродолжается.
Применим метод двоичного поиска на примере поиска вупорядоченном массиве. X – искомый элемент, равный 11, а A – массив, состоящий из10 элементов:
1) 0 — verhe
5
7
11
12 — srede
24
32
68
87
92 – nize
srede равный 12>11 = X, следовательно искомый элементнаходится выше среднего элемента.
2) 0 — verhe
5
7 — srede
11– nize
Srede равный 7
3) 11=11
В итоге нужный элемент найден на третьем сравнении.Данный пример наглядно показывает всё удобство и легкость двоичного методапоиска. Результаты работы программы приведены в приложении Г.
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 nenaiden’).
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. Результаты линейного поискаКоличество элементов массива 16 128 512 1024 Позиция элемента Искомый элемент Количество сравнений Искомый элемент Количество сравнений Искомый элемент Количество сравнений Искомый элемент Количество сравнений Первая 5 1 1 48 1 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).
/>
Рисунок 1. График результатов линейного поиска
Вывод: Из рисунка 2 видно, что график линейного поискаимеет линейный характер. Теоретическое время незначительно отличается отпрактического, что означает правильность результатов выполнения линейногопоиска.
Данный метод удобен для массивов с малой длиной, ноиспользование его для больших массивов занимает много времени.
5.2 Двоичный поиск
Анализ двоичного поиска был проведен на примере числовогоодномерного массива длиной в 16, 128, 512, 1024 элементов. В качестве искомыхэлементов были взяты числа, расположенные в первой, средней, последней ипроизвольной позициях. Для двоичного поиска теоретическое время поискаопределяется по формуле Tтеор.=[время сравнения]× log2N
Результаты приведены в таблице, которая приведена ниже.
Таблица 3. Результаты двоичного поискаКоличество элементов массива 16 128 512 1024 Позиция элемента Искомый элемент Количество сравнений Искомый элемент Количество сравнений Искомый элемент Количество сравнений Искомый элемент Количество сравнений Первая 4 7 9 10 Средняя 13 1 310 1 156 1 491 1 Последняя 45 4 901 7 491 9 942 10 Произвольная 2 2 80 3 127 7 660 9 Элемент отсутствует 88 4 1001 7 1002 9 1003 10 Среднее количество сравнений 3 5 7 8 Теоретическое значение 4 7 9 10
Ниже приведен график зависимости времени поиска отколичества элементов массива.
/>
Рисунок 2. График результатов двоичного поиска
Вывод: Из рисунка 2 видно, что график двоичного поискаимеет логарифмический характер. Теоретическое время незначительно отличается отпрактического, что означает правильность результатов выполнения двоичногопоиска.
Данный метод удобен для массивов с большой длиной, но егоиспользование возможно только в упорядоченных массивах.
5.3 Анализ сортировки деревом
Анализ сортировки деревом был проведен на примере массивадлиной в 16, 128, 512, 1024 элементов.
Результаты представлены в виде нижеследующей таблицы.
Таблица 6. Результаты сортировкиКоличество элементов в массиве 16 128 512 1024 Количество перестановок 18 130 514 1026
Ниже приведен график сортировки деревом.
/>
Рисунок 3. График сортировки деревом.
Вывод: Организация массива в виде двоичного дереватребует несколько больших затрат как на организацию массива, так и на поиск внем нужного элемента, чем это минимально необходимо. Впрочем, это увеличение нестоль существенно. Этот метод оптимален по порядку роста трудоемкости поиска взависимости от размера массива.
Сортировка деревом не является минимальной по памяти, таккак на построения дерева необходимы большие затраты памяти, но процесссортировки с помощью данного метода занимает мало времени.
Заключение
В процессе выполнения данного курсового проекта изучены иразработаны алгоритмы нечисленной обработки данных: линейный и двоичный поискзаданного элемента, а также упорядочение массива методом сортировки дерева. Былпроведен анализ результатов программы, который подтвердил правильностьсоставления и отладки программы. Для наглядности результатов работы программыпостроены графики и составлены таблицы.
Список литературы
1. Лорин Г. Сортировка и системы сортировки. М.: Наука,1983г.
2. Лавров С.С, Гончаров Л.И. Автоматическая обработкаданных. Хранение информации в памяти ЭВМ. М.: Наука, 1971г.
3. Попов В.Б. Turbo Pascal. М.: Финансы и статистика,2007г.
Приложение А
Таблицы идентификаторов
Таблица А.1: Идентификаторы основной программыИмя параметра Физический смысл параметра Тип параметра n Длина исходного массива до 1024 элементов integer i Счетчик, индекс элемента массива integer j Счетчик, индекс элемента массива, указатель integer x Искомое число integer a Одномерный числовой массив (исходный массив) mas=array [1..1024] of integer b Двумерный числовой массив, дерево, образованное из исходного массива mas2=array [1..1024, 1..5] of integer b1 Двумерный числовой массив, сортируемое дерево mas2=array [1..1024, 1..5] of integer F Текстовый файл для хранения исходного массива text F_1 Текстовый файл для хранения отсортированного массива, сортируемого массива после каждой перестановки text
Таблица А.2: Идентификаторы процедуры VVodИмя параметра Физический смысл параметра Тип параметра i Счетчик, индекс элемента формируемого массива integer n Длина формируемого массива integer a Формируемый массив mas=array [1..1024] of integer
Таблица А.3: Идентификаторы процедуры VivodИмя параметра Физический смысл параметра Тип параметра i Счетчик, индекс элемента выводимого на экран массива integer n Длин массива, выводимого на экран integer a Выводимый на экран массив mas=array [1..1024] of integer
Таблица А.4: Идентификаторы процедуры Save_To_FileИмя параметра Физический смысл параметра Тип параметра i1 Счетчик, индекс элемента массива, сохраняемого в файл integer F Файл, в который необходимо записывать сортируемый массив после каждой перестановки text n Длина массива integer a Исходный массив, сохраняемый в файл mas=array [1..1024] of integer m Количество перестановок integer
А.5 Идентификаторы процедуры Lin_PoiskИмя параметра Физический смысл параметра Тип параметра i Счетчик, индекс элемента массива integer k Количество сравнений integer n Длина массива integer a Массив, в котором необходимо найти искомый элемент mas=array [1..1024] of integer x Искомый элемент integer
Таблица А.6 Идентификаторы процедуры Dv_PoiskИмя параметра Физический смысл параметра Тип параметра sri Индекс среднего элемента в массиве integer k Количество сравнений integer vi Индекс верхнего элемента в массиве integer ni Индекс нижнего элемента в массиве integer n Длина массива integer a Массив, в котором необходимо найти искомый элемент mas=array [1..1024] of integer x Искомый элемент integer f Флаг нахождения искомого элемента в массиве boolean
Таблица А.7: Идентификаторы процедуры TreeИмя параметра Физический смысл параметра Тип параметра i Счетчик, индекс элемента массива (строка) integer j Счетчик, индекс элемента массива (столбец) integer s Рабочая память, необходимая для хранения значения integer k Индекс элемента в массиве integer a Исходный массив, из которого следует построить дерево mas=array [1..1024] of integer n Длина массива integer b Дерево, полученное из массива A mas2=array [1..1024, 1..5] of integer
Таблица А.8: Идентификаторы процедуры TreeSortИмя параметра Физический смысл параметра Тип параметра k Число вершин дерева integer m Количество перестановок integer i1 Счетчик, индекс элемента массива integer b Дерево, полученное из массива mas2=array [1..1024, 1..5] of integer b1 Сортируемое дерево mas2=array [1..1024, 1..5] of integer a Отсортированный массив mas=array [1..1024] of integer
Приложение Б
Текст программы
Program Fariza_Kurs;
uses crt;
type
mas= array [1..1024] of integer;
mas2= array [1..1024, 1..5] of integer;
var n,i,j,x: integer;
a: mas;
b,b1: mas2;
f, f1: text;
Procedure Vvod(n: integer; Var a: mas);
var i: integer;
begin
if n
begin
writeln('Vvedite elementy massiva');
for i:=1 to n do read(A[i]);
end
else
for i:=1 to n do
A[i]:=random(1000);
writeln(f,'Ishodnii masssiv');
for i:=1 to n do write(f,a[i]:4);
end;
Procedure Vivod(n: integer; a: mas);
var i: integer;
begin
for i:=1 to n do write(a[i], ' ');
end;
{zapis v fail}
Procedure Save_To_File(var f:text; n: integer; a: mas;m:integer);
var i1: integer;
begin
if n
begin
writeln(f,m,'-yi shag:');
for i1:=1 to n do
write(f,A[i1]:4);
writeln(f);
end;
if (n>16) and (m mod 10=0) then
begin
writeln(f,m,'-yi shag:');
for i1:=1 to n do
write(f,A[i1]:4);
writeln(f);
end;
end;
{metod lineinogo poiska}
Procedure Lin_Poisk(n: integer; a: mas; x: integer);
var i,k: integer;
begin
writeln('Metod lineinogo poiska:');
k:=0;
for i:=1 to n do
if a[i]=x then begin k:=i; break;
end;
if k0 then Writeln('Element naiden. Sravnenii — ',k)
else writeln('Element ne naiden');
end;
{========metod dvoichnogo poiska ================}
procedure Dv_Poisk(n:integer;a:mas; x:integer);
var k,ni,vi, sri:integer;
f:boolean;
begin
writeln('Metod dvoichnogo poiska:');
vi:=N;
ni:=1;
k:=0;
f:=FALSE;
repeat
sri:=( (ni+vi) div 2);
k:=k+1;
if a[sri] = X then f:=TRUE
else if X > a[sri] then ni:=sri else vi:=sri;
until (k>trunc(ln(n)/ln(2))) or (f=true);
if f=true then writeln('Element naiden, Index= ', sri,'.Sravnenii ',k)
else writeln('Element ne naiden');
end;
{predstavlenie massiva A v vide dereva}
Procedure Tree(a:mas; n: integer; var b: mas2 );
label l;
var i,j,s,k: integer;
begin
b[1,3]:=0;
b[1,4]:=0;
b[1,5]:=0;
for i:=1 to n do begin
b[i,1]:=a[i];
b[i,2]:=a[i];
end;
for i:=2 to n do
begin
k:=1;
l: if b[i,1]
s:=b[k,j];
if s0 then begin
k:=s;
goto l;
end;
b[k,j]:=i;
b[i,3]:=0;
b[i,4]:=0;
b[i,5]:=k;
end;
end;
{sortirovka derevom}
procedure Tree_Sort(b: mas2; var b1: mas2; n: integer);
label l1,l2,l3;
var k,m,i1: integer;
begin m:=0;
for i:=1 to n do
for j:=1 to 5 do
b1[i,j]:=b[i,j];
i:=1;
k:=0;
l1:
if b[i,3]0 then
begin
i:= b[i,3];
goto ll;
end;
m:=m+1;
for i1:=1 to n do A[i1]:=b1[i1,1];
savetofile(f1,n,a,m);
l2:
k:=k+1;
b1[k,1]:=b[i,1];
b1[k,2]:=b[i,2];
if b[i,4]0 then
begin
i:=b[i,4];
goto ll;
end;
m:=m+1;
for i1:=1 to n do A[i1]:=b1[i1,1];
savetofile(f1,n,a,m);
l3:
j:=i;
i:=b[i,5];
if i0 then
begin
if b[i,1]> b[j,1] then goto lm else goto ln;
end;
m:=m+1;
for i1:=1 to n do A[i1]:=b1[i1,1];
savetofile(f1,n,a,m);
writeln('Otsortirovanii massiv');
Vivod(n,a);
readln;
writeln('Kolichestvo perestanovok=',m);
end;
BEGIN
writeln(' VVedite 4islo elementov massiva N
readln(n);
assign (f, 'd:\dan.txt');
rewrite(f);
Vvod(n,a);
close(f);
writeln('Ishodnii massiv:');
Vivod(n,a);
{====================lineinii poisk===============}
writeln;
writeln('Vvedite element dla poiska');
readln(x);
LinPoisk(n,a,x);
{========sortirovka============}
assign (f1, 'd:\res.txt');
rewrite(f1);
tree(a,n,b);
Treesort(b,b1,n);
writeln(f1, 'Otsortirovannyi massiv:');
for i:=1 to n do write(f1, A[i]:4);
close(f1);
{========dvoichnii poisk===========}
DvPoisk(n,a,x);
end.