| | значения diff}
| | while (d <> 0) and ..стек непуст do begin {d = 1}
| | | ..взять из стека пару в
| | | if direct = l then begin
| | | | if diff [v] = 1 then begin
| | | | | c := 0;
| | | | end else begin
| | | | | c := 1;
| | | | end;
| | | | diff [v] := diff [v] - 1;
| | | end else begin {direct = r}
| | | | if diff [v] = -1 then begin
| | | | | c := 0;
| | | | end else begin
| | | | | c := 1;
| | | | end;
| | | | diff [v] := diff [v] + 1;
| | | end;
| | | {c = изменение высоты поддерева с корнем в v по сравне-
| | | нию с исходным деревом; массив diff содержит правиль-
| | | ные значения для этого поддерева; возможно нарушение
| | | сбалансированности в v}
| | | balance (v, d1); d := c + d1;
| | end;
| end;
end;
Легко проверить, что значение d может быть равно только 0 или 1
(но не -1): если c = 0, то diff [v] = 0 и балансировка не произ-
водится.
Программа удаления строится аналогично. Ее основной фраг-
мент таков:
{инвариант: стек содержит путь к изменившемуся поддереву,
высота которого изменилась по сравнению с высотой в
исходном дереве на d (=0 или -1); это поддерево
сбалансировано; значения diff для его вершин правильны;
в остальном дереве все осталось как было -
в частности, значения diff}
while (d <> 0) and ..стек непуст do begin
| {d = -1}
| ..взять из стека пару в
| if direct = l then begin
| | if diff [v] = -1 then begin
| | | c := -1;
| | end else begin
| | | c := 0;
| | end;
| | diff [v] := diff [v] + 1;
| end else begin {direct = r}
| | if diff [v] = 1 then begin
| | | c := -1;
| | end else begin
| | | c := 0;
| | end;
| | diff [v] := diff [v] - 1;
| end;
| {c = изменение высоты поддерева с корнем в v по срав-
| нению с исходным деревом; массив diff содержит
| правильные значения для этого поддерева;
| возможно нарушение сбалансированности в v}
| balance (v, d1);
| d := c + d1;
end;
Легко проверить, что значение d может быть равно только 0 или -1
(но не -2): если c = -1, то diff [v] = 0 и балансировка не про-
изводится.
Отметим также, что наличие стека делает излишними перемен-
ные father и direction (их роль теперь играет вершина стека).
12.2.6. Доказать, что при добавлении элемента
(а) второй из трех случаев балансировки (см. рисунок выше)
невозможен;
(б) полная балансировка требует не более одного вращения
(после чего все дерево становится сбалансированным),
в то время как при удалении элемента может понадобиться
много вращений.
Замечание. Мы старались записать программы добавления и
удаления так, чтобы они были как можно более похожими друг на
друга. Используя специфику каждой из них, можно многое упрос-
тить.
Существуют и другие способы представления множеств, гаран-
тирующие число действий порядка log n на каждую операцию. Опишем
один из них (называемый Б-деревьями).
До сих пор каждая вершина содержала один элемент хранимого
множества. Этот элемент служил границей между левым и правым
поддеревом. Будем теперь хранить в вершине k >= 1 элементов мно-
жества (число k может меняться от вершины к вершине, а также при
добавлении и удалении новых элементов, см. далее). Эти k элемен-
тов служат разделителями для k+1 поддерева. Пусть фиксировано
некоторое число n >= 1. Будем рассматривать деревья, обладающие
такими свойствами:
(1) Каждая вершина содержит от n до 2n элементов (за исклю-
чением корня, который может содержать любое число элементов от 0
до 2n).
(2) Вершина с k элементами либо имеет k+1 сына, либо не
имеет сыновей вообще (такие вершины называются листьями).
(3) Все листья находятся на одной и той же высоте.
Добавление элемента происходит так. Если лист, в который он
попадает, неполон (т.е. содержит менее 2n элементов), то нет
проблем. Если он полон, то 2n+1 элемент (все элементы листа и
новый элемент) разбиваем на два листа по n элементов и разделя-
ющий их серединный элемент. Этот серединный элемент надо доба-
вить в вершину предыдущего уровня. Это возможно, если в ней ме-
нее 2n элементов. Если и она полна, то ее разбивают на две, вы-
деляют серединный элемент и т.д. Если в конце концов мы захотим
добавить элемент в корень, а он окажется полным, то корень рас-
щепляется на две вершины, а высота дерева увеличивается на 1.
Удаление элемента. Удаление элемента, находящемся не в лис-
те, сводится к удалению непосредственно следующего за ним, кото-
рый находится в листе. Поэтому достаточно научиться удалять эле-
мент из листа. Если лист при этом становится неполным, то его
можно пополнить за счет соседнего листа - если только и он не
имеет минимально возможный размер n. Если же оба листа имеют
размер n, то на них вместе 2n элементов, вместе с разделителем -
2n+1. После удаления одного элемента остается 2n элементов - как
раз на один лист. Если при этом вершина предыдущего уровня ста-
новится меньше нормы, процесс повторяется и т.д.
12.2.7. Реализовать описанную схему хранения множеств, убе-
дившись, что она также позволяет обойтись C*log(n) действий для
операций включения, исключения и проверки принадлежности.
12.2.8. Можно определять сбалансированность дерева иначе:
требовать, чтобы для каждой вершины ее левое и правое поддеревья
имели не слишком сильно отличающиеся количества вершин. (Преиму-
щество такого определения состоит в том, что при вращениях изме-
няется сбалансированность только в одной вершине.) Реализовать
на основе этой идеи способ хранения множеств, гарантирующий
оценку в C*log(n) действий для включения, удаления и проверки
принадлежности. (Указание. Он также использует большие и малые
вращения. Подробности см. в книге Рейнгольда, Нивергельта и Део
"Комбинаторные алгоритмы".)
Н Е П О К У П А Й Т Е Э Т У К Н И Г У !
(Предупреждение автора)
В этой книге ничего не говорится об особенностях BIOSа,
DOSа, OSа, GEMа и Windows, представляющих основную сложность при
настоящем программировании.
В ней нет ни слова об объектно-ориентированном программиро-
вании, открывшем новую эпоху в построении дружественных и эффек-
тивных программных систем.
Из нее Вы не узнаете о графических возможностях компьютера,
без которых немыслимо современное программирование, о богатстве
и разнообразии мира видеоадаптеров.
Не рассказано в ней и о написании резидентных программ,
тонкости взаимодействия которых должен знать каждый.
Искусственный интеллект, открывший новые рынки сбыта для
программного обеспечения, обойден презрительным молчанием.
Экспертные системы, которые в скором будущем займут место
на рабочем столе каждого, даже не упоминаются.
Логическое программирование, постепенно вытесняющее уста-
ревший операторный стиль программирования, не затронуто.
Драматический поворот от баз данных к базам знаний, вызвав-
ший в жизни новую профессию -- инженер знаний -- остался незаме-
ченным автором.
Проблемы отладки и сопровождения программ, занимающие, по
общему мнению профессионалов, 90% в программировании, игнориру-
ются.
В книге используются лишь самые элементарные возможности
паскаля. Обширные возможности, предоставляемые современными ин-
тегрированными программными средами, остаются невостребованными.
(Не говоря уже о том, что паскаль уже вообще устарел, вытеснен-
ный языком Си.)
Игрушечные головоломки, которым посвящена книга, никому не
нужны. Если же перед Вами встанет действительно важная задача,
неужели Вы не справитесь с ней сами, без непрошеных учителей и
советчиков?
Короче говоря, покупать эту книгу глупо - особенно теперь,
когда выходит столько переводных руководств, написанных в циви-
лизованных странах настоящими профессионалами.
Глава 1. Переменные, выражения, присваивания.
1.1. Задачи без массивов
1.1.1. Даны две целые переменные a, b. Составить фрагмент
программы, после исполнения которого значения переменных поменя-
лись бы местами (новое значение a равно старому значению b и на-
оборот).
Решение. Введем дополнительную целую переменную t.
t := a;
a := b;
b := t;
Попытка обойтись без дополнительной переменной, написав
a := b;
b := a;
не приводит к цели (безвозвратно утрачивается начальное значение
переменной a).
1.1.2. Решить предыдущую задачу, не используя дополни-
тельных переменных (и предполагая, что значениями целых перемен-
ных могут быть произвольные целые числа).
Решение. (Начальные значения a и b обозначим a0, b0.)
a := a + b; {a = a0 + b0, b = b0}
b := a - b; {a = a0 + b0, b = a0}
a := a - b; {a = b0, b = a0}
1.1.3. Дано целое число а и натуральное (целое неотрица-
тельное) число n. Вычислить а в степени n. Другими словами, не-
обходимо составить программу, при исполнении которой значения
переменных а и n не меняются, а значение некоторой другой пере-
менной (например, b) становится равным а в степени n. (При этом
разрешается использовать и другие переменные.)
Решение. Введем целую переменную k, которая меняется от 0
до n, причем поддерживается такое свойство: b = (a в степени
k).
k := 0; b := 1;
{b = a в степени k}
while k <> n do begin
| k := k + 1;
| b := b * a;
end;
Другое решение той же задачи:
k := n; b := 1;
{a в степени n = b * (a в степени k)}
while k <> 0 do begin
| k := k - 1;
| b := b * a;
end;
1.1.4. Решить предыдущую задачу, если требуется, чтобы чис-
ло действий (выполняемых операторов присваивания) было порядка
log n (то есть не превосходило бы C*log n для некоторой констан-
ты C; log n - это степень, в которую нужно возвести 2, чтобы по-
лучить n).
Решение. Внесем некоторые изменения во второе из предложен-
ных решений предыдущей задачи:
k := n; b := 1; c:=a;
{a в степени n = b * (c в степени k)}
while k <> 0 do begin
| if k mod 2 = 0 then begin
| | k:= k div 2;
| | c:= c*c;
| end else begin
| | k := k - 1;
| | b := b * c;
| end;
end;
Каждый второй раз (не реже) будет выполняться первый вариант
оператора выбора (если k нечетно, то после вычитания единицы
становится четным), так что за два цикла величина k уменьшается
по крайней мере вдвое.
1.1.5. Даны натуральные числа а, b. Вычислить произведение
а*b, используя в программе лишь операции +, -, =, <>.
Решение.
var a, b, c, k : integer;
k := 0; c := 0;
{инвариант: c = a * k}
while k <> b do begin
| k := k + 1;
| c := c + a;
end;
{c = a * k и k = b, следовательно, c = a * b}
1.1.6. Даны натуральные числа а и b. Вычислить их сумму
а+b. Использовать операторы присваивания лишь вида
<переменная1> := <переменная2>,
<переменная> := <число>,
<переменная1> := <переменная2> + 1.
Решение.
...
{инвариант: c = a + k}
...
1.1.7. Дано натуральное (целое неотрицательное) число а и
целое положительное число d. Вычислить частное q и остаток r при
делении а на d, не используя операций div и mod.
Решение. Согласно определению, a = q * d + r, 0 <= r < d.
{a >= 0; d > 0}
r := a; q := 0;
{инвариант: a = q * d + r, 0 <= r}
while not (r < d) do begin
| {r >= d}
| r := r - d; {r >= 0}
| q := q + 1;
end;
1.1.8. Дано натуральное n, вычислить n!
(0!=1, n! = n * (n-1)!).
