Олимпиадные задачи по программированию.

Введем массив b[1]..b[n], отмечающий начало "остающейся части" массивов a[1]..a[n].

  for k:=1 to n do begin
  |  b[k]:=1;
  end;
  eq := true;
  for k := 2 to n do begin
  | eq := eq and (a[1][b[1]] = a[k][b[k]]);
  end;
  {инвариант: оставшиеся части  пересекаются,  т.е.  существует
   такое  х,  что для всякого i из [1..n] найдётся j из [1..m],
   не меньшее b[i], для которого a[i][j] =  х;  eq  <=>  первые
   элементы оставшихся частей равны}
  while not eq do begin
  | s := 1; k := 1;
  | {a[s][b[s]] - минимальное среди a[1][b[1]]..a[k][b[k]]}
  | while k <> n do begin
  | | k := k + 1;
  | | if a[k][b[k]] < a[s][b[s]] then begin
  | | | s := k;
  | | end;
  | end;
  | {a[s][b[s]] - минимальное среди a[1][b[1]]..a[n][b[n]]}
  | b [s] := b [s] + 1;
  | for k := 2 to n do begin
  | | eq := eq and (a[1][b[1]] = a[k][b[k]]);
  | end;
  end;
  writeln (a[1][b[1]]);

[Назад]

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

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

Рассмотрим элемент 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.

[Назад]

Простейшим решением является просмотр элементов i-й строки и i-го столбца, i=1,2,...,N (номера строки и столбца должны быть равны, иначе они пересекаются не по диагональному элементу) массива до нахождения индекса k, такого что элементы k-ой строки и k-го столбца удовлетворяют требуемому свойству или установления факта, что такого индекса нет. Очевидно, что в последнем случае необходим просмотр почти всех элементов массива.

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

Рассмотрим элемент A[k,j], k<>j. Возможны следующие ситуации:

В этом случае легко заметить, что индекс k не подходит, так как в строке с индексом k стоит 0. Поэтому можно ограничится по иском заданного элемента в подмассиве без k-ого столбца и k-й строки.

В этом случае легко заметить, что индекс 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.

[Назад]

Простейшим решением случая а) является просмотр координат вершин 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. Осталось проверить только их координаты на требуемое свойство.

[Назад]

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

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.

[Назад]

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

Заведем массив 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

[Назад]

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

[Назад]

Очевидно, что при вводе n натуральных чисел по крайней мере одно число из интервала [1,n+1] отсутствует.

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

Если все числа от 1 до n 'зарегистрированы', то минимальное отсутствующее натуральное - n+1.

[Назад]

Очевидно, что при вводе 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.

[Назад]

Очевидным решением задачи является создание общего упорядоченного массива, содержащего элементы двух массивов, и нахождение в нем 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 номеров элементов в массивах по следующему правилу:

если Х находится в первом массиве

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

[Назад]

Очевидным решением задачи является создание общего упорядоченного массива, содержащего элементы всех массивов, и нахождение в нем k-того по величине элемента. В этом случае требуется порядка (а₁+а+...+a_n)*log(а₁+а2+...+a_n) операций.

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

Пусть для каждого из наборов i определены начальный N_i и конечный K_i индексы. Определим индексы средних элементов S_i=(N_i+K_i) div 2. Вычислим S=S₁+S₂+... +S_N.

Возможны три ситуации:

1. S > k

Очевидно, что если найти минимальный элемент среди средних элементов (пусть он в наборе j), то ни один из элементов с индексами S_j,...,K_j заведомо не является решением. Поэтому можно пересчитать K_j=S_j-1 (если K_j>N_j).

2. S < k

Очевидно, что если найти максимальный элемент среди средних элементов (пусть он в наборе t), то ни один из элементов с индексами N_t,...,S_t заведомо не является решением. Поэтому можно пересчитать N_t=S_t+1 (если K_t>N_t).

3. S = k

Очевидно, что в этом случае можно пересчитать K_j=S_j и N_t=S_t+1.

Процесс заканчивается, когда начальный N[i] и конечный K[i] индексы удовлетворяют условию K[i]<=N[i] для каждого i. При этом меньший из элементов с индексами K[i] и будет искомым (если K[i]=0, то этот элемент рассматривать не нужно).

[Назад]

Для решения задачи достаточно осуществлять просмотр элементов массивов А и В, фиксируя две величины:

- положение p максимального просмотренного элемента из А;

Замечание. На начальном этапе p=1, i₀=1, j₀=2.

При просмотре очередного i элемента из А определяется:

Процесс заканчивается, когда начальный Ni и конечный Ki индексы равны для каждого i.

[Назад]

Зачастую решение задачи по информатике протекает следующим образом:

Вы смотрите на постановку задачи и, используя приобретенные навыки и известные Вам методы, выдаете решение. При этом обычно неявно считается, что "первый взгляд - наиболее верный", и если решение получено, то на этом "акт творения" программы завершен. Но насколько это "творение" является законченным и эффективным?

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

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

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

Поиск мажорирующего элемента в неупорядоченном массиве.

Найдем какое-нибудь число D, которого нет в массиве (например, пусть D есть увеличенный на 1 максимальный элемент массива).

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

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

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

"Если у Вас есть задача, и Вы не знаете, как ее решать, то от сортируйте входные данные - может быть это Вас натолкнет на дельную мысль".

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

Поиск мажорирующего элемента в упорядоченном массиве.

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

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 операций сравнения. Но, наверное, тут мы делаем больше, чем требует постановка задачи - а именно получаем упорядоченную последовательность, тогда как нас интересуют только повторяющиеся элементы. Поэтому, вероятно, данный алгоритм не является наилучшим. По пытаемся найти лучшее решение.

Мы будем использовать форму двоичного представления числа и некоторые элементы математической логики. Вспомним, что числа в машине хранятся в ячейках памяти. Каждая ячейка имеет фиксированное число разрядов (бит). Пусть 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.

Проверку можно проводить следующим образом:

Оператор 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.

00000010, 00000100.

Разряд i=0, K=2,

Пример 2. Массив A: 3,3,4,2,4,4,2,4,4.

00000010, 00000100, 00000100.

Разряд

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

Пример 3. Массив A: 2,2,3,4,3,4.

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

В дальнейшем нам потребуется такая структура данных, как стек. Стеком будем называть последовательность элементов, упорядоченных по времени их поступления. Эта последовательность доступна только с одного конца (вершины стека). Для работы со стеком необходим указатель вершины стека. Основные операции над стеком следующие: "запомнить в стеке" и "извлечь из стека" (причем извлекается последний из занесенных в стек элементов - то есть элемент с вер шины стека). Поэтому говорят, что стек -- это структура типа LIFO - "Last In - First Out" - "последним зашел - первым вышел". Для представления стека в программе обычно используется одномерный массив (назовем его B), нумерация элементов которого начинается с нуля. В этом нулевом элементе массива хранится индекс первого свободного места в массиве (т.е. увеличенный на 1 индекс вершины стека). Если массив пуст, то указатель равен 1 (B[0]=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;

Заведем массив-стек 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. Следовательно, немажорирующих элементов, не вошедших в пары совпадающих элементов 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.

Мы заведем стек и будем добавлять и извлекать из стека элемен ты по следующему правилу:

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

[Назад]

Вверх по странице, к оглавлению и навигации.