Основы алгоритмизации и программирования. Часть вторая. Типовые алгоритмы обработки массивов. Асламова В.С - 18 стр.

UptoLike

ВУЗ: 

АГТА | Ангарск

Составители: 

Рубрика: 

35
Бинарный поиск
Поиск можно выполнять значительно эффективнее, если данные
будут упорядочены, то есть значения элементов последовательности
возрастают (убывают) с увеличением номера элемента. Будем
рассматривать упорядоченный по возрастанию массив, для которого
выполняются условия: X[ i –1]≤X[ i ] для всех i из интервала [1, n].
Основная идея – выбрать случайно некоторый элемент,
предположим X[k] и сравнить его с по
исковой переменной P. Если
X[ k ]=P, то поиск заканчивается. Если X[ k ]<P, то мы можем исключить
из дальнейшего поиска все элементы с индексами меньшими или равными
k. При X[ k ]>P исключаются все элементы с индексами большие или
равные k. Наша задача – исключить на каждом шаг
е как можно больше
элементов. Оптимальным решением будет выбор в качестве X[ k ]
среднего элемента, так как при этом в любом случае будет исключаться
половина массива. Тогда максимальное число сравнений с поисковой
переменной P равно log
2
n, округленному до ближайшего целого числа.
Обратимся к листу опорного сигнала №2 (Рисунок 17.). Как найти
нужную книгу на полке среди расставленных по порядку томов Ф.М.
Достоевского? Если мы знаем, что всего томов 40, то сразу выберем
средний (20-ый том) и посмотрим, этот ли нам нужен. Если нет, то
проверим, справа или слева нахо
дится интересующий нас 15-тый том.
Поскольку он должен находиться между 1-ым и 20-тым томами, выбираем
средний 10-тый том и снова делаем проверку, 15-тый том находится
правее. Делим промежуток межу 10-тым и 20-тым томами пополам и
сразу находим нужный 15-тый том. Запоминаем место, где он стоит.
В процессе поиска мы сдвигаем гр
аницы интервала, в котором
ищется нужная книга. Причем, после нового сравнения изменяем лишь
одну границу либо нижнюю, либо верхнюю.
Метод, использующий последовательное уменьшение исследуемых
данных в два раза, называется бинарным или методом дихотомии (деление
пополам). Разработаем блок-схему метода дихотомии для упорядоченного
по возрастанию массива данных. Обозначим A=1 (индекс наименьшего
элемента),
B=n (индекс наибольшего элемента), n – количество элементов.
Основой алгоритма будет итерационный цикл, который выполняется до
тех пор, пока границы A и B не совпадут. В теле цикла выбираем средний
индекс C, разделив интервал индексов пополам. Так как индекс C должен
быть целым числом, нужно воспользоваться функцией
div – деление
нацело двух чисел, то есть будем вычислять C по формуле: C:=(A+B)
div2.
36
Далее сравниваем элемент под номером
C с поисковой переменной P и в зависимости
от результата сравнения заново вычисляем
границы A или B. Проверку на совпадение
X(C)=P для повышения эффективности
алгоритма будем выполнять после выхода из
цикла. По условию цикл прекращает свою
работу при A=B. Как достичь этог
о? Пусть мы
несколько раз сделали пересчет A и В и дошли
до соотношения между ними А+1=В. Это
означает, что при очередном сравнении мы
будем искать нужный элемент среди двух,
расположенных рядом Х(А) и Х(В). Пусть А=7,
В=8 и Х(8)=Р. тогда C=(7+8)
div 2=7, то есть
С=А и будет выполняться соотношение
Х(С)<Р. поэтому нужно сделать так, чтобы А
стало равным В, то есть при выполнении
условия Х(С)<Р следует полагать А=С+1. Если
выполняется условие Х(С)>Р, то искомым
элементом, возможно, является Х(А), тогда для
завершения работы цикла следует полагать
В=С.
Легко убедиться, чт
о такие
присваивания не противоречат выбранному
алгоритму на любом шаге работы цикла.
После выхода из цикла необходимо проверить
условие Х(А)=Р, если оно выполняется, то
индекс искомого элемента k=А, в противном
случае будем полагать k=0 (элемент не
найден).
На Рисунке 21 приведена блок-схема
рассмот
ренного алгоритма.
Программа 13. Процедура для массива
символьного типа
Const n=40;
Type mass=array[1 . . n] of char;
Procedure BiPoisk(X:mass; P:char; n: integer; var
k:integer);
Рисунок 21. Блок-схема
бинарного поиска
НАЧАЛО
Ввод n, P,
X(n)
A:= 1;
B:= n;
A:=C+1;
КОНЕЦ
Печать k
X(C)=P
A < B
B:=C;
нет
да
нет
да
C:=(A+B)di v2
k:= A;
X(A )=P
k:= 0;
нет
да 
Бинарный поиск                                                                   НАЧАЛО
                                                                                                             Далее сравниваем элемент под номером
                                                                                                       C с поисковой переменной P и в зависимости
      Поиск можно выполнять значительно эффективнее, если данные
                                                                                Ввод n, P,             от результата сравнения заново вычисляем
