Вход


Главная страница >> Учебный процесс >> Задачник >> Олимпиадные задачи (с решениями) >> Поиск >> Номер 15

[Назад]    [Содержание ]    [Вперед]

  


Номер 15


  Условие: Номер 15


Задача 15. Мажорирующим элементом в массиве A[1..N] будем называть элемент, встречающийся в массиве более N/2 раз. Легко заметить, что в массиве может быть не более одного мажорирующего элемента. Например, массив 3, 3, 4, 2, 4, 4, 2, 4, 4 имеет мажорирующий элемент 4, тогда как в массиве 3, 3, 4, 2, 4, 4, 2, 4 мажорирующего элемента нет. Необходимо определить, есть ли в массиве мажорирующий элемент, и если есть, то какой.

  Решение задачи: Номер 15


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

Назад



[Назад]    [Содержание ]    [Вперед]

  


  
За содержание страницы отвечает Гончарова М.Н.
©
Кафедра СПиКБ, 2002-2017