Вариации на тему поиска

Банально, но факт: одно дело — иметь представление о методе, другое — уметь этот метод применять. Все мы знаем метод половинного деления. Давайте посмотрим, к каким на первый взгляд непохожим задачам он, оказывается, применим.
Одна из стандартных задач информатики — это задача поиска элемента с заданными свойствами в имеющемся наборе элементов. Простейшим способом ее решения является последовательный просмотр набора до нахождения элемента с требуемыми свойствами или установление факта, что такового нет. Очевидно, что в последнем случае необходим просмотр всех элементов набора. Однако иногда, когда заранее известна некоторая информация о наборе, удается существенно сократить количество операций, требуемое для решения этой задачи, применяя другие (не обязательно последовательные) методы поиска.
Наиболее распространенным методом непоследовательного поиска является метод бинарного (двоичного) поиска, который также известен как метод половинного деления или дихотомии. Этот метод получил свое название оттого, что в большинстве случаев при его использовании после каждой итерации область поиска сокращается вдвое (хотя при решении некоторых задач требуется сделать несколько шагов, чтобы удалить некоторую константную порцию (не обязательно 50%) интервала допустимых значений).
Продемонстрируем применение этого метода на примерах задач, встречавшихся на олимпиадах и в литературе.

Задача 1.
Дано целое X и массив отсортированных в порядке неубывания целых чисел А[1..n]. Найти такое i, что A[i]=X, или возвратить i=0, если элемента X в массиве нет.
Одно из решений состоит в просмотре всего массива, что требует времени, пропорционального числу элементов массива. Однако этот алгоритм не использует того факта, что массив A уже отсортирован.
Наилучший метод поиска состоит в том, чтобы проверить, является ли X средним элементом массива A. Если да, то ответ получен. Если X меньше среднего элемента, то, в силу упорядоченности исходного массива, мы можем применить тот же метод поиска к элементам расположенным слева от среднего элемента; аналогично, если X больше среднего элемента, то в дальнейшем мы будем рассматривать правую половину массива.
Мы будем считать, что элемент A[0]=X; ответ возвращается в переменной mid, а через low и high обозначаются, соответственно, индексы начала и конца рассматриваемой части массива. Цикл начинается при high-low=n-1 и завершается при low=high. При каждом выполнении тела цикла величина high-low уменьшается по крайней мере вдвое по сравнению с ее предыдущим значением; таким образом, цикл будет выполняться не более [log2(n-1)]+2 раз (тут через [z] обозначается целая часть числа z). Поэтому говорят, что сложность вышеизложенного метода (который обычно и называется методом дихотомии) О(log2n). Обратите внимание, что в выражение, стоящее в скобках после О, не входит ничего кроме переменной n. Мы рассматриваем только зависимость количества необходимых операций от длины имеющегося массива.
Приведем фрагменты программ, реализующие бинарный поиск с использованием фиктивного элемента А[0] (фрагмент слева) и без него (справа).

A[0]:=X;
low:=1;
high:=n;
repeat
mid:=(low+high) div 2;
if low>high
then mid:=0
else if A[mid]X
then low:=mid+1

else high:=mid;
end;
if A[low]=X
then i:=low
else i:=0;

При n равном, например, 230, последовательный поиск будет длиться десятки минут, а дихотомический же закончиться в доли секунды.
Таким образом факт упорядоченности элементов в массиве играет ключевую роль для существенного сокращения времени поиска. Более того, не существует алгоритма, который требовал бы сравнений меньше, чем алгоритмы деления пополам.
Приведем доказательство этого утверждения, взятое из книги С.А.Абрамова «Математические построения и программирование»:
Пусть мы обладаем некоторым алгоритмом, который требует не более m сравнений. Результаты m сравнений можно записать в виде m-элементной последовательности слов «да» и «нет». Наш алгоритм фактически позволяет по такой последовательности выбрать нужный элемент. Всего элементов n штук, и каждый из них может оказаться тем, который разыскивается. Это означает, что для любого i существует последовательность из m слов «да» и «нет», указывающая на то, что a[i] — искомый. Поэтому должно существовать n последовательностей слов «да» и «нет», каждая из которых содержит не более m слов. Из этих последовательностей никакая не должна быть началом некоторой другой, более длинной последовательности. Таким образом, число этих последовательностей не больше, чем число всех последовательностей из m слов, т.е. 2m. Получаем, что 2m=n и m=log2 n.

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

