Под упорядоченными в дальнейшем будут пониматься неубывающие массивы, если не оговорено иное. То есть, a[1] <= a[2] <= … <= a[N].
Сначала приведем пример реализации широко известного алгоритма двоичного (бинарного) поиска элемента, равного K, в уже упорядоченном массиве. Оказывается, досрочный выход из цикла в случае нахождения элемента выигрыша по скорости практически не дает, а лишние проверки делают программу более громоздкой. Поэтому рекомендуется производить поиск, пока диапазон рассматриваемых элементов состоит более, чем из одного элемента.
L:=1; R:=N+1;
while L
begin
m:=(L+R)div 2;
if a[m]
else R:=m
end;
if a[m]=K then write(m) else write(0)
На полуфинале чемпионата мира по программированию среди студенческих команд вузов, проходившем в г.Санкт-Петербург в 2000 году предлагалась следующая обратная двоичному поиску задача (см. сайт neerc.ifmo.ru на котором можно найти тесты и ответы к ним для указанной задачи). Известно, что алгоритм бинарного поиска, аналогичный приведенному выше, но заканчивающий свою работу в случае досрочного обнаружения элемента, за Q сравнений определил, что искомым является элемент с номером I. Какова могла быть при этом размерность массива (указать все допустимые диапазоны значений N). Несмотря на кажущуюся сложность, при заданных в условии ограничениях задача решалась путем простого перебора различных значений N и обращения с каждым из этих значений к функции бинарного поиска. Конструктивный же подход к решению задачи намного сложнее. Однако и в случае подбора можно использовать немало интересных фактов. Например, длина каждого из диапазонов возможных значений N, является степенью двойки, а каждый следующий диапазон не меньше предыдущего. Это позволяет значительно сократить количество рассматриваемых значений N. Кроме того, максимальное допустимое значение для N легко найти аналитически.
Рассмотрим теперь задачу поиска в упорядоченном массиве наибольшего "равнинного" участка. То есть, требуется найти такое число p, что в массиве имеется последовательность из p равных элементов и нет последовательности из p + 1 равных по значению элементов. Оказывается, существует алгоритм решения этой задачи, количество операций в котором может оказаться существенно меньше, чем N. Так, если мы уже нашли последовательность из p1 равных между собой чисел, то другую последовательность имеет смысл теперь рассматривать только если ее длина не менее p1 + 1. Поэтому, если a[i] — первый элемент предполагаемой новой подпоследовательности, то сравнивать его надо сразу с элементом a[i+p], где p — максимальная величина для уже рассмотренных подпоследовательностей из равных элементов. Приведем фрагмент программы, решающий данную задачу. В качестве результата мы получаем длину максимальной подпоследовательности p, номер элемента, с которого эта подпоследовательность начинается, k и значение элементов в найденной подпоследовательности:
p:=1; k:=1;
i:=1; f:=false;
while i+p<=N do
if a[i+p]=a[i] then
begin
p:=p+1; f:=true
end
else if f then
begin
k:=i; i:=i+p; f:=false
end
else i:=i+1;
writeln(p,’ ’,k, ’ ’,a[k])
В [7] можно найти еще одну интересную задачу под названием “жулик на пособии” поиска в упорядоченных последовательностях уже практически какой угодно длины. Пусть имеются три упорядоченных по алфавиту списка из фамилий людей, получающий пособие по безработице в трех различных местах. Длина каждого из списков может быть как угодно большой (каждый из списков можно хранить в отдельном файле). Известно, что по крайней мере одно лицо фигурирует во всех трех списках. Требуется написать программу поиска такого лица, порядок количества операций в которой не будет больше, чем сумма длин всех трех списков. Приведем фрагмент программы, работающий с тремя файлами, обращение к элементам которых (они могут быть любого типа, в том числе и string, к элементам которого в Паскале применимы операции сравнения, чтения и записи) из программы происходит с помощью файловых переменных x, y, z типа text:
readln(x,p); readln(y,q); readln(z,r);
while not((p=q)and(q=r)) do
begin
if p
else if q
else if r
end;
writeln(p);{p=q=r}
Покажите, что для поставленной задачи чтение из файла всегда будет производиться корректно и на каждом шаге цикла значение одной из трех переменных p, q, r будет изменено. Кроме того докажите, что с помощью этой программы всегда будет найден именно минимальный из элементов, присутствующих во всех трех файлах.
Наконец, рассмотрим задачу поиска элемента, значение которого равно K, в двухмерном массиве, упорядоченном по строкам и столбцам: a[i,j] <=a [i,j+1], a[i,j] <= a[i+1,j], 1 <= i < N, 1 <= j < M. Данная задача решается за M + N действий, а не за M*N, как в произвольном массиве. Поиск следует начинать с элемента a[N,1]. Этот элемент самый маленький в своей строке и самый большой в своем столбце (в математике подобные элементы называют “седловыми точками”). Поэтому, если он окажется меньше, чем K, то из рассмотрения первый столбец можно исключить, а если больше — из рассмотрения исключается последняя строка и т. д. Вот возможная реализация этого алгоритма:
i:=N; j:=1;
while (i>0)and(jK) do
if a[i,j]
else i:=i-1;
if (i>0)and(j
Программа могла бы быть еще короче и эффективней, если бы в ней использовался упоминавшийся выше барьерный метод. В данном случае для организации барьера требуется дополнить массив нулевой строкой и m+1-м столбцом. Во все созданные барьерные элементы следует поместить значение K. Тогда условие в цикле можно сократить до следующего: a[i,j]<>K.
|
Главная
Каталог файлов
