Глава 4. Сортировка.

 

     4.1. Квадратичные алгоритмы.

 

     4.1.1. Пусть a[1],  ...,  a[n]  -  целые  числа.  Требуется

построить  массив  b[1],  ..., b[n], содержащий те же числа, для

которых b[1] <= ... <= b[n].

     Замечание. Среди чисел a[1]...a[n] могут быть равные.  Тре-

буется,  чтобы  каждое целое число входило в b[1]...b[n] столько

же раз, сколько и в a[1]...a[n].

 

     Решение. Удобно считать, что числа a[1]..a[n] и  b[1]..b[n]

представляют собой начальное и конечное значения массива x. Тре-

бование  "a  и b содержат одни и те же числа" будет заведомо вы-

полнено, если в процессе работы  мы  ограничимся  перестановками

элементов x.

  ...

  k := 0;

  {k наименьших элементов массива x установлены на свои места}

  while k <> n do begin

  | s := k + 1; t := k + 1;

  | {x[s] - наименьший среди x[k+1]...x[t] }

  | while t<>n do begin

  | | t := t + 1;

  | | if x[t] < x[s] then begin

  | | | s := t;

  | | end;

  | end;

  | {x[s] - наименьший среди x[k+1]..x[n] }

  | ... переставить x[s] и x[k+1];

  | k := k + 1;

  end;

 

     4.1.2.  Дать другое решение задачи сортировки, использующее

инвариант {первые k элементов упорядочены: x[1] <= ... <= x[k]}

 

     Решение.

 

  k:=1

  {первые k элементов упорядочены}

  while k <> n do begin

  | {k+1-ый элемент продвигается к началу, пока не займет

  |   надлежащего места }

  | t := k+1;

  | {x[1] <= ... <= x[t-1] и x[t-1], x[t] <= ... <= x[k+1] }

  | while (t > 1) and (x[t] < x[t-1]) do begin

  | | ... поменять x[t-1] и x[t];

  | | t := t - 1;

  | end;

  end;

 

     Замечание. Дефект программы: при ложном выражении (t  >  1)

проверка x[t] < x[t-1] требует несуществующего значения x[0].

     Оба  предложенных решения требуют числа действий, пропорци-

онального n*n. Существуют более эффективные алгоритмы.

 

     4.2. Алгоритмы порядка n log n.

 

     4.2.1. Предложить алгоритм сортировки, число действий кото-

рого  было  бы  порядка  n  log  n,  то  есть не превосходило бы

C*n*log(n) для некоторого C и для всех n.

 

     Мы предложим два решения.

 

     Решение 1. (сортировка слиянием).

     Пусть  k  -  положительное  целое  число.  Разобьем  массив

x[1]..x[n]  на  отрезки  длины  k.  (Первый  - x[1]..x[k], затем

x[k+1]..x[2k] и т.д.) Последний отрезок будет неполным,  если  n

не  делится на k. Назовем массив k-упорядоченным, если каждый из

этих отрезков упорядочен. Любой массив 1-упорядочен. Если массив

k-упорядочен и n<=k, то он упорядочен.

     Мы  опишем,  как  преобразовать  k-упорядоченный  массив  в

2k-упорядоченный (из тех же элементов). С помощью этого преобра-

зования алгоритм записывается так:

 

  k:=1;

  {массив x является k-упорядоченным}

  while k < n do begin

  | .. преобразовать k-упорядоченный массив в 2k-упорядоченный;

  | k := 2 * k;

  end;

 

     Требуемое  преобразование  состоит в том,что мы многократно

"сливаем" два упорядоченных отрезка длины не  больше  k  в  один

упорядоченный  отрезок. Пусть процедура слияние (p,q,r: integer)

при p <=q <= r сливает отрезки  x[p+1]..x[q]  и  x[q+1]..x[r]  в

