Навигация
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 Область и условия применения программы
В данной программе были разработаны алгоритмы нечисленной обработки данных – линейный и двоичный поиск, сортировка деревом. Сортировку деревом очень удобно использовать, когда необходимо сэкономить максимально возможно количество времени, но для представления дерева требуются большие затраты дополнительной памяти.
Программа является познавательной, её целесообразно использовать в качестве обучающего примера.
Похожие работы
... процессов и явлений, использовать графику машины для повышения наглядности изучаемого материала. Использование пакетов прикладных учебных программ, готового программного обеспечения является одной из самых важных компонентов формирования компьютерной грамотности. При этом значительно расширяются межпредметные связи между многими учебными дисциплинами, особенно между математикой и информатикой. ...
... практичных алгоритмов оптимизированного перебора, позволяющих за разумное время осуществлять распараллеливание достаточно больших участков. Анализ работ, посвященных оптимизации кода для процессоров с параллелизмом на уровне команд показывает, что для достижения наилучших результатов необходимо применение комплекса оптимизаций, среди которых можно выделить следующие классы. Преобразования циклов ...
... і слова в орфографічному словнику контроль орфографічної правильності його написання слід здійснювати за правилами орфографії. Зараз готують до затвердження наступний п’ятий правопис. Тому в процесі редагування треба враховувати динамічність правопису і слідкувати за правописними змінами. Відхилення від правильного написання допустиме лише тоді, коли в повідомленні йдеться про юридичну справу і ...
... дисциплин. Горн рассматривает эти вопросы, отталкиваясь в своих рассуждениях от профессиональных интересов ученых в этой области еще на, стадии получения ими образования: «Информационно-компьютерная наука рассматривает прагматические аспекты использования символов их пользователями и интерпретаторами в качестве еще одного центрального вопроса таким же образом, как эти аспекты должны исследоваться ...
0 комментариев