Жанр: Учеба
Программирование в теоремах и задачах
...(state = WL) and not есть_сверху then begin
| | обработать; state := WLU;
| end else if (state = WLU) and есть_справа then begin
| | вправо; state := WL;
| end else begin {state = WLU, not есть_справа, есть_снизу}
| | вниз;
| end;
end;
Решение. Инвариант цикла:
state = WL =" ОЛ
state = WLU =" ОЛН
Доказательство завершения работы: переход из состояния ОЛ в ОЛН
возможен только при обработке вершины, поэтому если программа
работает бесконечно, то с некоторого момента значение state не
меняется, что невозможно.
3.1.4. Решить задачу об обходе дерева, если мы хотим, чтобы
обрабатывались все вершины (не только листья).
Решение. Пусть x - некоторая вершина. Тогда любая вершина y
относится к одной из четырех категорий. Рассмотрим путь из корня
в y. Он может:
(а) быть частью пути из корня в x (y ниже x);
(б) свернуть налево с пути в x (y левее x);
(в) пройти через x (y над x);
(г) свернуть направо с пути в x (y правее x);
В частности, сама вершина x относится к категории (в). Условия
теперь будут такими:
(ОНЛ) обработаны все вершины ниже и левее;
(ОНЛН) обработаны все вершины ниже, левее и над.
Вот как будет выглядеть программа:
procedure вверх_до_упора_и_обработать
| {дано: (ОНЛ), надо: (ОНЛН)}
begin
| {инвариант: ОНЛ}
| while есть_сверху do begin
| | обработать
| | вверх_налево
| end
| {ОНЛ, Робот в листе}
| обработать;
| {ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
| if есть_справа then begin {ОНЛН, есть справа}
| | вправо;
| | {ОНЛ}
| | вверх_до_упора_и_обработать;
| end else begin
| | {ОЛН, не есть_справа, есть_снизу}
| | вниз;
| end;
end;
{ОНЛН, Робот в корне =" все вершины обработаны}
3.1.5. Приведенная только что программа обрабатывает вершину
до того, как обработан любой из ее потомков. Как изменить ее,
чтобы каждая вершина, не являющаяся листом, обрабатывалась дважды:
один раз до, а другой раз после всех своих потомков? (Листья
по-прежнему обрабатываются по разу.)
Решение. Под "обработано ниже и левее" будем понимать "ниже
обработано по разу, слева обработано полностью (листья по разу,
останые по два)". Под "обработано ниже, левее и над" будем понимать
"ниже обработано по разу, левее и над - полностью".
Программа будет такой:
procedure вверх_до_упора_и_обработать
| {дано: (ОНЛ), надо: (ОНЛН)}
begin
| {инвариант: ОНЛ}
| while есть_сверху do begin
| | обработать
| | вверх_налево
| end
| {ОНЛ, Робот в листе}
| обработать;
| {ОНЛН}
end;
Основной алгоритм:
дано: Робот в корне, ничего не обработано
надо: Робот в корне, все вершины обработаны
{ОНЛ}
вверх_до_упора_и_обработать
{инвариант: ОНЛН}
while есть_снизу do begin
| if есть_справа then begin {ОНЛН, есть справа}
| | вправо;
| | {ОНЛ}
| | вверх_до_упора_и_обработать;
| end else begin
| | {ОЛН, не есть_справа, есть_снизу}
| | вниз;
| | обработать;
| end;
end;
{ОНЛН, Робот в корне =" все вершины обработаны полностью}
3.1.6. Доказать, что число операций в этой программе по порядку
равно числу вершин дерева. (Как и в других программах, которые
отличаются от этой лишь пропуском некоторых команд "обработать".)
Указание. Примерно каждое второе действие при исполнении
этой программы - обработка вершины, а каждая вершина обрабатывается
максимум дважды.
Теперь реализуем операции с деревом позиций. Позицию будем
представлять с помощью переменной k: 0..n (число ферзей) и массива
c: array [1..n] of 1..n (c [i] - координаты ферзя на i-ой
горизонтали; при i " k значение c [i] роли не играет). Предполагается,
что все позиции допустимы (если убрать верхнего ферзя,
остальные не бьют друг друга).
program queens;
| const n = ...;
| var
| k: 0..n;
| c: array [1..n] of 1..n;
|
| procedure begin_work; {начать работу}
| begin
| | k := 0;
| end;
|
| function danger: boolean; {верхний ферзь под боем}
| | var b: boolean; i: integer;
| begin
| | if k "= 1 then begin
| | | danger := false;
| | end else begin
| | | b := false; i := 1;
| | | {b "=" верхний ферзь под боем ферзей с номерами " i}
| | | while i "" k do begin
| | | | b := b or (c[i]=c[k]) {вертикаль}
| | | | or (abs(c[[i]-c[k]))=abs(i-k)); {диагональ}
| | | | i := i+ 1;
| | | end;
| | | danger := b;
| | end;
| end;
|
| function is_up: boolean {есть_сверху}
| begin
| | is_up := (k " n) and not danger;
| end;
|
| function is_right: boolean {есть_справа}
| begin
| | is_right := (k " 0) and (c[k] " n);
| end;
| {возможна ошибка: при k=0 не определено c[k]}
|
| function is_down: boolean {есть_снизу}
| begin
| | is_up := (k " 0);
| end;
|
| procedure up; {вверх_налево}
| begin {k " n}
| | k := k + 1;
| | c [k] := 1;
| end;
|
| procedure right; {вправо}
| begin {k " 0, c[k] " n}
| | c [k] := c [k] + 1;
| end;
|
| procedure down; {вниз}
| begin {k " 0}
| | k := k - 1;
| end;
|
| procedure work; {обработать}
| | var i: integer;
| begin
| | if (k = n) and not danger then begin
| | | for i := 1 to n do begin
| | | | write ('"', i, ',' , c[i], '" ');
| | | end;
| | | writeln;
| | end;
| end;
|
| procedure UW; {вверх_до_упора_и_обработать}
| begin
| | while is_up do begin
| | | up;
| | end
| | work;
| end;
|
begin
| begin_work;
| UW;
| while is_down do begin
| | if is_right then begin
| | | right;
| | | UW;
| | end else begin
| | | down;
| | end;
| end;
end.
3.1.7. Приведенная программа тратит довольно много времени
на выполнение проверки есть_сверху (проверка, находится ли
верхний ферзь под боем, требует числа действий порядка n). Изменить
реализацию операций с деревом позиций так, чтобы все три
проверки есть_сверху/справа/снизу и соответствующие команды требовали
бы количества действий, ограниченного не зависящей от n
константой.
Решение. Для каждой вертикали, каждой восходящей и каждой
нисходящей диагонали будем хранить булевское значение - сведения
о том, находится ли на этой линии ферзь (верхний ферзь не учитывается).
(Заметим, что в силу допустимости позиции на каждой из
линий может быть не более одного ферзя.).
3.2. Обход дерева в других задачах.
3.2.1. Использовать метод обхода дерева для решения следующей
задачи: дан массив из n целых положительных чисел
a[1]..a[n] и число s; требуется узнать, может ли число s быть
представлено как сумма некоторых из чисел массива a. (Каждое
число можно использовать не более чем по одному разу.)
Решение. Будем задавать k-позицию последовательностью из k
булевских значений, определяющих, входят ли в сумму числа
a[1]..a[k] или не входят. Позиция допустима, если ее сумма не
превосходит s.
Замечание. По сравнению с полным перебором всех (2 в степени
n) подмножеств тут есть некоторый выигрыш. Можно также предварительно
отсортировать массив a в убывающем порядке, а также
считать недопустимыми те позиции, в которых сумма отброшенных
членов больше, чем разность суммы всех членов и s. Последний
приём называют "методом ветвей и границ". Но принципиального
улучшения по сравнению с полным перебором тут не получается (эта
задача, как говорят, NP-полна, см. подробности в книге Ахо,
Хопкрофта и Ульмана "Построение и анализ вычислительных алгоритмов").
Традиционное название этой задачи - "задача о рюкзаке"
(рюкзак общей грузоподъемностью s нужно упаковать под завязку,
располагая предметами веса a[1]..a[n]). См. также в главе 7
(раздел о динамическом программировании) алгоритм её решения,
полиномиальный по n+s.
3.2.2. Перечислить все последовательности из n нулей, единиц
и двоек, в которых никакая группа цифр не повторяется два
раза подряд (нет куска вида XX).
3.2.3. Аналогичная задача для последовательностей нулей и
единиц, в которых никакая группа цифр не повторяется три раза
подряд (нет куска вида XXX).
К этой же категории относятся задачи типа "можно ли сложить
данную фигуру из пентамино" и им подобные. В них важно умелое
сокращение перебора (вовремя распознать, что имеющееся расположение
фигурок уже противоречит требованиям, и по этой ветви поиск
не продолжать).
Глава 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 подсчитываем, сколько
раз оно встречается в массиве. После этого исх
...Закладка в соц.сетях