упорядоченный  отрезок x[p+1]..x[r] (не затрагивая других частей

массива x).

                  p               q               r

            -------|---------------|---------------|-------

                   | упорядоченный | упорядоченный |

            -------|---------------|---------------|-------

                                  |

                                  |

                                  V

            -------|-------------------------------|-------

                   |     упорядоченный             |

            -------|-------------------------------|-------

 

Тогда преобразование k-упорядоченного массива в 2k-упорядоченный

осуществляется так:

 

  t:=0;

  {t кратно 2k или t = n, x[1]..x[t] является

   2k-упорядоченным; остаток массива x не изменился}

  while t + k < n do begin

  | p := t;

  | q := t+k;

  | ...r := min (t+2*k, n); {в паскале нет функции min }

  | слияние (p,q,r);

  | t := r;

  end;

 

Слияние требует вспомогательного массива для записи  результатов

слияния  -  обозначим его b. Через p0 и q0 обозначим номера пос-

ледних элементов участков, подвергшихся слиянию, s0 -  последний

записанный  в  массив b элемент. На каждом шаге слияния произво-

дится одно из двух действий:

 

        b[s0+1]:=x[p0+1];

        p0:=p0+1;

        s0:=s0+1;

или

        b[s0+1]:=x[q0+1];

        q0:=q0+1;

        s0:=s0+1;

 

Первое действие (взятие элемента из первого отрезка) может  про-

изводиться при двух условиях:

    (1) первый отрезок не кончился (p0 < q);

    (2) второй отрезок кончился (q0 = r)  или  не  кончился,  но

элемент в нем не меньше [(q0 < r) и (x[p0+1] <= x[q0+1])].

     Аналогично для второго действия. Итак, получаем

 

  p0 := p; q0 := q; s0 := p;

  while (p0 <> q) or (q0 <> r) do begin

  | if (p0 < q) and ((q0 = r) or ((q0 < r) and

  | |                (x[p0+1] <= x[q0+1]))) then begin

  | | b [s0+1] := x [p0+1];

  | | p0 := p0+1;

  | | s0 := s0+1;

  | end else begin

  | | {(q0 < r) and ((p0 = q) or ((p0<q) and

  | |   (x[p0+1] >= x[q0+1])))}

  | | b [s0+1] := x [q0+1];

  | | q0 := q0 + 1;

  | | s0 := s0 + 1;

  | end;

  end;

 

(Если оба отрезка не кончены и первые невыбранные элементы в них

равны, то допустимы оба действия; в программе выбрано первое.)

     Программа  имеет  привычный дефект: обращение к несуществу-

ющим элементам массива при вычислении булевских выражений.

 

     Решение 2 (сортировка деревом).

     Нарисуем "полное двоичное дерево"  -  картинку,  в  которой

снизу один кружок, из него выходят стрелки в два других, из каж-

дого - в два других и так далее:

 

               .............

                 o  o o  o

                  \/   \/

                   o   o

                    \ /

                     o

 

 

     Будем  говорить, что стрелки ведут "от отцов к сыновьям": у

каждого кружка два сына и один отец (если  кружок  не  верхний).

Предположим  для  простоты, что количество подлежащих сортировке

чисел есть степень двойки, и они могут заполнить один  из  рядов

целиком. Запишем их туда. Затем заполним часть дерева под ним по

правилу:

   число в кружке = минимум из чисел в кружках-сыновьях

Тем  самым  в  корне дерева (нижнем кружке) будет записано мини-

мальное число во всем массиве.

     Изымем из сортируемого  массива  минимальный  элемент.  Для

этого  его  надо вначале найти. Это можно сделать, идя от корня:

от отца переходим к тому сыну, где записано то же  число.  Изъяв

минимальный  элемент,  заменим  его  символом  "бесконечность" и

скорректируем более низкие ярусы (для этого  надо  снова  пройти

путь к корню). При этом считаем, что минимум из n и бесконечнос-

ти  равен  n. Тогда в корне появится второй по величине элемент,

мы изымаем его, заменяя бесконечностью и корректируя дерево. Так