Задача 2.
На столе в двух столбиках лежат 64 золотых и 64 серебряных монеты соответственно. Как серебряные, так и золотые монеты упорядочены в порядке убывания масс (самая тяжелая — вверху, самая легкая — внизу). Массы всех монет разные. Какое наименьшее количество взвешиваний необходимо для определения 64-ой монеты в порядке убывания масс среди всех 128 монет? За один раз можно взвешивать две монеты и определять, которая из них тяжелее.
Создадим два массива, каждый из которых будет содержать массы монет из первого и второго столбиков соответственно.
Очевидное решение задачи — слияние этих двух массивов в общий упорядоченный массив весов и нахождение в нем 64-го по величине элемента.
Однако задачу можно решить быстрее, используя метод дихотомии. При этом не возникает необходимости объединять исходные массивы.
Обозначим через Ni и Ki начальный и конечный номера элементов в рассматриваемых на данном шаге массивах, i=1,2. Определим номера средних элементов Si=(Ni+Ki) div 2. На первом шаге N1=1, K1=64, N2=1, K2=64, S1=32, S2=32. Значения элементов, стоящих на месте Si, i=1,2, обозначим X и Y.
Сравнив средние элементы X и Y, найдем больший из них. Пусть это X. В силу упорядоченности массива каждый из элементов, стоящих перед X, больше X по величине. С другой стороны, только элементы, стоящие перед Y во втором массиве, могут быть больше X. Поэтому X больше искомого 64-го элемента. Следовательно, в первом массиве можно не рассматривать первые 32 элемента. Аналогично можно показать, что элементы, стоящие после Y, можно также не рассматривать, так как они меньше искомого элемента. После таких действий в массивах осталось по 32 элемента, и при этом необходимо найти 32-й по величине элемент. Повторяем описанный выше процесс с измененными значениями начальных Ni, конечных Ki, и средних Si номеров элементов в массивах по следующему правилу: если больший из X и Y находится в первом массиве, то N1=S1+1, K2=S2; иначе N2=S2+1, K1=S1. Процесс заканчивается, когда в каждом массиве останется по одному элементу. При этом больший из них и будет искомым.
Поскольку количество монет после каждого шага уменьшается в два раза, то количество взвешиваний — log2128=7.

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

Задача 3.
На плоскости своими координатами задается выпуклый N-угольник. Координаты N-угольника целочисленны и перечисляются в порядке обхода по контуpу. Вводятся кооpдинаты точки (X,Y). Опpеделить, является ли она веpшиной N-угольника;
Простейшим решением является просмотр координат вершин N-угольника и определение, совпадают ли координаты одной из них с координатами точки (X,Y). В этом случае необходим просмотр координат всех N вершин многоугольника.
Опять же, можно сократить количество просмотров, используя метод дихотомии.
Пусть вершины пронумерованы от 1 до N в порядке обхода по контуру и их координаты хранятся в массиве.
Сравним вначале координату первой вершины в обходе с координатами точки (X,Y). Если они совпадают, то задача решена. Иначе точка (X,Y) может совпадать с одной из оставшихся N-1 вершиной. Номер начальной вершины оставшегося участка контура равен 2, конечной — N.
Пусть на некотором шаге номера начальной и конечной вершин рассматриваемого контура равны f и p соответственно. Найдем номер средней вершины m=(f+p) div 2. Определим теперь положение точки (X,Y) и вершины с номером f относительно прямой, проходящей через вершины с номерами 1 и m. Возможны следующие ситуации:
1. Точки лежат по одну сторону от прямой. В этом случае нас не интересует часть контура от вершины m до вершины p. Поэтому последней интересующей нас вершиной в контуре можно считать вершину m-1. Полагаем p:=m-1.
2. Точки лежат по разные стороны от прямой. В этом случае нас не интересует часть контура от вершины f до вершины m-1. Поэтому первой интересующей нас вершиной в контуре можно считать вершину m. Полагаем f:=m.
Процесс заканчивается, когда p-f=1 (т.е. осталось только две точки). Проверка их координат на совпадение с точкой (X,Y) и дает ответ на поставленный в задаче вопрос. Для решения задачи нам понадобилось проанализировать O(log2N) вершин.
В рассмотренной задаче была использована упорядоченность по углам, под которым видны вершины выпуклого контура из вершины с номером 1.

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

