Главная » Basic » ПОИСК

0

Поиском заданного значения в  массиве  приходится  заниматься очень  часто.  При этом  задается аргумент поиска и требуется определить положение в массиве  такого элемента, у которого значение ключа совпадает с аргументом. Если порядок расположения данных в  массиве неизвестен,  то нет более эффективного метода, чем описанный ранее простой последовательный поиск, при котором ключ каждого элемента данных сравнивается с аргументом поиска некоторым регулярным образом. При этом для поиска  в массиве  из N значений в среднем приходится выполнить N/2 сравнений. Предложить методы более быстрого поиска можно только в том случае, если данные определенным образом упорядочены. Например, тот факт, что в  телефонном справочнике  записи упорядочены по алфавиту, позволяет нам очень быстро находить нужную фамилию и номер телефона.

Универсальным методом быстрого поиска   в упорядоченном множестве данных является бинарный поиск, при котором число сравнений, выполняемых  для поиска   в массиве  из N значений, в среднем

пропорционально log2N. Сравним это число со средним числом сравнений в простом методе последо-

вательного поиска, которое пропорционально N:

N

10

100

1000

log2N

3.3

6.6

9.9

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

Метод бинарного поиска заключается в последовательном делении множества  данных на две равные части — отсюда и название "бинарный"  (двоичный) . Первоначально областью поиска считается все множество;  из него извлекается средний элемент, ключ которого сравнивается с аргументом поиска. Если они совпали, то поиск на этом успешно завершается, но если  они не совпадают, то аргумент поиска может быть больше или меньше ключа среднего элемента. Тогда в зависимости   от способа упорядочения данных в качестве области поиска выбирается первая или вторая половина множества,  из  нее извлекается средний элемент и  его ключ сравнивается с аргументом поиска. Этот процесс продолжается до тех пор, пока не приведет либо к /спеху, либо к неудаче. Такое последовательное деление множества работает на удивление хорошо. На рис. 4.3 показан первый шаг поиска  в массиве 134

Рис. 4.3. Массив сортируется в  алфавитном порядке. Изображен первый цикл двоичного поиска с ключом S$

строк  символов,  упорядоченных  по  алфавиту  по  нескольким первым символам каждой  строки

(являющихся ключом).

Приведенная ниже форма алгоритма  бинарного поиска следует форме, предложенной П. Науром, согласно  которой  вводятся   фиктивные  нижняя и   верхняя границы значений индексов  массива, равные -1  и   N+1,  в  то  время как  фактически  индексы пробегают значения от  0  до  N.  В  этом алгоритме первые М символов каждой строки рассматриваются как ключ и строки упорядочиваются в  алфавитном порядке по этим ключам. Строки могут содержать фамилии,  за которыми следуют адреса или  какая-либо другая информация;  таким образом, процедура поиска может быть частью справочной системы. Структограмма алгоритма такова:

Входными данными для приведенного ниже фрагмента программы служат массив А$(0), .. . , A$(N),

значение N,  значение М,  определяющее  число символов    в  ключе,  а  также  аргумент  поиска в переменной S$. На выходе из  фрагмента в  Q находится индекс найденного элемента массива   или N+1, если элемента с заданным значением ключа нет.

1000 REM БИНАРНЫЙ

1010 REM ПРЕДПОЛАГАЕТСЯ, ЧТО МАССИВ A$(0), …, A$(N)

1020 REM СОДЕРЖИТ ЗНАЧЕНИЯ. ОТСОРТИРОВАННЫЕ ПО ПЕРВЫМ М

1030 REM СИМВОЛАМ В АЛФАВИТНОМ ПОРЯДКЕ

1040 REM В Q ВОЗВРАЩАЕТСЯ ЛИБО ИНДЕКС НАЙДЕННОГО ЗНАЧЕНИЯ

1050 REM ЛИБО N+1

1060 В2=-1

1070 T2=N+1

1080 E=0

1090 IF T2-B2=l THEN 1220

1100  С=INT(B2+T2)/2)

1110   K$=LEFT$(A$(C),M)

1120   IF S$=K$ THEN 1160

1130     IF S$<K$ THEN 1160

1140       B2=C

1150             GOTO 1250

1160                  T2=C

1170             GOTO 1250

1180        PRINT "ЗНАЧЕНИЕ НАЙДЕНО"

1190        Q=C

1200        E=1