постепенно мы изымем все элементы в порядке возрастания, пока  в

корне не останется бесконечность.

     При записи этого алгоритма полезно нумеровать кружочки чис-

лами 1, 2, ...: сыновьями кружка номер n являются кружки  2*n  и

2*n+1. Подробное изложение этого алгоритма мы опустим, поскольку

мы  изложим  более  эффективный  вариант,  не требующий дополни-

тельной памяти, кроме конечного числа переменных (в дополнении к

сортируемому массиву).

     Мы будем записывать сортируемые числа во всех вершинах  де-

рева,  а не только на верхнем уровне. Пусть x[1]..x[n] - массив,

подлежащий сортировке. Вершинами дерева будут числа от 1 до n; о

числе x[i] мы будем говорить как о числе, стоящем в вершине i. В

процессе сортировки количество вершин дерева будет  сокращаться.

Число вершин текущего дерева будем хранить в переменной k. Таким

образом,  в  процессе работы алгоритма массив x[1]..x[n] делится

на две части: в x[1]..x[k] хранятся числа на дереве, а в  x[k+1]

.. x[n] хранится уже отсортированная в порядке возрастания часть

массива - элементы, уже занявшие свое законное место.

     На каждом шаге алгоритм будет изымать максимальный  элемент

дерева и помещать его в отсортированную часть, на освободившееся

в результате сокращения дерева место.

     Договоримся о терминологии. Вершинами дерева считаются чис-

ла от 1 до текущего значения переменной k. У  каждой  вершины  s

могут  быть  сыновья 2s и 2s+1. Если оба этих числа больше k, то

сыновей нет; такая вершина называется листом. Если 2s=k, то вер-

шина s имеет ровно одного сына (2s).

     Для каждого s из 1..k рассмотрим "поддерево" с корнем в  s:

оно  содержит вершину s и всех ее потомков (сыновей, сыновей сы-

новей и т.д. - до тех пор, пока мы не выйдем из  отрезка  1..k).

Вершину  s будем называть регулярной, если стоящее в ней число -

максимальный элемент s-поддерева; s-поддерево  назовем  регуляр-

ным,  если  все  его вершины регулярны. (В частности, любой лист

образует регулярное одноэлементное поддерево.)

 

     Схема алгоритма такова:

 

  k:= n

  ... Сделать 1-поддерево регулярным;

  {x[1],..,x[k] <= x[k+1] <= ... <= x[n]; 1-поддерево регулярно,

   в частности, x[1] - максимальный элемент среди x[1]..x[k]}

  while k <> 1 do begin

  | ... обменять местами x[1] и x[k];

  | k := k - 1;

  | {x[1]..x[k-1] <= x[k] <=...<= x[n]; 1-поддерево регу-

  |   лярно везде, кроме, возможно, самого корня }

  | ... восстановить регулярность 1-поддерева всюду

  end;

 

В качестве вспомогательной процедуры нам  понадобится  процедура

восстановления регулярности s-поддерева в корне. Вот она:

 

  {s-поддерево регулярно везде, кроме, возможно, корня}

  t := s;

  {s-поддерево регулярно везде, кроме, возможно, вершины t}

  while ((2*t+1 <= k) and (x[2*t+1] > x[t])) or

  |     ((2*t <= k) and (x[2*t] > x[t])) do begin

  | if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin

  | | ... обменять x[t] и x[2*t+1];

  | | t := 2*t + 1;

  | end else begin

  | | ... обменять x[t] и x[2*t];

  | | t := 2*t;

  | end;

  end;

 

     Чтобы убедиться в правильности этой процедуры, посмотрим на

нее повнимательнее. Пусть в s-поддереве все вершины, кроме разве

что вершины t, регулярны. Рассмотрим сыновей вершины t. Они  ре-

гулярны, и потому содержат наибольшие числа в своих поддеревьях.

Таким  образом,  на  роль  наибольшего числа в t-поддереве могут

