                       Дихотомия и поиск.

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

Function BSearch(var A:input_array; x,n:integer): integer;
var low,high,mid: integer;
begin
   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-1;
  until (A[mid]=x);
   BSearch:=mid;
end;

                            Задача 2.
     Простейшим решением  является  просмотр  элементов массива до
нахождения требуемого элемента или установления факта,  что такого
элемента нет.  Очевидно, что в последнем случае необходим просмотр
всех элементов массива.
     Однако возможно  существенно  сократить  количество операций,
используя следующий факт.
     Рассмотрим элемент  A[1,m].  Возможны следующие ситуации:
  1. X = A[1,m].
     В этом случае заданный элемент найден.
  2. X < A[1,m].
     В этом  случае  легко заметить,  что элемента,  равного X,  в
столбце с номером M быть не может.  Поэтому можно ограничится  по-
иском заданного элемента в подматрице без M-того столбца.
  3. X > A[1,m].
     В этом  случае  легко заметить,  что элемента,  равного X,  в
строке с номером 1 быть не может.  Поэтому можно  ограничится  по-
иском заданного элемента в подматрице без 1-той строки.
     Таким образом,  сравнивая на каждом шаге  значение  заданного
элемента X со значением элемента,  расположенного в правом верхнем
углу интересующей нас подматрицы, суммарное число строк и столбцов
интересующей нас подматрицы уменьшается на 1. Поэтому трудоемкость
такого поиска не превосходит N+M.

                            Задача 5.
     Простейшим решением  является просмотр элементов i-й строки и
i-го столбца,  i=1,2,...,N (номера строки и  столбца  должны  быть
равны, иначе они пересекаются не по диагональному элементу) масси-
ва до нахождения индекса k, такого что элементы k-ой строки и k-го
столбца  удовлетворяют требуемому свойству или установления факта,
что такого индекса нет. Очевидно, что в последнем случае необходим
просмотр почти всех элементов массива.
     Однако возможно существенно  сократить  количество  операций,
используя следующий факт.
     Рассмотрим элемент A[k,j], k<>j. Возможны следующие ситуации:
   1. A[k,j] = 0.
     В этом случае легко заметить,  что индекс k не подходит,  так
как  в строке с индексом k стоит 0.  Поэтому можно ограничится по-
иском заданного элемента в подмассиве  без  k-ого  столбца  и  k-й
строки.
   2. A[k,j] = 1.
     В этом случае легко заметить,  что индекс j не подходит,  так
как в столбце с индексом j стоит 1.  Поэтому можно ограничится по-
иском  заданного  элемента  в  подмассиве  без j-ого столбца и j-й
строки.
     Таким образом, рассматривая на каждом шаге значения элементов
A[k,j], таких что A[k,j] является элементом интересующего нас под-
массива,  потребуется просмотр ровно N-1 элемента для установления
единственного индекса  k,  удовлетворяющего  требуемому  свойству.
Осталось проверить только элементы этого столбца и строки.
     k:=1
     для j от 2 до N
        если A[k,j] = 0
        то   k:=j
     Осталось проверить только элементы k-ого  столбца  и  строки.
Поэтому трудоемкость такого поиска не превосходит 3*N.

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

                            Задача 7.
     Простейшим решением является последовательное определение по-
ложения точки (X,Y) относительно прямых,  проходящей через точки с
координатами   (A[i],1),(B[i],0)   и  (A[i+1],1),(B[i+1],0)  соот-
ветственно, i=1,...N-1. Возможны следующие ситуации:
  1. Точка лежит по одну сторону от прямых.
      Полагаем i:=i+1.
  2. Точка лежит по разные стороны от прямых.
     В этом  случае  интересующей  нас трапецией является конечная
трапеция с индексом i.

     Если же  процесс оканчивается,  а ситуация 2 не возникла,  то
очевидно,  что точка лежит в одной из бесконечных трапеций.  Оста-
лось проверить только положения точки (X,Y) и точки, лежащей заве-
домо в левой (или правой) бесконечной трапеции,  относительно пря-
мой,  проходящей через точки с координатами (A[1],1),(B[1],0), для
определения искомой трапеции.
     Однако возможно  существенно  сократить  количество операций,
используя метод дихотомии.
     Определим индексы начального и конечного номеров интересующей
нас трапеции.  Очевидно,  что вначале они  равны  1  и  N+1  соот-
ветственно (левая  бесконечная  трапеция  имеет номер 1,  правая -
N+1, конечные трапеции - от 2 до N).
     Пусть на некотором шаге индексы начального и конечного  номе-
