Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
voprosy_NEW.docx
Скачиваний:
5
Добавлен:
01.07.2025
Размер:
1 Мб
Скачать
☆

31. Сравнительный анализ методов поиска

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

Алгоритм носит название двоичного (бинарного) поиска, т.к. на каждом шаге область поиска уменьшается вдвое.

Пусть в отсортированном массиве требуется найти элемент со значением x, или указать, что такого элемента там нет. Выберем средний элемент. Для этого элемента относительно значения x возможны три случая:

1. элемент равен x (поиск завершен);

2. элемент больше x (поиск необходимо продолжить в левой части массива);

3. элемент меньше x (поиск необходимо продолжить в правой части массива).

В случаях 2-3 поиск (если это ещё возможно) продолжается. Для этого в выделенной части массива вновь выбирается средний элемент и проводятся аналогичные рассуждения. И т.д., до тех пор, пока поиск не будет завершен.

Поиск завершается в одном из двух случаев:

1. элемент найден;

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

Рассмотрим программную реализацию алгоритма.

function find(a: mas; n: byte; x: integer): byte;

var L, R, c: byte;

Begin L := 1; R := n; {изначально область поиска - весь массив}

repeat

c := (L + R) div 2; {индекс среднего элемента}

if a[c] > x then R := c - 1; {случай 2}

if a[c] < x then L := c + 1; {случай 3}

until (a[c]=x) or (L > R);

if a[c]=x then find:=c else find := 0; {возвращем индекс элемента или нуль, если элемент не найден}

end;

32. Разработка приложений, поддерживающих графический интерфейс

При работе с GUI пользователь имеет произвольный доступ (с помощью клавиатуры) ко всем видимым экранным объектам. Графический интерфейс пользователя - разновидность пользовательского интерфейса, в котором элементы интерфейса , представленные пользователю на дисплее, исполнены в виде графических изображений. В отличие от интерфейса командной строки, в ГИ пользователь имеет произвольный доступ (с помощью устройств ввода — клавиатуры, мыши, джойстика и т. п.) ко всем видимым экранным объектам (элементам интерфейса) и осуществляет непосредственное манипулирование ими. Чаще всего элементы интерфейса в ГИ реализованы на основе метафор и отображают их назначение и свойства, что облегчает понимание и освоение программ неподготовленными пользователями. Основная черта любой программы с графическим интерфейсом - интерактивность. Программа не просто что-то считает (в пакетном режиме) от начала своего запуска до конца: ее действия зависят от вмешательства пользователя. Фактически, графическое приложение выполняет бесконечный цикл обработки событий. Программа, реализующая графический интерфейс, событийно-ориентирована. Она ждет от интерфейса событий, которые и обрабатывает сообразно своему внутреннему состоянию. Эти события возникают в элементах графического интерфейса и обрабатываются прикрепленными к ним обработчиками.

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]