претендовать число в самой вершине t и числа в  ее  сыновьях. (В

первом случае вершина t регулярна, и все в порядке.) В этих тер-

минах цикл можно записать так:

 

  while наибольшее число не в t, а в одном из сыновей do begin

  | if оно в правом сыне then begin

  | | поменять t с ее правым сыном; t:= правый сын

  | end else begin {наибольшее число - в левом сыне}

  | | поменять t с ее левым сыном; t:= левый сын

  | end

  end

 

После  обмена  вершина  t  становится регулярной (в нее попадает

максимальное число t-поддерева). Не принявший участия  в  обмене

сын остается регулярным, а принявший участие может и не быть ре-

гулярным. В остальных вершинах s-поддерева не изменились ни чис-

ла,  ни поддеревья их потомков (разве что два элемента поддерева

переставились), так что регуярность не нарушилась.

 

   Эта же процедура может использоваться для того, чтобы сделать

1-поддерево регулярным на начальной стадии сортировки:

 

  k := n;

  u := n;

  {все s-поддеревья с s>u регулярны }

  while u<>0 do begin

  | {u-поддерево регулярно везде, кроме разве что корня}

  | ... восстановить регулярность u-поддерева в корне;

  | u:=u-1;

  end;

 

     Теперь запишем процедуру сортировки на паскале  (предпола-

гая,  что  n  -  константа,  x  имеет тип arr = array [1..n] of

integer).

 

  procedure sort (var x: arr);

  | var u, k: integer;

  | procedure exchange(i, j: integer);

  | | var tmp: integer;

  | | begin

  | | tmp  := x[i];

  | | x[i] := x[j];

  | | x[j] := tmp;

  | end;

  | procedure restore (s: integer);

  | | var t: integer;

  | | begin

  | | t:=s;

  | | while ((2*t+1 <= k) and (x[2*t+1] > x[t]) ) or

  | | |     ((2*t <= k) and (x[2*t] > x[t])) do begin

  | | | if (2*t+1 <= k) and (x[2*t+1] >= x[2*t]) then begin

  | | | | exchange (t, 2*t+1);

  | | | | t := 2*t+1;

  | | | end else begin

  | | | | exchange (t, 2*t);

  | | | | t := 2*t;

  | | | end;

  | | end;

  | end;

  begin

  | k:=n;

  | u:=n;

  | while u <> 0 do begin

  | | restore (u);

  | | u := u - 1;

  | end;

  | while k <> 1 do begin

  | | exchange (1, k);

  | | k := k - 1;

  | | restore (1);

  | end;

  end;

 

     Несколько замечаний.

 

     Метод, использованный при сортировке деревом, бывает полез-

ным в других случах. (См. в главе 6 (о типах данных)  раздел  об

очереди с приоритетами.)

 

     Сортировка слиянием хороша тем, что она на  требует,  чтобы

весь  сортируемый  массив  помещался в оперативной памяти. Можно

сначала отсортировать такие куски, которые помещаются  в  памяти

(например, с помощью дерева), а затем сливать полученные файлы.

 

     Еще один практически важный алгоритм сортировки таков: что-

бы  отсортировать массив, выберем случайный его элемент b, и ра-

зобъем массив на три части: меньшие b, равные  b  и  большие  b.

(Эта  задача  приведена в главе о массивах.) Теперь осталось от-

сортировать первую и третью части: это делается тем же способом.

Время работы этого алгоритма - случайная величина;  можно  дока-

зать, что в среднем он работает не больше C*n*log n. На практике

- он один из самых быстрых. (Мы еще вернемся к нему, приведя его

рекурсивную и нерекурсивную реализации.)

 

     Наконец, отметим, что сортировка за время порядка C*n*log n

может быть выполнена с помощью техники сбалансированных деревьев

(см.  главу  12), однако программы тут сложнее и константа C до-

