Задача 1.
Дано целое х и массив целых чисел А[1], ..., А[n], которые
отсортированы в порядке неубывания и уже находятся в памяти. Найти
такое i, что A[i]=x, или возвратить i=0, если элемента x в массиве
нет.
Задача 2.
Задан массив чисел А[1:N,1:M],упорядоченный по возрастанию по
строкам и столбцам, т.е.:
А[I,1]<А[I,2]<...<А[I,M] (при всех I),
А[1,J]<A[2,J]<...<А[N,J] (при всех J).
Найти элемент массива, равный заданному числу Х и отпечатать
его индексы (I,J). Напечатать слово "НЕТ", если такого элемента
не окажется. Х можно сравнить не более, чем с M+N элементами
массива.
Задача 3.
Написать подпрограмму, которая в двумерном массиве А(N,M)
целых чисел, таком, что для всех I от 1 до N , J от 1 до М-1 вы-
полняется А(I,J)>A(I,J+1) и для всех I от 1 до N-1 выполняется
A(I,M)>A(I+1,M), находит все элементы A(I,J), равные J+I, или
устанавливает, что таких элементов нет.
Задача 4.
Написать подпрограмму, которая в двумерном массиве А(N,M)
целых чисел, таком, что для всех I от 1 до N , J от 1 до М-1 вы-
полняется А(I,J)<A(I,J+1) и для всех I от 1 до N-1 выполняется
A(I,M)<A(I+1,M), находит все элементы A(I,J), равные J+I , или
устанавливает, что таких элементов нет.
Задача 5.
Задана прямоугольная таблица А[1:N,1:N], элементы которой
равны 0 или 1 причем А[i,i]=0 для любого i.
Необходимо найти, если они есть, такие строку i0 и столбец
j0, чтобы в столбце j0 были все 0, а в строке i0 - все 1 (кроме
элемента A[i0,i0], равного 0).
Задача 6.
На плоскости задается выпуклый N-угольник целочисленными
кооpдинатами своих веpшин в порядке обхода по контуpу. Вводятся
кооpдинаты точки (X,Y). Опpеделить:
a) является ли она веpшиной N-угольника;
б) пpинадлежит ли она N-угольнику.
Задача 7.
На двух паpаллельных пpямых слева напpаво заданы по N точек
на каждой.
├────┬──────┬─────┬───┬───────┬──── A
│ │ / / x,y \ │
│ │ / / . \ │
├────┴───┴─────┴─────────┴────┴──── B
0
Их кооpдинаты задаются в массивах A[1..N] и B[1..N]. Расстоя-
ние между пpямыми единичное. Вводится точка (X,Y), где 0<Y<1.
Опpеделить, в какой из получившихся N-1 конечных и 2 бесконечных
тpапециях лежит точка.
Задача 8.
На пpямой своими концами заданы N отpезков и точка X. Опpеде-
лить, пpинадлежит ли точка межотpезочному интеpвалу. Если да, то
указать концевые точки этого интервала. Если нет, то найти,
а. Какому количеству отpезков пpинадлежит точка.
б. Каким именно отрезкам принадлежит точка.
Задача 9.
На пpямой своими концами заданы N отpезков. Найти точку, при-
надлежащую максимальному числу отрезков
Задача 10.
Вводится последовательность из n натуральных чисел.Необходимо
определить наименьшее натуральное число, отсутствующее в последо-
вательности.
Задача 11.
На длинной перфоленте записаны N попарно различных положи-
тельных целых чисел. Ваша ЭВМ может перематывать ленту на начало и
считывать числа одно за другим. Внутренняя память машины может
хранить только несколько целых чисел. Требуется найти наименьшее
положительное целое число,которого нет на ленте. Опишите алго-
ритм,который сделает это за небольшое количество перемоток ленты.
Задача 12.
На столе в двух столбиках лежат 64 золотых и 64 серебряных
монеты соответственно. Как серебряные, так и золотые монеты упоря-
дочены в порядке убывания масс. Массы всех монет разные. Какое на-
именьшее количество взвешиваний необходимо для определения 64-ой
монеты в порядке убывания масс среди всех 128 монет? За один раз
можно взвешивать две монеты и определить, которая из них тяжелее.
Ответ обосновать.
Задача 13.
Задано N наборов монет из различных стран. Наборы упорядочены
по невозpастанию массы монет. В i-ом наборе a_i монет. Необходимо
за минимальное число взвешиваний на чашечных весах определить
к-тую по массе монету среди всех монет.
Задача 14.
Заданы массивы A[1..n] и B[1..n]. Необходимо найти такие ин-
дексы i_0 и j_0, , что
a + b = max (a + b ),
i_0 j_0 i j
где 1<=i<=n, 1<=j<=m , i<j.
Задача 15.
Мажорирующим элементом в массиве A[1..N] будем называть эле-
мент, встречающийся в массиве более N/2 раз. Легко заметить, что
в массиве может быть не более одного мажорирующего элемента. Нап-
ример, массив
3, 3, 4, 2, 4, 4, 2, 4, 4
имеет мажорирующий элемент 4, тогда как в массиве
3, 3, 4, 2, 4, 4, 2, 4
мажорирующего элемента нет.
Необходимо определить, есть ли в массиве мажорирующий элемент,
и если есть, то какой.
Задача 1.
Очевидное решение состоит в просмотре всего массива, что тре-
бует времени, пропорционального числу элементов массива. Однако
этот алгоритм не использует того факта, что массив A уже отсорти-
рован, и, вероятно, приведенное решение не является наилучшим.
Наилучший метод поиска состоит в том, чтобы проверить, явля-
ется ли x средним элементом массива A. Если да, то ответ получен.
Если x меньше среднего элемента, то мы можем применить тот же ме-
тод поиска к отсортированному подмассиву слева от среднего элемен-
та; аналогично, если x больше среднего элемента, то в дальнейшем
мы будем рассматривать правую половину массива.
Мы будем считать, что элемент A[0]=х; ответ возвращается в
переменной mid, а через low и high обозначаются, соответственно,
индексы начала и конца рассматриваемого подмассива. Цикл начина-
ется при high-low=n-1 и завершается при high-low>=-1. На каждой
итерации цикла величина high-low уменьшается по крайней мере вдвое
по сравнению с ее предыдущим значением; таким образом, цикл будет
проходиться не более [log2 (n-1)]+2 раз (тут через [] обозначается
целая часть числа, а log2 - это логарифм по основанию 2). Поэтому
говорят, что сложность вышеизложенного метода (который обычно на-
зывается методом дихотомии - т.е. "деления на два") О(log n). Об-
ратите внимание, что в выражение, стоящее в скобках после О не
входит ничего кроме переменной n - мы рассматриваем только зависи-
мость количества операций, которые необходимо выполнить, от длины
имеющегося массива.
Function BSearch(var A:input_array; x,n:integer): integer;
var low,high,mid: integer;
begin
A[0]:=x;
low:=1;
high:=n;
repeat
mid:=(low+high) div 2;
if low>high
then mid:=0
else if A[mid]<x
then low:=mid+1
else high:=mid-1;
until (A[mid]=x);
BSearch:=mid;
end;
Задача 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+а2+...+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 максимального просмотренного элемента из А;
- значение индексов i_0,j_0 для максимальной найденной суммы,
удовлетворяющей требуемому условию.
Замечание. На начальном этапе p=1, i_0=1, j_0=2.
При просмотре очередного i элемента из А определяется:
- максимальная сумма из А[i_0]+В[j_0], А[р]+В[i+1] или
А[i]+В[i+1] c пересчетом индексов i_0,j_0 для максимальной
найденной суммы;
- положение 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*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. Очевидно, что если 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. Следовательно, немажорирующих элементов, не
вошедших в пары сBовпадающих элементов 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