Задача 4. Корень.
Решить уравнение f(x)=0 на промежутке [a,b], на котором функция f(x) имеет корень и является монотонной и непрерывной. Корень уточнить с точностью n знаков после запятой (если n=5, то ¦f(x)¦<0.00001). Если функция имеет на промежутке единственный корень, значения функции на концах этого промежутка имеют разные знаки, т.е. f(a)*f(b)<0. Найдем середину отрезка [a,b]: с=(a+b)/2. Точка с разделит наш промежуток на две части. Вычислим значение f(c). Если f(c)=0, то с - корень уравнения. Если f(c) 0, то либо f(a)*f(c)<0, либо f(c)*f(b)<0. В качестве нового промежутка [a,b] берем тот, на концах которого функция принимает значения разных знаков. Длина промежутка сократилась вдвое. Описанный выше шаг будем проводить до тех пор, пока значение функции в найденной на текущем шаге точке с не будет меньше 10-n. Возможность использовать метод дихотомии для решения некоторых задач не всегда очевидна. Рассмотрим несколько примеров. Задача 5. На длинной перфоленте записаны N попарно различных положительных целых чисел. Ваша ЭВМ может перематывать ленту на начало и считывать числа одно за другим. Внутренняя память ЭВМ может хранить только несколько целых чисел. Требуется найти наименьшее положительное целое число, которого нет на ленте. Опишите алгоритм, который сделает это за небольшое количество перемоток ленты. Среди N натуральных чисел, записанных на ленте, отсутствует по крайней мере одно число из интервала [1,N+1]. Пусть a - начало, a b - конец некоторого интервала, a и b -целые. Так как записанные на ленте числа различны, то за один просмотр ленты можно подсчитать, сколько чисел на ней попадают в интервал [a,b]. С другой стороны, нетрудно определить количество натуральных чисел интервала [a,b], равное (b-a+1). Алгоритм состоит в следующем. На первом шаге значения начала и конца рассматриваемого интервала положим равными 1 и N+1 соответственно. Пусть на некотором шаге значения начала и конца анализируемого интервала есть f и p. Найдем средний элемент интервала m=(f+p) div 2. Подсчитаем k - количество элементов на ленте, лежащих в интервале [f,m]. Возможны следующие ситуации: 1. Количество элементов kX справедливо f(B) A[1,m]. В этом случае элемента, равного X, в строке с номером 1 быть не может. Поэтому в дальнейшем поиск заданного элемента будет проводиться в массиве A без 1-ой строки.
Таким образом, на каждом шаге, после сравнения заданного элемента X со значением элемента из правого верхнего угла массива, из массива выбрасывается либо строка, либо столбец. В результате этого суммарное число строк и столбцов уменьшается на 1. Поэтому для решения задачи потребуется не более чем N+M сравнений.

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

Чуть изменим формулировку задачи 5:

Задача 10.
Ввод состоит из (N-1)-го различных натуральных чисел между 1 и N. Как можно быстрее и с как можно меньшими затратами памяти определить, какое число отсутствует во вводе.
Рассмотреть случаи
a) N=32767;
б) N — произвольное натуральное число, помещающееся в переменную типа longint (4 байта).
Можно, конечно, решать эту задачу предложенным ранее для задачи 5 методом. Но давайте проведем более тщательный анализ для приведенной формулировки.
Случай а). Обозначим числа из ввода a1, …, a32766.
Отметим, что сумма 1+2+3+…+32767 помещается в переменную типа longint, и если мы из суммы натуральных чисел от 1 до 32767 вычтем сумму всех введенных чисел, то как раз и получим отсутствующее число.
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0
Можно подойти к этой задаче и по другому. Отметим, что если выписать друг под другом в двоичном представлении все числа от 0 до 32767=215-1, то количество единиц в каждом разряде будет четным (действительно, каждому числу D с единицей в разряде i поставим во взаимно однозначное соответствие число 32767-D с нулем в i-ом разряде, при этом ни одно из чисел не перейдет в себя, и, следовательно, чисел с нулем в i-ом разряде столько же, сколько и с единицей, т.е. 214). Напомним что оператор XOR выполняет побитовую операцию над двумя числами согласно приведенным ниже в таблице правилам, и для любого числа D справедливо D XOR D = 0.
Поэтому, выполняя поразрядный XOR над всеми числами от 1 до 215-1, получим 0:

Отсюда следует, что если во вводе пропущено число j, то ,
так как .
Случай б). N — произвольное. Если сумма 1+..+N помещается в longint, то можно воспользоваться первым из приведенных выше способов, иначе же найдем и (одинаковые числа при выполнении последней операции взаимно уничтожаться, и останется именно пропущенный элемент).
Затраты памяти при использовании предложенных методов составляют всего несколько байт, и требуется только один ввод последовательности чисел, в отличие от решения задачи 5.

Задача 11.
В ряд лежат N арбузов, пронумерованных от 1 до N. Нам известно, что:
1) массы первого и N-го арбузов m(1) и m(N) соответственно;
2) масса i-го арбуза m(i) есть среднее арифметическое масс двух соседних арбузов, увеличенное на d: m(i)=d+(m(i-1)+m(i+1))/2;
По введенным m(1), m(N), N, d и j найти m(j).
Мы знаем массу m(1). Если бы мы знали массу m(2), то могли бы вычислить m(3), …, m(N). Следовательно, m(N) зависит от m(2). Возьмем несколько различных значений m(2). Оказывается, что большему значению m(2) соответствует большее значение m(N). Поэтому значение m(2) может быть найдено дихотомическим поиском по интервалу [low,high], где low -это такое значение m(2), при котором полученное значение m(N) меньше заданного в условии задачи, а high — при котором больше. Такой подход называется методом стрельбы.
Проведем более тщательный анализ зависимости m(N) от m(2). Зададим произвольное m'(2) — массу второго арбуза и будем вычислять массы m'(i). Пусть m'(2)-m(2)=s, m'(1)=m(1) и m'(i)=d+(m'(i-1)+m'(i+1))/2. Тогда, так как m(i)=d+(m(i-1)+m(i+1))/2, то
m(i+1)=-2*d+2*m(i)-m(i-1), m'(i+1)=-2*d+2*m'(i)-m'(i-1),
поэтому
m'(3)-m(3)=[-2*d+2*m'(2)-m'(1)]-[-2*d+2*m(2)-m(1)]=2s
m'(4)-m(4)=[-2*d+2*m'(3)-m'(2)]-[-2*d+2*m(3)-m(2)]=3s
…..
m'(n)-m(n)=(n-1)s.
Находим разность m'(n)-m(n)=(n-1)s. Вычисляем s и m(2).
Итак, мы рассмотрели несколько примеров использования общеизвестного метода половинного деления. Он является одновременно и простым, и мощным. На каждой итерации поиска удаляется фиксированный процент множества допустимых значений до тех пор, пока оставшееся множество не станет столь малым, что каждый из его элементов будет решением с желаемыми свойствами.

Приведем еще несколько задач, которые можно эффективно решить, применяя изложенные выше идеи.
12. Определить, можно ли представить заданное натуральное число в виде произведения четырех последовательных натуральных чисел. Длина числа не более 250 символов. Конец числа — пробел.
13. Дан прямоугольный треугольник ABC:

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Можно использовать следующие HTML-теги и атрибуты: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>