будут упорядочены, то есть значения элементов последовательности
                                                                                  X(n)                 границы A или B. Проверку на совпадение
возрастают (убывают) с увеличением номера элемента. Будем
                                                                                                       X(C)=P для повышения эффективности
рассматривать упорядоченный по возрастанию массив, для которого
                                                                                  A:= 1;               алгоритма будем выполнять после выхода из
выполняются условия: X[ i –1]≤X[ i ] для всех i из интервала [1, n].                                   цикла. По условию цикл прекращает свою
                                                                                  B:= n;
       Основная идея – выбрать случайно некоторый элемент,                                             работу при A=B. Как достичь этого? Пусть мы
предположим X[k] и сравнить его с поисковой переменной P. Если                                   нет   несколько раз сделали пересчет A и В и дошли
X[ k ]=P, то поиск заканчивается. Если X[ k ]P исключаются все элементы с индексами большие или                                       будем искать нужный элемент среди двух,
равные k. Наша задача – исключить на каждом шаге как можно больше              C:=(A+B)div2            расположенных рядом Х(А) и Х(В). Пусть А=7,
элементов. Оптимальным решением будет выбор в качестве X[ k ]                                          В=8 и Х(8)=Р. тогда C=(7+8)div 2=7, то есть
среднего элемента, так как при этом в любом случае будет исключаться                                   С=А и будет выполняться соотношение
                                                                                                нет    Х(С)<Р. поэтому нужно сделать так, чтобы А
половина массива. Тогда максимальное число сравнений с поисковой                  X(C)=P
переменной P равно log2n, округленному до ближайшего целого числа.                                     стало равным В, то есть при выполнении
                                                                                        да             условия Х(С)<Р следует полагать А=С+1. Если
       Обратимся к листу опорного сигнала №2 (Рисунок 17.). Как найти                                  выполняется условие Х(С)>Р, то искомым
нужную книгу на полке среди расставленных по порядку томов Ф.М.                  A:=C+1;
                                                                                                       элементом, возможно, является Х(А), тогда для
Достоевского? Если мы знаем, что всего томов 40, то сразу выберем                                      завершения работы цикла следует полагать
средний (20-ый том) и посмотрим, этот ли нам нужен. Если нет, то                                       В=С.
проверим, справа или слева находится интересующий нас 15-тый том.                  B:=C;
Поскольку он должен находиться между 1-ым и 20-тым томами, выбираем                                          Легко     убедиться,    что    такие
средний 10-тый том и снова делаем проверку, 15-тый том находится                                       присваивания не противоречат выбранному
правее. Делим промежуток межу 10-тым и 20-тым томами пополам и                                         алгоритму на любом шаге работы цикла.
сразу находим нужный 15-тый том. Запоминаем место, где он стоит.                                нет    После выхода из цикла необходимо проверить
                                                                                  X(A )=P
                                                                                                       условие Х(А)=Р, если оно выполняется, то
      В процессе поиска мы сдвигаем границы интервала, в котором                           да          индекс искомого элемента k=А, в противном
ищется нужная книга. Причем, после нового сравнения изменяем лишь                                      случае будем полагать k=0 (элемент не
одну границу либо нижнюю, либо верхнюю.                                            k:= A;              найден).
      Метод, использующий последовательное уменьшение исследуемых                                            На Рисунке 21 приведена блок-схема
данных в два раза, называется бинарным или методом дихотомии (деление                                  рассмотренного алгоритма.
пополам). Разработаем блок-схему метода дихотомии для упорядоченного               k:= 0;
по возрастанию массива данных. Обозначим A=1 (индекс наименьшего                                       Программа 13. Процедура           для   массива
элемента), B=n (индекс наибольшего элемента), n – количество элементов.                                символьного типа
Основой алгоритма будет итерационный цикл, который выполняется до                 Печать k             Const n=40;
тех пор, пока границы A и B не совпадут. В теле цикла выбираем средний                                 Type mass=array[1 . . n] of char;
индекс C, разделив интервал индексов пополам. Так как индекс C должен             КОНЕЦ                Procedure BiPoisk(X:mass; P:char; n: integer; var
быть целым числом, нужно воспользоваться функцией div – деление                                        k:integer);
нацело двух чисел, то есть будем вычислять C по формуле: C:=(A+B)div2.
                                                                          Рисунок 21. Блок-схема
                                                                          бинарного поиска

                                                                    35    36

Страницы