вольно велика.

 

     4.3. Применения сортировки.

 

     4.3.1. Найти количество  различных  чисел  среди  элементов

данного массива. Число действий порядка n*log n. (Эта задача уже

была в главе о массивах.)

 

     Решение. Отсортировать числа, а затем посчитать  количество

различных, просматривая элементы массива по порядку.

 

     4.3.2. Дано n отрезков [a[i],  b[i]]  на  прямой  (i=1..n).

Найти максимальное k, для которого существует точка прямой, пок-

рытая k отрезками ("максимальное число слоев"). Число действий -

порядка n*log n.

 

     Решение. Упорядочим все левые и правые концы отрезков вмес-

те  (при этом левый конец считается меньше правого конца, распо-

ложеннного в той же точке прямой). Далее двигаемся слева  напра-

во,  считая  число  слоев.  Встреченный левый конец увеличивает

число  слоев  на 1, правый - уменьшает. Отметим, что примыкающие

друг к другу отрезки обрабатываются правильно: сначала идет  ле-

вый конец (правого отрезка), а затем - правый (левого отрезка).

 

     4.3.3. Дано n точек на плоскости. Указать (n-1)-звенную не-

самопересекающуюся незамкнутую ломаную, проходящую через все эти

точки.  (Соседним  отрезкам  ломаной разрешается лежать на одной

прямой.) Число действий порядка n*log n.

 

     Решение. Упорядочим точки по  x-координате,  а  при  равных

x-координатах  - по y-координате. В таком порядке и можно прово-

дить ломаную.

 

     4.3.4. Та же задача, если ломаная должна быть замкнутой.

 

     Решение. Возьмем самую левую точку (т.е. точку с наименьшей

x-координатой) и проведем из нее лучи во  все  остальные  точки.

Теперь упорядочим эти лучи, а точки на одном луче поместим в по-

рядке увеличения расстояния от начала луча.

 

     4.3.5. Дано n точек на  плоскости.  Построить  их  выпуклую

оболочку  -  минимальную  выпуклую фигуру, их содержащую. (Форму

выпуклой оболочки примет резиновое колечко, если его натянуть на

гвозди, вбитые в точках.)  Число операций не более n*log n.

 

    Указание. Упорядочим точки - годится любой из порядков,  ис-

пользованных в двух предыдущих задачах. Затем, рассматривая точ-

ки по очереди, будем строить выпуклую оболочку уже рассмотренных

точек. (Для хранения выпуклой оболочки полезно использовать дек,

см. главу 6 о типах данных.)

 

 

     4.4. Нижние оценки для числа сравнений при сортировке.

 

     Пусть  имеется  n  различных по весу камней и весы, которые

позволяют за одно взвешивание определить, какой из двух  выбран-

ных  нами  камней тяжелее. (В программистских терминах: мы имеем

доступ к функции  тяжелее(i,j:1..n):boolean.)  Надо  упорядочить

камни  по  весу,  сделав  как  можно меньше взвешиваний (вызовов

функции "тяжелее").

 

    Разумеется, число взвешиваний зависит не только от выбранно-

го  нами алгоритма, но и от того, как оказались расположены кам-

ни. Сложностью алгоритма назовем число взвешиваний при наихудшем

расположении камней.

 

    4.4.1. Доказать, что сложность любого алгоритма сортировки n

камней не меньше log (n!). (Логарифм берется по основанию 2,  n!

- произведение чисел 1..n.)

 

     Решение. Пусть имеется алгоритм сложности не более  d.  Для

каждого  из n! возможных расположений камней запротоколируем ре-

зультаты взвешиваний (обращений к функции "тяжелее");  их  можно

записать  в  виде  последовательности  из не более чем d нулей и

единиц. Для  единообразия  дополним  последовательность  нулями,

чтобы ее длина стала равной d. Тем самым у нас имеется n! после-

довательностей  из  d нулей и единиц. Все эти последовательности

разные - иначе наш алгоритм дал бы одинаковые ответы для  разных

