Метод двоичного поиска

Результатом работы алгоритма является индекс Pos, показывающий на место в упорядоченном массивеАс номерами элементов отFirst до Last, где располагается искомое значениеVal. Также в качестве результата формируется логическая переменнаяResultOk, которая принимает значениеTRUE, если искомый элемент содержится в массивеА, иFALSE– в противном случае.

Перед поиском исходный массив должен быть отсортирован любым методом.

Алгоритм двоичного поиска:

Шаг 1. Полагается ResultOk=false;First=0;Last=N-1 (N-размер массива).

Шаг 2. Пока справедливо условие First<Last, выполняетсяШаг 3.

Шаг 3. Вычисляется середина массива Middle=(Last+First)/2. ЕслиVal=А[Middle], то полагаетсяFirst=Middle;Last=First;ResultOk=true(т.е. элемент найден);Pos=Middle, в противном случае проверяется условиеVal>А[Middle]. Если это условие справедливо, то полагается First=Middle+1, в противном случае полагаетсяLast=Middle-1. После чего управление передается наШаг 1.

Шаг 4. Если ResultOk=true, то выводится сообщение об успешном поиске и выводится индекс элементаPos. В противном случае выдается сообщение что элемент не найден.

Конец алгоритма.

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

Рисунок 2 – Блок-схема алгоритма бинарного поиска

Задание.

Написать программу поиска элемента массива двумя методами: на основе линейного просмотра, двоичного поиска.

Предусмотреть время выполнения каждого метода в программе.

Защитить программу.

Технология выполнения работы

Разрабатываемый программный комплекс должен обеспечивать:

• выбор алгоритма поиска (с помощью RadioGroup);

• формирования одномерного массива, состоящего из 5000 элементов, с помощью генератора псевдослучайных чисел random();

• вывод исходного массива в объект ListBox;

• поиск элемента массива;

• вывод сообщения о результате поиска (найден или нет) и, в случае если элемент найден, вывод индекса этого элемента.

• замеры времени выполнения поиска элемента в массиве с помощью функции Time().

Описание и блок-схемы алгоритмов поиска приведены выше. Студенту требуется реализовать алгоритмы поиска в виде программного кода по приведенным выше блок-схемам, там же приведены примеры использования генератора случайных чисел, функции измерения времени выполнения алгоритма, а также пример заполнения списка ListBox.

Демонстрация работоспособности разработанных программных средств должна обеспечивать два варианта контроля: контроль работоспособности каждого из методов и контроль временных характеристик всех реализованных методов.

Рекомендуется следующая компоновка формы (рис. 3).

Рисунок 3 – Форма для поиска элемента массива

Вопросы для защиты работы

1. Опишите принцип работы алгоритма линейного поиска.

2. Опишите принцип работы алгоритма бинарного поиска.

3. Какое требование предъявляется к массиву при реализации бинарного поиска?

4. Скорость работы алгоритмов линейного и бинарного поиска.

Лабораторная работа № 16 Вычисления в Mathcad. Построение графиков функций

Время выполнения – 2 часа.

Цель работы

Научиться выполнять вычисления по формулам в Mathcad, научиться строить графики функций одной переменной.

Задачи лабораторной работы

После выполнения работы студент должен знать и уметь:

• знать основные приемы работы в Mathcad;

• уметь производить вычисления с использованием математических формул;

• уметь строить графики функций одной переменной.

Перечень обеспечивающих средств

Для обеспечения выполнения работы необходимо иметь компьютер с операционной системой MSWindows, установленное приложение РТСMathcadверсии 14 или выше; методические указания по выполнению работы.

Общие теоретические сведения

Программа Mathcadявляется математическим редактором, позволяющим проводить разнообразные научные и инженерные расчеты.

Она имеет ту же структуру, что и большинство программ Windows. Сверху вниз располагается заголовок окна, строка меню, панели инструментов и рабочая область документа (рис. 1).

Рисунок 1 – Пользовательский интерфейс Mathcad14

Для того чтобы выполнить простые расчеты по формуле, необходимо проделать следующее:

1. определить место в документе, где должно появиться выражение, щелкнув мышью в соответствующей точке документа;

2. ввести левую часть выражения;

3. ввести знак равенства < = >.

Пример:

Для проведения расчетов потребуется инструмент Калькулятор(рис. 2).

Рисунок 2 – Панель инструмента Калькулятор

Для отображения Калькуляторанужно нажать кнопку с изображением калькулятора на панелиMath(рис. 3).

Рисунок 3 – Панель инструментов Math

При расчетах по формулам целесообразно использовать переменные. Для задания значений переменных используется оператор присваивания: знаки двоеточия и равно (:=)

Пример:

a := 5.6 b := 1.8

a + b = 7.4 a – b = 3.8

a·b= 10.08

Для задания математических функций можно использовать инструмент Калькулятор; можно непосредственно набирать названия функций, используя клавиатуру, а можно воспользоваться менюinsert / functionи вставить необходимую функцию.

Для построения графиков функций необходимо использовать панель Graph(рис. 4).

Рисунок 4 – Панель инструментов Graph

Для того чтобы панель Graphоткрылась, необходимо щелкнуть мышкой по иконке с изображением графика на панелиMath.

Графики функций можно строить следующими двумя способами:

1. С использованием автовыбора значений интервала построения и шага. В данном случае в качестве аргумента функции необходимо задать переменную, которая ранее не использовалась (рис. 5).

Рисунок 5 – Построение графика функции

2. Задать в явном виде интервал, на котором будет построен график функции и «шаг», то есть промежуток через который будут вычисляться значения функции.

Задаем значения аргумента r, которые меняются от -2π до 2π с шагом 0.025

r:= -2·π, -2·π+ 0.025 .. 2·π

Строим графики функций (рис. 6):

Рисунок 6 – Построение графика функции

Замечание: часть формулы (0.025 .. 2π) необходимо набирать с использованием инструмента Range Variable (m .. n), расположенного на панелиМatrix(рис. 7):

Рисунок 7 – Панель инструментов Matrix

Оформление текста и комментариев в Mathcad

Текстовую область можно разместить в любом незанятом месте документа Mathcad. Чтобы до начала ввода указать программе, что требуется создать не формульный, а текстовый регион, достаточно, перед тем как ввести первый символ, нажать клавишу " (двойная кавычка). В результате на месте курсора ввода появится новый текстовый регион, который имеет характерное выделение:

Курсор принимает при этом вид вертикальной линии красного цвета, которая называется линией ввода текста.