ров интересующей нас трапеции равны f и l соответственно.  Опреде-
лим индекс среднего номера m=(f+l) div 2.
     Определяем теперь положение точки (X,Y) и точки,  лежащей за-
ведомо в левой бесконечной трапеции,относительно прямой,  проходя-
щей через точки с координатами (A[m],1),(B[m],0).
     Возможны следующие ситуации:
  1. Точки лежат по одну сторону от прямой.
     В этом случае нас не интересуют трапеции с номерами от  m  до
l.  Поэтому последним интересующим нас номером можно считать номер
m. Поэтому полагаем l:=m.
  2. Точки лежат по разные стороны от прямой.
     В этом случае нас не интересуют трапеции с номерами от  f  до
m.  Поэтому  первым  интересующим  нас номером можно считать номер
m+1. Поэтому полагаем f:=m+1.
     Процесс оканчивается, когда f=l.

                            Задача 8.
     Отсортируем концевые точки  отрезков  в  порядке  неубывания.
Если  несколько концевых точек отрезков имеют одинаковую координа-
ту, то сначала выпишем те из них, которые являются начальными точ-
ками  отрезков,  а за ними - конечные точки.  Для такой сортировки
необходимо для каждой точки сохранить информацию,  является ли она
правым или левым концом отрезка.
     Рассмотрим одну из возможных реализаций:
    Заведем массив  A[1..2,1..2*N];  сначала  в ячейки A[1,2i-1] и
A[1,2i] заносим координаты начала и конца i-го отрезка, а в ячейки
A[2,2i-1]  и  A[2,2i] - числа +i и -i -- признаки того,  что соот-
ветствующие координаты являются началом и концом отрезка i. Сорти-
руем  столбцы  массива A по неубыванию элементов первой строки,  и
если при этом несколько элементов первой  строки  равны  (то  есть
соответствующие точки имеют одинаковые координаты), то сначала вы-
писываем начальные точки отрезков (A[2,i]>0),  а затем -  конечные
(A[2,2i-1]<0).
    Заведем еще массив Pr[1..N],  в котором будет храниться инфор-
мация об отрезках, содержащих точку A[1,i]. После окончания работы
алгоритма Pr[j]=1, если отрезок j содержит точку A[1,i], и Pr[j]=0
иначе. Сначала массив Pr нулевой.
    Пусть в переменной C хранится количество отрезков,  пересекаю-
щихся в точке A[1,i]. Сначала C=0.
    Делаем проверку,  размещается ли точка X левее A[1,1] или пра-