порядков  (и один из ответов был бы неправильным). Получаем, что

2 в степени d не меньше n! - что и требовалось доказать.

 

     Другой способ объяснить то же самое  -  рассмотреть  дерево

вариантов,  возникающее в ходе выполнения алгоритма, и сослаться

на то, что дерево высоты d не может иметь более (2 в степени  d)

листьев.

 

     Это  рассуждение показывает, что любой алгоритм сортировки,

использующий только сравнения элементов массива и их перестанов-

ки, требует не менее C*n*log n действий, так что наши  алгоритмы

близки  к  оптимальным. Однако алгоритм сортировки, использующий

другие операции, может действовать быстрее. Вот один  из  приме-

ров.

 

     4.4.2. Имеется массив целых чисел  a[1]..a[n],  причем  все

числа неотрицательны и не превосходят m. Отсортировать этот мас-

сив; число действий порядка m+n.

 

     Решение.  Для каждого числа от 0 до m подсчитываем, сколько

раз оно встречается в массиве. После этого исходный массив можно

стереть и заполнить заново в порядке возрастания, используя све-

дения о кратности каждого числа.

 

Отметим также, что этот алгоритм не переставляет числа в  масси-

ве, как большинство других, а "записывает их туда заново".

 

Есть также метод сортировки, в котором последовательно проводится

ряд  "частичных  сортировок"  по отдельным битам. Начнём с такой

задачи:

 

     4.4.3. В массиве a[1]..a[n] целых чисел переставить элемен-

ты так, чтобы чётные шли перед нечётными (не меняя взаимный  по-

рядок в каждой из групп).

 

     Решение.  Сначала  спишем  (во  вспомогательный массив) все

чётные, а потом - все нечётные.

 

     4.4.4. Имеется массив из n чисел от 0 до (2 в степени k)  -

1, каждое из которых мы будем рассматривать как k-битовое слово.

Используя проверки "i-ый бит равен 0" и "i-ый бит равен 1" вмес-

то сравнений, отсортировать все числа за время порядка n*k.

 

     Решение. Отсортируем числа по последнему биту (см. предыду-

щую  задачу),  затем по предпоследнему и так далее. В результате

они будут отсортированы. В самом деле, индукцией по i легко  до-

казать, что после i шагов любые два числа, отличающиеся только в

i последних битах, идут в правильном порядке.  (Вариант: после i

шагов i-битовые концы чисел идут в правильном порядке.)

 

     Аналогичный алгоритм может быть применен для m-ичной систе-

мы  счисления  вместо двоичной. При этом полезна такая вспомога-

тельная задача:

 

     4.4.5. Даны n чисел и функция f, принимающая (на них)  зна-

чения  1..m.  Требуется переставить числа в таком порядке, чтобы

значения функции f не убывали (сохраняя  притом  порядок  внутри

каждой из групп). Число действий порядка m+n.

     Указание. Завести m списков суммарной длины n (как это сде-

лать,  смотри в главе 6 о типах данных) и помещать в i-ый список

числа, для которых значение функции f равно i.  Вариант:  посчи-

тать  для  всех  i, сколько имеется чисел x c f(x)=i, после чего

легко определить, с какого места нужно начинать размещать  числа

с f(x)=i.

 

     4.5. Родственные сортировке задачи.

 

     4.5.1. Какова минимально возможная сложность (число сравне-

ний  в наихудшем случае) алгоритма отыскания самого легкого из n

камней?

 

     Решение. Очевидный алгоритм  с  инвариантом  "найден  самый

легкий  камень  среди первых i" требует n-1 сравнений. Алгоритма

меньшей сложности нет. Это вытекает из следующего более сильного

утверждения.

 

     4.5.2. Эксперт хочет докать суду, что данный камень - самый

легкий среди n камней, сделав менее n-1  взвешиваний.  Доказать,

что  это  невозможно.  (Веса камней неизвестны суду, но известны

эксперту.)

 

     Решение. Изобразим камни точками, а взвешивания  -  линиями

