Решение задачи 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
|
