ЕДИНСТВЕННО ВЕРНОЕ РЕШЕНИЕ?

Зачастую решение задачи по информатике протекает следующим об-
разом:
Вы смотрите на постановку задачи и, используя приобретенные
навыки и известные Вам методы, выдаете решение. При этом обычно
неявно считается, что «первый взгляд — наиболее верный», и если
решение получено, то на этом «акт творения» программы завершен.
Но насколько это «творение» является законченным и эффективным?
Давайте рассмотрим пример решения одной задачи, которая не яв-
ляется ни краеугольной, ни фундаментальной в науке, — это просто
пример того, что первый взгляд может всего не увидеть, и что если
после него еще чуть-чуть подумать, то результат может получиться
намного лучше (что верно не только в информатике). Мы приведем
пять разных подходов к решению одной и той же задачи, каждый из
которых является одним из распространенных стандартных методов.
Итак:
Задача. Мажорирующим элементом в массиве A[1..N] будем назы-
вать элемент, встречающийся в массиве более N/2 раз. Легко заме-
тить, что в массиве может быть не более одного мажорирующего эле-
мента. Например, массив 3, 3, 4, 2, 4, 4, 2, 4, 4 имеет мажориру-
ющий элемент 4, тогда как в массиве 3, 3, 4, 2, 4, 4, 2, 4 мажо-
рирующего элемента нет.
Необходимо определить, есть ли в массиве мажорирующий элемент,
и если есть, то какой.
. . .
Все приведенные примеры фрагментов программ написаны на языке
Паскаль, так как он является одновременно мощным, ясным и струк-
турированным языком программирования. Мы надеемся, что даже люди,
не знакомые с Паскалем, смогут понять зти фрагменты, используя
знания Бейсика, английского языка, а также комментарии практичес-
ки у каждого оператора.
Массив — это последовательность однотипных элементов, в школь-
ном алгоритмическом языке его также называют таблицей. В условии
задачи 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).
В программистском фольклоре можно найти упоминание об «амери-
канской методике решения задачи», состоящей в следующем: «Если у
Вас есть задача, и Вы не знаете, как ее решать, то отсортируйте
входные данные — может быть это Вас натолкнет на дельную мысль».
Может быть и нам стоит последовать этому мудрому совету и переу-
порядочить элементы так, чтобы все одинаковые шли друг за другом,
после чего посмотреть, уменьшится ли число сравнений и, соответс-
твенно, сложность алгоритма?

Метод 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. Очевидно, что если 2K=N,
то мажорирующего элемента нет. Если 2K>N, то, если мажорирующий
элемент существует, его i-ый бит должен равняться единице, а если
2K1 { Если стек не пуст }
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=2k и в A есть m пар, составленных из сов-
падающих немажорирующих элементов. Мажорирующих элементов в A по
крайней мере k+1. Следовательно, немажорирующих элементов, не во-
шедших в пары совпадающих элементов N-2m-(k+1)=k-2m-1. Итак,
среди k пар есть: m пар из немажорирущих совпадающих элементов;
не более k-2m-1 пар из мажорирующего и немажорирующего элементов;
k-m-(k-2m-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). Для определения того, на самом ли деле полученный
элемент является мажорирующим, требуется еще один проход по
исходному массиву. Итого, число операций не превышает 5N.

Метод 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
1. С упорядочением в зависимости от способа сортиров-
ки от N*N до N log N
2. Машинно-ориентированный СN, С зависит от формата числа
вариант
3. С использованием двух <=5N массивов 4. С использованием стека 2N Мы планируем в следующих статьях провести разбор других клас- сов задач, и для каждого из них дать свои стандартные методы ре- шения. И.А.Волков, В.М.Котов, Т.Г.Котова

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

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

методические материалы по информатике