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

$\scriptstyle{\blacktriangleright}$ 4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого легкого из n камней?

Решение. Очевидный алгоритм с инвариантом << найден самый легкий камень среди первых i >> требует n-1 сравнений. Алгоритма меньшей сложности нет. Это вытекает из следующего более сильного утверждения. $\scriptstyle\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 4.5.2. Эксперт хочет убедить суд, что данный камень -- самый легкий среди n камней, сделав менее n-1 взвешиваний. Доказать, что это невозможно. (Веса камней неизвестны суду, но известны эксперту.)

Решение. Изобразим камни точками, а взвешивания -- линиями между ними. Получим граф с n вершинами и менее чем n-1 ребрами. Такой граф несвязен (добавление каждого следующего ребра уменьшает число компонент не более чем на 1 ). Поэтому суд ничего не знает относительно соотношения весов камней в двух связных компонентах и может допустить, что самый легкий камень -- в любой из них. $\scriptstyle\blacktriangleleft$

Разница между этой задачей и предыдущей: в этой задаче мы доказываем, что n-2 взвешиваний не достаточно не только для нахождения самого легкого, но даже для того, чтобы убедиться, что данный камень является самым легким -- если предположительный ответ известен. (В случае сортировки, зная предположительный ответ, мы можем убедиться в его правильности, сделав всего n-1 сравнений -- каждый сравниваем со следующим по весу.)

$\scriptstyle{\blacktriangleright}$ 4.5.3. Доказать, что можно найти самый легкий и самый тяжелый из 2n+1 камней (одновременно), сделав 3n взвешиваний.

[Указание. Для начала разобьем камни на пары (n пар, один камень остается непарным) и сравним камни внутри пар.] $\blacktriangleleft$

$\scriptstyle{\blacktriangleright}$ 4.5.4. Дано n различных по весу камней и число k (от 1 до n ). Требуется найти k -ый по весу камень, сделав не более Cn взвешиваний, где C -- некоторая константа, не зависящая от k и n .

Замечание. Сортировка позволяет сделать это за $Cn\log n$ взвешиваний. Указание к этой (трудной) задаче приведено в главе про рекурсию.

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

$\scriptstyle{\blacktriangleright}$ 4.5.5. Имеется n одинаковых на вид камней, некоторые из которых на самом деле различны по весу. Имеется прибор, позволяющий по двум камням определить, одинаковы они или различны (но не говорящий, какой тяжелее). Известно, что среди этих камней большинство (более n/2 ) одинаковых. Сделав не более n взвешиваний, найти хотя бы один камень из этого большинства. (Предостережение. Если два камня одинаковые, это не гарантирует их принадлежности к большинству.)

[Указание. Если найдены два различных камня, то их оба можно выбросить -- хотя бы один из них плохой и большинство останется большинством.] $\blacktriangleleft$

Решение. Программа просматривает камни по очереди, храня в переменной i число просмотренных камней. (Считаем камни пронумерованными от 1 до n.) Помимо этого программа хранит номер << текущего кандидата>> c и его << кратность>> k. Смысл этих названий объясняется инвариантом (И):

если к непросмотренным камням (с номерами ${\hbox{\tt i+1}}\ldots{\hbox{\tt 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, ее можно вынести наружу.

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

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

$\scriptstyle{\blacktriangleright}$ 4.5.6. Имеется квадратная таблица a[1..n,1..n]. Известно, что для некоторого i строка с номером i заполнена одними нулями, а столбец с номером i -- одними единицами (за исключением их пересечения на диагонали, где стоит неизвестно что). Найти такое i (оно, очевидно, единственно). Число действий порядка n. (Заметим, что это существенно меньше числа элементов в таблице).

[Указание. Рассмотрите a[i][j] как результат << сравнения>> i с j и вспомните, что самый тяжелый из n камней может быть найден за n сравнений. (Заметим, что таблица может не быть << транзитивной>>, но все равно при << сравнении>> двух элементов один из них отпадает.) ] $\blacktriangleleft$

pvv
1/8/1999