1210        GOTO 1250

1220   PRINT "ЗНАЧЕНИЕ НЕ НАЙДЕНО"

1230   Q=T2

1240   E=1

1250   IF E=0 THEN 1090

1260   REM ВЫХОД

Переменная Е вводится  для учета различных условий  выхода из  цикла. Произвольные  передачи управления за  пределы  такого  цикла не  могут  быть  представлены символами  структограммы, поэтому применение структограмм способствует развитию хорошего стиля программирования. Этот фрагмент можно проверить,  добавив к нему операторы

10 REM ТЕСТ ПРОГРАММЫ ДВОИЧНОГО А

20 DIM A$(2B)

30 N=15

40 М=1

50 INPUT "ВВЕДИТЕ ИСКОМОЕ ЗНАЧЕНИЕ";S$

60 FOR I=0 ТО N

70   READ A$(I)

80 NEXT I

90 DATA ABBA, BRIAN, COLIN, FRED

100 DATA GERRY, HUGH, JIM, LEN

110 DATA MIKE, NICK, OLIVER, PETER

120 DATA RUPERT, STAN, TIM, WILLIAM

1300      PRINT Q, A$(Q)

1310   END

Запуски этой  программы  для  поиска по  очереди всех имен из  содержащегося в   ней  списка к регистрация чисел сравнений показывают,  что в среднем на каждый успешный поиск приходится 3,4 сравнения (log2 16 равен 4); сами числа распределены между 5  (наихудший случай) и 1 (наилучший случай).

УПРАЖНЕНИЯ

4.1.       Напишите  программу для чтения десяти чисел из  списка данных оператора DATA и  печати наибольшего и наименьшего из этих чисел.

4.2.     Напишите программу для регистрации и изображения экзаменационных  оценок одного класса. Фамилии учеников  хранятся в  нескольких операторах DATA в  программе. Во время  исполнения программа  по  очереди выводит  каждую  фамилию  и   запрашивает   ввод  оценки с  терминала. В заключение изображаются средняя оценка и список фамилий с указанием оценок.

4.3.       Напишите  программу для ведения  журнала посещаемости класса. Данные  представляются в виде   списка единиц    и  нулей:  единица  означает, что  ученик присутствовал  в  классе, а  нуль  — отсутствовал.  Для класса из восьми  учеников   запись одного дня в  журнале  посещаемости  может иметь  вид

1, 1,0, 1, 1, 1,0,0 Эти данные можно поместить в оператор DATA или ввести с терминала.

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

4.4.  Разработайте программу для выполнения следующих действий со строками символов :

(а)  Присвоить двум строковым  переменным соответственно  Ваши имя и фамилию, объединить эти строки  в одну и распечатать результат.

(б) Выделить  из строковых  переменных инициалы  и напечатать их.

(в)    Присвоить одной строковой переменной форму обращения к Вам  (Г-Н, Г-ЖА и пр.), а другой -

Ваш адрес и распечатать Ваши фамилию и адрес в обычной форме.

4.5.     Группа из шести  рабочих  занята на строительной площадке. В течение каждой недели двое из них отвечают за организацию  чаепития.  Разработайте и  напишите  программу для  печати  такого списка пар  имен, составляющего полный  график дежурств, в   котором  каждый  из  работников  отвечает за чаепитие   в течение пяти недель. Попробуйте использовать  оператор DATA и  массив  строк символов для работы с фамилиями.

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

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

4.7.    Разработайте и напишите программу анализа текста. Она должна воспринимать фрагмент текста как предложение и вычислять частоту появления  входящих  в него слов. Таким образом, как только при обработке текста встречается новое слово, оно должно запоминаться в  таблице  со значением частоты появления,  равной 1; если обнаруженное слово не является новым, то  определяется его положение в таблице и соответствующее ему значение частоты появления увеличивается на 1. Отсортируйте результаты и изобразите  слова  в порядке алфавита с указанием частоты их появления.

4.8.     Напишите программу  для  выдачи справок. Соответствующие  сведения можно  хранить   в операторах DATA,  предваряя каждую  справку  "ключевым словом". При исполнении  программа должна запросить ввод ключевого  слова, найти его положение и распечатать соответствующую ему справку.

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

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

Источник: Уолш Б.    Программирование на Бейсике: Пер. с англ. М.: Радио и связь, 1988. 336 с: ил.

По теме:

  • Комментарии