|
Решение задачи 1
Введем массив 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]]);
[Назад]
Решение задачи 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+а+...+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 максимального просмотренного элемента из А;
- значение индексов i0,j0 для максимальной найденной суммы, удовлетворяющей требуемому условию.
Замечание. На начальном этапе p=1, i0=1, j0=2.
При просмотре очередного i элемента из А определяется:
- максимальная сумма из А[i0]+В[j0], А[р]+В[i+1] или А[i]+В[i+1] c пересчетом индексов i0,j0 для максимальной найденной суммы;
- положение 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*logn операций сравнения. Но, наверное, тут мы делаем больше, чем требует постановка задачи - а именно получаем упорядоченную последовательность, тогда как нас интересуют только повторяющиеся элементы. Поэтому, вероятно, данный алгоритм не является наилучшим. По пытаемся найти лучшее решение.
Метод 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. Следовательно, немажорирующих элементов, не вошедших в пары совпадающих элементов 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
[>]
|