между  ними. Получим граф с n вершинами и менее чем n-1 ребрами.

Такой  граф  несвязен  (добавление  каждого   следующего   ребра

уменьшает число компонент не более чем на 1). Поэтому суд ничего

не  знает  относительно  соотношения весов камней в двух связных

компонентах и может допустить, что самый легкий камень - в любой

из них.

 

     Разница  между  этой  задачей  и  предыдущей в том, что n-1

взвешиваний не достаточно не только для нахождения самого легко-

го, но даже для того, чтобы убедиться, что данный камень являет-

ся самым легким - если предположительный ответ известен. (В слу-

чае сортировки, зная предположительный ответ, мы можем убедиться

в его правильности, сделав всего n-1 сравнений: каждый сравнива-

ем со слеследующим по весу.)

 

     4.5.3. Дано n различных по весу камней и число k (от  1  до

n). Требуется найти k-ый по весу камень,  сделав  не  более  C*n

взвешиваний, где C - некоторая константа, не зависящая от k.

 

     Замечание.  Сортировка  позволяет  сделать это за C*n*log n

взвешиваний. Указание к этой (трудной) задаче приведено в  главе

про рекурсию.

 

     Следующая задача имеет неожиданно простое решение.

 

     4.5.4. Имеется n одинаковых на вид камней, некоторые из ко-

торых на самом деле различны по весу. Имеется  прибор,  позволя-

ющий  по  двум камням определить, одинаковы они или различны (но

не говорящий, какой тяжелее). Известно, что  среди  этих  камней

большинство  (более n/2) одинаковых. Сделав не более n взвешива-

ний, найти хотя бы один камень из этого большинства.

 

     Предостережение. Если два камня одинаковые, это не гаранти-

рует их принадлежности к большинству.

 

     Указание. Если найдены два различных камня, то их оба можно

выбросить - хотя бы один из них плохой и  большинство  останется

большинством.

 

     Решение. Программа просматривает камни по очереди, храня  в

переменной i число просмотренных камней. (Считаем камни пронуме-

рованными от 1 до n.) Помимо этого программа хранит номер "теку-

щего  кандидата"  c  и  его  "кратность"  k. Смысл этих названий

объясняется инвариантом:

 

   если к непросмотренным камням (с номерами i+1..n)  до-

   бавили бы k копий c-го камня, то наиболее частым среди  (И)

   них был бы такой же камень, что и для исходного массива

 

Получаем такую программу:

 

   k:=0; i:=0

   {(И)}

   while i<>n do begin

   | if k=0 then begin

   | | k:=1; c:=i+1; i:=i+1;

   | end else if i+1-ый камень одинаков с c-ым then begin

   | | i:=i+1; k:=k+1;

   | |  {заменяем материальный камень идеальным}

   | end else begin

   | | i:=i+1; k:=k-1;

   | |  {выкидываем один материальный и один идеальный камень}

   | end;

   end;

   искомым является c-ый камень

 

Замечание.  Поскольку во всех трех вариантах выбора стоит

команда i:=i+1, ее можно вынести наружу.

 

     Следующая задача не имеет на первый взгляд никакого отноше-

ния к сортировке.

 

     4.5.5.  Имеется квадратная таблица a[1..n, 1..n]. Известно,

что для некоторого i строка с номером i заполнена одними нулями,

а столбец с номером i - одними единицами (за исключением их  пе-

ресечения на диагонали, где стоит неизвестно что). Найти такое i

(оно, очевидно, единственно). Число действий не превосходит C*n.

(Заметим, что это существенно меньше числа элементов в таблице).

 

     Указание. Рассмотрите a[i][j] как результат "сравнения" i с

j  и  вспомните, что самый тяжелый из n камней может быть найден

за n сравнений. (Не забудьте, впрочем, что таблица может не быть

"транзитивной".)

Hosted by uCoz