Технология выполнения работы
Разрабатываемый программный комплекс должен обеспечивать:
выбор алгоритма сортировки (с помощью RadioGroup);
формирования одномерного массива, состоящего из 5000 элементов, с помощью генератора псевдослучайных чисел random();
вывод исходного массива в объект ListBox;
сортировку массива);
вывод результата (отсортированного массива) в ListBox;
замеры времени выполнения сортировок массива с помощью функции Time().
Студенту требуется реализовать алгоритмы сортировки в виде программного кода по приведенным выше блок-схемам. Кроме того, выше приведены примеры использования генератора случайных чисел, функции измерения времени выполнения алгоритма, а также пример заполнения списка ListBox.
Демонстрация работоспособности разработанных программных средств должна обеспечивать два варианта контроля: контроль работоспособности каждого из методов и контроль временных характеристик всех реализованных методов.
Рекомендуется следующая компоновка формы (рис. 4).
Рисунок 4 – Форма для сортировки массива
Вопросы для защиты работы
Назовите основные свойства управляющего элемента ListBox.
Заполнение списка ListBox.
Использование генератора случайных чисел.
Принцип измерения времени работы алгоритмов.
Какие методы сортировки одномерных массивов вы знаете? Какой из перечисленных вами методов наиболее быстрый?
Лабораторная работа № 15 Программирование в среде разработки Borland C++ Builder. Поиск элемента в массиве
Время выполнения – 6 часов.
Цель работы
Изучить алгоритмы поиска элемента в массиве и научиться использовать их при обработке данных.
Задачи лабораторной работы
После выполнения работы студент должен уметь применять алгоритмы поиска элемента в массиве при обработке данных.
Перечень обеспечивающих средств
Для обеспечения выполнения работы необходимо иметь компьютер со следующим программным обеспечением: операционная система семейства Windowsи среда разработки программBorland С++Builderv.6.0.
Общие теоретические сведения
Выполнение лабораторной работы направлено на освоение основных приемов использования массивов и методов доступа к элементам массивов. В качестве практической проблемы, требующей решения, рассматривается задача поиска элементов в массиве. При решении этой задачи требуется в исходном массиве, содержащем произвольные целые числа, найти элемент, содержащий искомое значение, и указать индекс этого элемента.
В данной лабораторной работе необходимо изучить следующие алгоритмы поиска и создать программу, реализующую:
метод поиска на основе линейного просмотра;
метод бинарного поиска.
Поиск элемента массива на основе линейного просмотра
Результатом работы алгоритма линейного поиска значения Valв массивеAявляются индексPosи логическая переменнаяResultOk, которая принимает значениеTRUE, если такой элемент содержится в массивеА, иFALSE– в противном случае. ИндексPosпринимает значение, равное номеру искомого элемента, если такой найден, и значение, равное -1 – в противном случае.
Алгоритм линейного поиска:
Шаг 1. Полагается Pos=-1 иResultOk=FALSE, и значение переменной циклаJ:=0.
Шаг 2. Если A[J]=Val, то переменнымPosиResultOkприсваиваются соответственно значенияPos=J,ResultOk=TRUEи алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицуJ=J+1.
Шаг 3. Если J<Las (гдеLast– число элементов массива А), то выполняетсяШаг 2, в противном случае – работа алгоритма завершена.
Конец алгоритма.
Схема алгоритма на основе линейного просмотра представлена на рис. 1.
Рисунок 1 – Блок-схема алгоритма линейного поиска