вее A[1,2*N]. Если да, то выводим сообщение о принадлежности точки
бесконечному интервалу, если же нет, то будем просматривать массив
A слева направо в порядке неубывания элементов.
   Пока выполняется следующее условие:
     массив A не закончился и
     (или текущая точка A[1,i] < X
      или текущая начальная точка отрезка A[1,i] = X)
   повторять
      Если A[1,i] - начальная точка отрезка,
      то
        увеличить C на 1 (начался еще один отрезок с номером
        A[2,i]), и присвоить Pr[A[2,i]] значение 1.
      Если A[1,i] - конечная точка отрезка,
      то
         уменьшить C на 1 (отрезок с номером -A[2,i] закончился),
         и присвоить Pr[-A[2,i]] значение 0..
   конец_пока.
    Когда мы выйдем из цикла, то проверим:
    Если С=0,  то  X  лежит  на межотрезочном интервале (A[1,i-1],
A[1,i]),  иначе X пpинадлежит C отpезкам. Номера отрезков есть ин-
дексы единичных элементов массива Pr.
   Набросок этого фрагмента программы:
    i:=1;
    пока (i<=2*N) и
         ((A[1,i]<X) или
          (A[1,i]=X) и (A[2,i]>0))
    повторять
         если A[2,i]>0
         то C:=C+1;
            Pr[A[2,i]:=1
            конец_то
         иначе C:=C-1;
               Pr[-A[2,i]:=0
               конец_иначе
         i:=i+1;
    конец_пока
    если С=0,
    то  X лежит на межотрезочном интервале (A[1,i-1],A[1,i]),
    иначе X пpинадлежит C отpезкам. Напечатаем номера этих от-
          резков:
            для i:=1 до N повторять
                если Pr[i]=1
                то печатать i

                            Задача 9.
     Решается аналогично задаче 8. Точки, принадлежащие максималь-
ному  числу  отрезков  сами образуют отрезок (отрезки).  Концевыми
точками этого отрезка (этих отрезков) являются  какие-то  концевые
точки заданных отрезков. Вспомним еще, что в переменной C хранится
количество отрезков,  пересекающихся в точке A[1,i] - конце отрез-
ка.

                            Задача 10.
     Очевидно, что при вводе n натуральных чисел по  крайней  мере
одно число из интервала [1,n+1] отсутствует.
     Поэтому идея решения состоит в том, что отводится массив из n
чисел,  в котором элемент с индексом i 'регистрирует',  пришло  ли
число со значением i.  После 'регистрации' всех элементов последо-
вательности осталось только проверить,  какое минимальное число не
'зарегистрировано'.  (В  качестве  признака  'регистрации' числа i
можно заносить в i-ый элемент массива 1.  Первоначально все  числа
не 'зарегистрированы' - все элементы массива равны 0).
     Если все числа от 1 до n 'зарегистрированы',  то  минимальное
отсутствующее натуральное - n+1.

                            Задача 11.
     Очевидно, что  при  вводе n натуральных чисел по крайней мере
одно число из интервала [1,n+1] отсутствует.
     Определим начало  a  и конец b некоторого интервала индексов,
который нас интересует. Возможно ли за один просмотр ленты устано-
вить,  все ли числа из интервала [a,b] присутствуют на ленте? Учи-
тывая факт,  что  записанные  числа  различны,  можно  определить,
сколько  чисел,  записанных на ленте,  попадают в интересующий нас
интервал.  С другой стороны,  нетрудно определить количество нату-
ральных чисел на интервале [a,b] - это (b-a+1).
     Поэтому алгоритм состоит в следующем.
     Определим значения  начала и конца интересующего нас интерва-
ла. Очевидно, что вначале они равны 1 и N+1 соответственно.
     Пусть на некотором шаге значения начала и конца интересующего
нас интервала равны f и l соответственно. Определим индекс средне-
го элемента интервала m=(f+l) div 2.
     Определяем теперь количество элементов k на ленте,  лежащих в
интервале [f,m].
     Возможны следующие ситуации:
  1. Количество элементов k<m-f+1 .
     В этом  случае нас не интересует интервал от m до l,  так как
на интервале [f,m] хотя бы одно число отсутствует.  Поэтому  инте-
ресующим  нас  интервалом  можно  считать [f,m].  Поэтому полагаем
l:=m.
  2. Количество элементов k=m-f+1 .
     В этом случае нас не интересует интервал от f до m,  так  как
на  интервале  [f,m]  все натуральные присутствуют.  Поэтому инте-
ресующим нас интервалом можно считать  [m+1,l].  Поэтому  полагаем
l:=m+1.
     Процесс оканчивается, когда f=l.

                            Задача 12.
     Очевидным решением задачи является создание  общего  упорядо-
ченного массива,  содержащего элементы двух массивов, и нахождение
в нем 64-того по величине элемента.
     Однако можно  существенно  сократить трудоемкость,  используя
дихотомический способ поиска.
     Пусть для  каждого  из двух наборов определены начальный Ni и
конечный Ki номера элементов в массивах, рассматриваемых на данном
шаге алгоритма, i=1,2. Определим номера средних элементов Si=(Ni+
+Ki)/2. Понятно,  что на первом этапе N1=1,  K1=64, N2=1, K2=64, а
S1=32, S2=32. Обозначим эти средние элементы массивов X и У
     Сравнив эти средние элементы Х и У,  найдем больший  из  них,
и пусть это Х.  Понятно, что каждый из элементов, стоящих перед Х,
не меньше Х по величине.  С другой стороны, только элементы, стоя-
щие перед средним элементом У другого массива, могут быть не мень-
ше Х.  Поэтому Х не меньше 64-го элемента.  Следовательно все эле-
менты первого массива от первого до элемента Х включительно (всего
32 элемента) можно выбросить,  учитывая при этом, что теперь необ-
ходимо искать 32-й по величине элемент среди оставшихся. Аналогич-
но можно показать,  что по крайней мере 63  элемента  (выброшенные
элементы и элементы,  стоящие перед У,) не меньше У.  Поэтому эле-
менты,  стоящие после У,  можно тоже выбросить,  так как они малы.
После таких действий в массивах осталось по 32 элемента, и при этом
необходимо найти 32-й по величине элемент. Повторяем описанный вы-
ше процесс с измененными значениями начальных Ni и конечных Ki но-
меров элементов в массивах по следующему правилу:
   если Х находится в первом массиве
       то     N1=S1+1; K2=S2
       иначе  N2=S2+1; K1=S1.
  Процесс заканчивается, когда осталось по одному элементу в каждом
массиве. При этом меньший из них и будет искомым.

                            Задача 13.
     Очевидным решением задачи является создание  общего  упорядо-
ченного массива,  содержащего элементы всех массивов, и нахождение
в нем k-того по величине элемента. В этом случае требуется порядка
(а1+а2+...+an)*log(а1+а2+...+an) операций.
     Однако можно существенно  сократить  трудоемкость,  используя
дихотомический способ поиска.
     Пусть для каждого из наборов i определены начальный Ni и  ко-
нечный Ki индексы.  Определим индексы средних элементов Si=(Ni+Ki)
div 2. Вычислим S=S1+S2+... +SN.
     Возможны три ситуации:
     1. S > k
     Очевидно, что  если  найти  минимальный элемент среди средних
элементов (пусть он в наборе j),  то ни один из  элементов  с  ин-
дексами Sj,...,Kj заведомо не является решением. Поэтому можно пе-
ресчитать Kj=Sj-1 (если Kj>Nj).
     2. S < k
     Очевидно, что если найти максимальный элемент  среди  средних
элементов  (пусть  он  в наборе t),  то ни один из элементов с ин-
дексами Nt,...,St заведомо не является решением. Поэтому можно пе-
ресчитать Nt=St+1 (если Kt>Nt).
     3. S = k
     Очевидно, что   в  этом  случае  можно  пересчитать  Kj=Sj  и
Nt=St+1.
     Процесс заканчивается,  когда  начальный N[i] и конечный K[i]
индексы удовлетворяют условию K[i]<=N[i] для каждого i.  При  этом
меньший  из  элементов  с  индексами  K[i]  и  будет искомым (если
K[i]=0, то этот элемент рассматривать не нужно).

                            Задача 14.
     Для решения задачи достаточно осуществлять просмотр элементов
массивов А и В, фиксируя две величины:
    - положение p максимального просмотренного элемента из А;
    - значение индексов i_0,j_0 для максимальной найденной  суммы,
      удовлетворяющей требуемому условию.
    Замечание. На начальном этапе p=1, i_0=1, j_0=2.
При просмотре очередного  i элемента из А определяется:
   - максимальная  сумма   из   А[i_0]+В[j_0],   А[р]+В[i+1]   или
     А[i]+В[i+1]  c  пересчетом  индексов i_0,j_0 для максимальной
     найденной суммы;
   - положение p максимального просмотренного элемента из А (срав-
     нивая значения А[р]+А[i]).  Процесс выполняется для i от 2 до
     m-1.
Процесс заканчивается,  когда начальный Ni и конечный  Ki  индексы
равны для каждого i.

                            Задача 15.
   Зачастую решение задачи по информатике протекает следующим об-
разом:
   Вы смотрите  на  постановку задачи и,  используя приобретенные
навыки и известные Вам методы,  выдаете решение.  При этом обычно
неявно считается,  что "первый взгляд - наиболее верный",  и если
решение получено,  то на этом "акт творения" программы  завершен.
Но насколько это "творение" является законченным и эффективным?
   На примере решения предлагаемой задачи, которая не является ни
краеугольной, ни фундаментальной в науке, мы попытаемся показать,
что  первый взгляд может всего не увидеть,  и что если после него
еще чуть-чуть подумать,  то результат  может  получиться  намного
лучше (что верно не только в информатике).  Мы приведем пять раз-
ных подходов к решению одной и той же задачи,  каждый из  которых
является одним из распространенных стандартных методов.
   Все приведенные примеры фрагментов программ написаны на  языке
Паскаль,  так как он является одновременно мощным, ясным и струк-
турированным языком программирования. Мы надеемся, что даже люди,
не  знакомые с Паскалем,  смогут понять зти фрагменты,  используя
знания Бейсика, английского языка, а также комментарии практичес-
ки у каждого оператора.
   Массив - это последовательность однотипных элементов, в школь-
ном алгоритмическом языке его также называют таблицей.  В условии
задачи  A[1..N] обозначает массив из N элементов с индексами от 1
до N.  Встречающаяся ниже операция div обозначает деление и  дает
целую часть частного; например 11 div 3 = 3.

                     Метод 0. Первый взгляд.
     Поиск мажорирующего элемента в неупорядоченном массиве.
    --------------------------------------------------------
   Найдем какое-нибудь число D,  которого нет в массиве  (напри-
мер, пусть D есть увеличенный на 1 максимальный элемент массива).
   Алгоритм состоит в  следующем:  на  i-ом  шаге  подсчитывается
сколько среди элементов A[i+1], A[i+2], ..., A[N] таких, значение
которых равно значению элемента A[i].  Таким элементам присваива-
ется значение D и в дальнейшем они рассматриваться не будут. Оче-
видно,  что  достаточно  проверить  только  элементы  A[1],  ...,
A[(N+1) div 2], так как оставшиеся элементы не могут быть мажори-
рующими.

   Max:=A[1];
   for i:=2 to n do      { Поиск максимального элемента массива }
     if A[i] > Max
     then Max:=A[i];
   D:=Max+1;             { Находим число D, которого  в массиве нет   }
   for i:=1 to (N+1) div 2 do   { Берем в качестве возможного решения }
    begin                       { элементы из первой половины массива }
     Count:=1;
     if A[i]<>D                 { Подсчитываем, сколько раз элемент   }
     then                       { встречается среди оставшихся        }
       for j:=i+1 to N do
         if A[i]=A[j]
         then
           begin
             Count:=Count+1; {  Увеличение счетчика встретившихся }
                             {  элементов                         }
             A[j]:=D;        {  Заполнение элемента значением D   }
           end;
     if Count*2>N            { Мажорирующий? }
     then
       begin
        writeln('Мажорирующий элемент',A[i])   { Печать }
        Halt;                                  {  Стоп  }
       end
    end;
    writeln('Мажорирующего элемента нет');

   Этот алгоритм  в  худшем  случае  (когда все элементы масссива
различны),  выполняет (N-1) + (N-2) + ...  +  [(N+1)/2]  операций
сравнения. Если подсчитать сумму этой арифсметической прогрессии,
то мы получим величину порядка N*N.  Обычно в этом  случае  гово-
рится, что предложенный алгоритм имеет сложность О(N*N).
   В программистском фольклоре можно найти упоминание об  "амери-
канской методике решения задачи", состоящей в следующем:
   "Если у Вас есть задача, и Вы не знаете, как ее решать, то от-
сортируйте входные данные - может быть это Вас натолкнет на дель-
ную мысль".
   Может быть  и нам стоит последовать этому мудрому совету и пе-
реупорядочить элементы так, чтобы все одинаковые шли друг за дру-
гом, после чего посмотреть,  уменьшится ли число сравнений и, со-
ответственно, сложность алгоритма?

                      Метод 1. Сортировка.
      Поиск мажорирующего элемента в упорядоченном массиве.
     ------------------------------------------------------
   Отсортируем исходный массив по неубыванию, а затем просмотрим
его, подсчитывая число идущих подряд одинаковых элементов.

 for i:=1 to N-1 do    {-------------------------------}
  for j:=2 to N do     {                               }
    if A[i]>A[j]       {   Сортировка по неубыванию    }
    then               {      методом пузырька         }
      begin            {                               }
         tmp:=A[i];    {                               }
         A[i]:=A[j];   {                               }
         A[j]:=tmp     {                               }
      end;             {-------------------------------}

 Count:=1;             { Количество одинаковых элементов }
 for i:=2 to N do
   if A[i]<>A[i-1]
   then if Count > N div 2
        then
         begin
          writeln('Mажорирующий элемент ',A[i-1]);  { Распечатать }
          Halt                                      {    Стоп     }
         end;
        else Count:=0   { Начать подсчет для следующего элемента  }
   else Count:=Count+1; { Увеличить счетчик для текущего элемента }
   
   Поиск мажорирующего  элемента можно организовать и по другому:
если в отсортированном массиве  a[i]=a[i + N div 2],  то  элемент
a[i] -- мажорирующий. С учетом этого цикл просмотра массива запи-
шется так:
 for i:=1 to (N+1) div 2 do
   if A[i]<>A[i + N div 2]
   then begin
          writeln('Mажорирующий элемент ',A[i]);  { Распечатать }
          Halt                                    {    Стоп     }
         end;
   writeln('Мажорирующего элемента нет');
        
   Сортировка методом  пузырька  требует  выполнения  порядка N*N
операций сравнения  и не дает никакого выигрыша относительно пре-
дыдущего алгоритма. При использовании более эффективной сортиров-
ки (например, "быстрой", см., например, книгу Н. Вирта "Алгоритмы
+ структуры данных = программы") потребуется порядка N*log N опе-
раций сравнения.  Но,  наверное, тут мы делаем больше, чем требу-
ет постановка задачи - а именно получаем упорядоченную последова-
тельность, тогда  как нас интересуют только повторяющиеся элемен-
ты. Поэтому, вероятно, данный алгоритм не является наилучшим. По-
пытаемся найти лучшее решение.
                               
        Метод 2. Машинно-ориентированный вариант решения.
        ------------------------------------------------
     Мы будем использовать форму двоичного представления числа  и
некоторые элементы математической логики.  Вспомним,  что числа в
машине хранятся в ячейках памяти. Каждая ячейка имеет фиксирован-
ное число разрядов (бит).  Пусть A - массив из N однобайтных эле-
ментов,  следовательно, каждый элемент этого массива A[i] cостоит
из 8 бит. Например, элементы массива 2,3,2,5,16 будут представле-
ны в виде:
   00000010, 00000011, 00000010, 00000101, 00010000.
   Рассмотрим следующий алгоритм:
   На i-ом  шаге  (i=0,...,7,  по  количеству бит в представлении
числа ) мы проверяем,  каких чисел больше: у которых i-ый бит ра-
вен 0 или у которых i-ый бит равен 1. Количество чисел, у которых
i-ый бит равен 1, обозначим K.
   Проверку можно проводить следующим образом:
       for j:=1 to N do
         if A[j] and (1 shl i) <>0 then K:=K+1;
   Оператор 1 shl i ставит 1 в i-ый бит в байте,  остальные  биты
равны 0  (биты  нумеруются  справа  налево  от 0 до 7).  Например,
1 shl 2 формирует число 00000100, а 1 shl 4 -- 00010000.
   Оператор and  выполняет  логическое (побитовое) умножение двух
чисел, согласно приведенным в таблице правилам:
                        A    B    A and B
                       -------------------
                        0    0       0
                        0    1       0
                        1    0       0
                        1    1       1
   Из сказанного следует, что с помощью оператора A[j] and (1 shl
i) мы в числе A[j] выделяем i-ый бит.  Например, если А[i] в дво-
ичной системе представляется в виде 01011001,  и i=4, то
     A[j] and (1 shl i) = 01011001 and 00010000 = 00010000,
Отметим также, что если хоть в одном из битов представления числа
стоит 1, то это число ненулевое.
   Таким образом в K получаем количество элементов массива, у ко-
торых i-ый бит равен 1.
   Идея алгоритма  состоит в том,  чтобы сформировать число C как
возможное решение,  заполняя на i-ом шаге его i-ый бит нулем  или
единицей в зависимости от значения K.  Очевидно,  что если 2*K=N,
то мажорирующего элемента нет.  Если 2*K>N, то, если мажорирующий
элемент существует, его i-ый бит должен равняться единице, а если
2*K<N - то нулю.  В числе C выставляем в i-ый бит 0 или 1,  в за-
висимости от результата сравнения чисел 2*K и N.
   После 8-го прохода нам остается лишь проверить за один  проход
по массиву,  является ли сформированное число C мажорирующим эле-
ментом.
   Рассмотрим несколько примеров:
   
   Пример 1. Массив A: 3,3,4,2,4,4,2,4.
   В  двоичном представлении последовательность имеет вид:
   00000011, 00000011, 00000100, 00000010, 00000100, 00000100,
   00000010, 00000100.
   
   Разряд  i=0,    K=2,
           i=1,    K=4, 2*K=N, мажорирующего элемента нет.
   
   Пример 2. Массив A: 3,3,4,2,4,4,2,4,4.
   В  двоичном представлении последовательность имеет вид:
   00000011, 00000011, 00000100, 00000010, 00000100, 00000100,
   00000010, 00000100, 00000100.
   
   Разряд i=0,    K=2,   С=00000000
          i=1,    K=4,   С=00000000
          i=2,    K=5,   С=00000100
          i=3,    K=0,   С=00000100
          i=4,    K=0,   С=00000100
          i=5,    K=0,   С=00000100
          i=6,    K=0,   С=00000100
          i=7,    K=0,   С=00000100
   Требуется еще один просмотр  для  того,  чтобы  убедится,  что
сформированный элемент действительно является мажорирующим.
   
   Пример 3. Массив A: 2,2,3,4,3,4.
   В  двоичном представлении последовательность имеет вид:
   00000010, 00000010, 00000011, 00000100, 00000011, 00000100.
   
   Разряд i=0,    K=2,   С=00000000
          i=1,    K=4,   С=00000010
          i=2,    K=2,   С=00000010
          i=3,    K=0,   С=00000010
          i=4,    K=0,   С=00000010
          i=5,    K=0,   С=00000010
          i=6,    K=0,   С=00000010
          i=7,    K=0,   С=00000010
   Дополнительный просмотр  исходного  массива  дает  возможность
убедиться в том, что сформированный элемент не является мажориру-
ющим.
               
                         Общие сведения.
                        -----------------
   В дальнейшем нам потребуется такая структура данных, как стек.
Стеком будем называть последовательность элементов, упорядоченных
по времени их поступления. Эта последовательность доступна только
с  одного  конца (вершины стека).  Для работы со стеком необходим
указатель вершины стека.  Основные операции над стеком следующие:
"запомнить  в  стеке"  и  "извлечь  из стека" (причем извлекается
последний из занесенных в стек элементов - то есть элемент с вер-
шины стека). Поэтому говорят, что стек -- это структура типа LIFO
- "Last In - First Out" - "последним зашел - первым  вышел".  Для
представления  стека  в  программе обычно используется одномерный
массив (назовем его B), нумерация элементов которого начинается с
нуля.  В  этом  нулевом  элементе массива хранится индекс первого
свободного места в массиве (т.е.  увеличенный на 1 индекс вершины
стека). Если массив пуст, то указатель равен 1 (B[0]=1).
   Добавление элемента  X  в  стек  реализуется очень просто - на
первое свободное место (индекс которого хранится в B[0])  помеща-
ется X,  после чего индекс первого свободного места увеличивается
на 1:
   
     B[B[0]]:=x;         { Занести в стек }
     B[0]:=B[0]+1;       { Увеличить указатель }
   
   Если необходимо извлечь элемент x из стека, то берется послед-
ний из занесенных элементов (естественно,  только в  том  случае,
если стек непуст),  и указатель на первое свободное место умень-
шается на 1:
   
     if B[0]<>1 { Если стек не пуст }
     then
       begin
         x:=B[B[0]];     { Взять элемент }
         B[0]:=B[0]-1;   { Уменьшить указатель }
       end;


                      Метод 3. Два массива.
                      ---------------------
   Заведем массив-стек B. Первоначально он пуст.
   В случае, если N - нечетное, N>1, то для элемента, не имеющего
пары, проверяем простым проходом по массиву и подсчетом, не явля-
ется ли он мажорирующим.  Если нет,  то уменьшаем N на 1 и сводим
задачу к случаю четного N.
   Предположим, что N - четное.  Сравним A[1] и  A[2].  Если  они
равны, то  один  из  элементов  заносим в массив-стек B на первое
свободное место,  иначе ничего не делаем. Затем сравниваем A[3] и
A[4].  Опять же, если они равны, то один из элементов добавляем к
B,  в противном случае ничего не делаем. Повторяем процесс до тех
пор, пока не просмотрим все пары из массива A.
   Утверждение: Если в массиве A есть мажорирующий элемент, то он
будет являться мажорирующим и в массиве B.
   Докажем это.  Пусть  N=2*k  и в A есть m пар,  составленных из
совпадающих немажорирующих элементов.  Мажорирующих элементов в A
по крайней мере k+1.  Следовательно, немажорирующих элементов, не
вошедших в пары сBовпадающих элементов N-2*m-(k+1)=k-2*m-1.  Итак,
среди  k пар есть:
   m пар из немажорирущих совпадающих элементов,
   не более k-2*m-1 пар из мажорирующего и  немажорирующего  эле-
ментов  и
   k-m-(k-2*m-1)=m+1  пара из мажорирующих элементов.
То есть,  при приведенном выше преобразовании, элемент мажорирую-
щий в A является таковым и в B.
   Далее, перед следующим шагом алгоритма,  пересылаем содержимое
массива B в массив A, массив B считаем пустым.
   Для нового массива A повторяем описанные выше действия.
   В конце  концов  после очередного шага либо массив B пуст - и,
следовательно, в исходном массиве не было мажорирующего элемента,
либо в B находится один единственный элемент,  который, возможно,
и является мажорирующим.  С целью проверки  пройдем  еще  раз  по
исходному массиву и подсчитаем, сколько раз интересующий нас эле-
мент там встретится - больше N/2 раз или нет. Необходимость доба-
вочного  прохода  по массиву можно показать на примере следующего
массива: 2 2 3 4 3 4.
   Оценим число обращений к элементам исходного массива:  на каж-
дом  шаге алгоритма мы совершаем просмотр всех элементов текущего
массива. Если размерность массива нечетная, то она уменьшается на
1,  если же четная - то вдвое. Таким образом, при выполнении каж-
дых двух шагов алгоритма размерность массива уменьшается по край-
ней мере вдвое,  и общее число обращений к элементам  массива  не
будет превышать  величины  2*(N  +  N/2 + N/4 + ...) = 4N (сумма,
стоящая в скобках, есть сумма геометрической прогрессии со знаме-
нателем 1/2).  Для определения того,  на самом ли деле полученный
элемент является  мажорирующим,  требуется  еще  один  проход  по
исходному массиву. Итого, число операций не превышает 5*N.

   
                         Метод 4. Стек.
                         --------------
   Мы заведем стек и будем добавлять и извлекать из стека элемен-
ты по следующему правилу:
   1) На первом шаге помещаем в стек A[1] .
   2) На i-ом шаге, i=2, ..., N повторяем следующие действия:
           Если   стек пуст,
           то     помещаем в него A[i]
           иначе
                  если  элемент A[i] совпадает с элементом
                        на верхушке стека
                  то    добавляем A[i] в стек
                  иначе удаляем элемент с верхушки стека.

    Если стек не пуст,  то в нем находятся лишь совпадающие  эле-
менты. Если у нас в последовательности есть мажорирующий элемент,
то он и останется в стеке после N-го шага (мажорирующие  элементы
встречаются  в  последовательности более N/2 раз,  и не могут при
выполнении N шагов алгоритма "сократиться"  со  всеми  остальными
немажорирующими элементами).
    Для проверки (в случае непустого стека после выполнения  N-го
шага)  является ли элемент в стеке мажорирующим (если в стеке бо-
лее одного элемента,  то они  все  совпадают),  мы  просматриваем
массив еще  один  раз  и подсчитываем,  сколько раз встречается в
массиве элемент из стека. Если это число больше N/2, то этот эле-
мент  мажорирующий,  иначе  - мажорирующего элемента в последова-
тельности нет.

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

        begin
          element:=A[1];       { Присвоение начальных значений }
          Count:=1;
          for i:=2 to N do
            if Count=0              { Счетчик нулевой? }
            then
               begin                { Да }
                 element:=A[i];     { Начать подсчет для нового }
                 Count:=1;          { элемента                  }
               end
            else                    { Если счетчик ненулевой }
              if element=A[i]       {  Элементы совпадают?   }
              then Count:=Count+1   { Да.  Увеличить счетчик }
              else Count:=Count-1;  { Нет. Уменьшить счетчик }
          if Count=0
          then writeln(' Мажорирующего элемента нет')
          else
            begin
              Count:=0;
              for i:=1 to n do      { Добавочный проход }
                if A[i]=element
                then Count:=Count+1;
              if Count*2>N
              then writeln('Мажорирующий элемент',element)
              else writeln('Мажорирующего элемента нет');
            end;
        end.

   Указанным выше  способом  можно  искать в массиве A и элемент,
удовлетворяющий такому условию:
   Элемент встречается в A не менее N/2 раз (в предыдущей  форму-
лировке задачи он должен был встречаться более N/2 раз). При чет-
ном N таких элементов, очевидно, может быть два.
   В случае вышеприведенной формулировки задачи мы проделываем ту
же самую последовательность действий, что и ранее: в случае, если
после N-го шага стек не пуст,  то оставшийся в нем элемент  явля-
ется претендентом на искомый,  и мы просматриваем массив еще раз,
подсчитывая, сколько раэ он там встречается.
   В случае,  если стек пуст,  то вполне возможно, что требуемому
свойству удовлетворяет два элемента,  и именно они то и принимали
участие  в  сравнении на N-ом,  последнем шаге.  Мы совершаем еще
один проход по массиву,  подсчитывая,  сколько раз встречаются  в
нем элементы element и A[n]. Затем делаем две проверки:
   Если количество для element не меньше N/2,  то element - иско-
мый  элемент.  Если количество для A[n] не меньше N/2,  то A[n] -
искомый элемент.

                           Заключение.
   Составим таблицу сложностей алгоритмов, предложенных для реше-
ния сформулированной задачи:
                            
   Алгоритм                   Сложность
   -------------------------------------------------------------
   0. Без упорядочения         N*N
   1. С упорядочением          в зависимости от способа сортиров-
                               ки от N*log N до N*N
   2. Машинно-ориентированный  С*N, С зависит от формата числа
      вариант
   3. С использованием двух    <=5*N
      массивов
   4. С использованием стека   2*N

