|
10.4.4.6. Как Антанаиресис порождает Дерево
|
|
"... желание установить начало событий встречало ту же помеху, с какой всегда сталкивается такое стремление: помеха состоит в том, что у каждого есть отец, что ни одна вещь на свете не появилась сама собой из ничего, а любая от чего-то произошла и обращена назад, к своим далеким первопричинам, к пучинам и глубинам колодца прошлого."
И зададимся вопросом: от чего же произошло
Дерево? Что является его "далекими первопричинами"?
По-видимому, есть все основания полагать, что ими является
алгоритм Антанаиресис, ибо по крайней мере с логической точки зрения он способен самым непосредственным образом породить
Stern-Brocot Tree.
Действительно, вообразим себе, что мы решили заняться исследованием
алгоритма Антанаиресис и с этой целью стали запускать его на различных упорядоченных парах
натуральных чисел a и
b, наблюдая при этом, "как он на них работает".
Допустим также, что с целью визуализации этих наблюдений мы решили прибегнуть к использованию
графической метафоры для Антанаиресиса, связанной со вписыванием квадратов в прямоугольник. Тогда "протокол" работы этого алгоритма на данной конкретной упорядоченной паре натуральных чисел
a и
b может быть записан в виде строки (или "цепочки") символов в
бинарном алфавите { V, H }, состоящем из двух символов
V и
H.
|
Поясним это на конкретном примере, когда на вход алгоритма подается пара натуральных чисел a = 11 и b = 8.
С использованием упомянутой графической метафоры эта исходная ситуация изобразится в виде прямоугольника с длиной горизонтальной стороны равной 11 и с длиной вертикальной стороны равной 8.
|
Каждый элементарный шаг работы алгоритма Антанаиресис моделируется вписыванием ровно одного квадрата в "текущий прямоугольник", который в зависимости от соотношения длин его сторон мы будем квалифицировать как "вертикальный", "горизонтальный" или "квадратный".
А именно, мы будем называть текущий прямоугольник "вертикальным", если длина его вертикальной стороны больше длины его горизонтальной стороны;
мы будем называть текущий прямоугольник "горизонтальным", если длина его горизонтальной стороны больше длины его вертикальной стороны;
наконец, мы будем называть текущий прямоугольник "квадратным", если длина его вертикальной стороны равна длине его горизонтальной стороны (появление такого прямоугольника будет свидетельствовать о завершении алгоритма).
Теперь объясним процедуру "протоколирования" работы алгоритма Антанаиресис при помощи некоторой строки
φ в
бинарном алфавите { V, H }. Перед началом работы алгоритма строка
φ полагается
пустой, а в качестве "текущего прямоугольника" выбирается прямоугольник, символизирующий собою упорядоченную пару чисел
a и
b, подаваемую на вход алгоритма (для нашего конкретного примера
a = 11 и
b = 8 этот прямоугольник изображен выше).
|
На первом шаге алгоритма, поскольку текущий прямоугольник является горизонтальным, мы добавляем справа к текущей строке букву H (от слова Horizontal) и полагаем модифицированную строку в качестве новой текущей строки. Т. е. новой текущей строкой будет φ = H.
|
Кроме того, на первом шаге алгоритма мы вписываем в текущий прямоугольник максимально возможный квадрат, как показано на рисунке, а получившийся в результате вписывания квадрата "остаточный" прямоугольник полагаем в качестве нового текущего прямоугольника. Таким образом, после выполнения первого шага алгоритма новым текущим прямоугольником станет прямоугольник с горизонтальной стороной 3 и вертикальной стороной 8.
|
На втором шаге алгоритма, поскольку текущий прямоугольник является вертикальным, мы добавляем справа к текущей строке букву V (от слова Vertical) и полагаем модифицированную строку в качестве новой текущей строки. Т. е. новой текущей строкой будет φ = HV.
|
Кроме того, на втором шаге алгоритма мы вписываем в текущий прямоугольник максимально возможный квадрат, как показано на рисунке, а получившийся в результате вписывания квадрата "остаточный" прямоугольник полагаем в качестве нового текущего прямоугольника. Таким образом, после выполнения второго шага алгоритма новым текущим прямоугольником станет прямоугольник с горизонтальной стороной 3 и вертикальной стороной 5.
|
На третьем шаге алгоритма, поскольку текущий прямоугольник является снова вертикальным, мы добавляем справа к текущей строке букву V и полагаем модифицированную строку в качестве новой текущей строки. Т. е. новой текущей строкой будет φ = HVV.
|
Кроме того, на третьем шаге алгоритма мы вписываем в текущий прямоугольник максимально возможный квадрат, как показано на рисунке, а получившийся в результате вписывания квадрата "остаточный" прямоугольник полагаем в качестве нового текущего прямоугольника. Таким образом, после выполнения третьего шага алгоритма новым текущим прямоугольником станет прямоугольник с горизонтальной стороной 3 и вертикальной стороной 2.
|
На четвертом шаге алгоритма, поскольку текущий прямоугольник является горизонтальным, мы добавляем справа к текущей строке букву H и полагаем модифицированную строку в качестве новой текущей строки. Т. е. новой текущей строкой будет φ = HVVH.
|
Кроме того, на четвертом шаге алгоритма мы вписываем в текущий прямоугольник максимально возможный квадрат, как показано на рисунке, а получившийся в результате вписывания квадрата "остаточный" прямоугольник полагаем в качестве нового текущего прямоугольника. Таким образом, после выполнения четвертого шага алгоритма новым текущим прямоугольником станет прямоугольник с горизонтальной стороной 1 и вертикальной стороной 2.
|
На пятом шаге алгоритма, поскольку текущий прямоугольник является вертикальным, мы добавляем справа к текущей строке букву V и полагаем модифицированную строку в качестве новой текущей строки. Т. е. новой текущей строкой будет φ = HVVHV.
|
Кроме того, на пятом шаге алгоритма мы вписываем в текущий прямоугольник максимально возможный квадрат, как показано на рисунке, а получившийся в результате вписывания квадрата "остаточный" прямоугольник полагаем в качестве нового текущего прямоугольника. Таким образом, после выполнения четвертого шага алгоритма новым текущим прямоугольником станет прямоугольник с горизонтальной стороной 1 и вертикальной стороной 1.
Поскольку этот прямоугольник является
квадратным, это свидетельствует о
завершении работы алгоритма Антанаиресис, "запущенного" на упорядоченной паре натуральных чисел
a = 11 и
b = 8. Последняя "текущая строка"
φ = HVVHV и будет
"протоколом" его работы на данной конкретной упорядоченной паре натуральных чисел.
Удивительным фактом, который можно строго доказать, является то обстоятельство, что запуская Антанаиресис на всевозможных парах
взаимно простых натуральных чисел, мы будем получать для разных пар разные протоколы и для каждой цепочки в алфавите
{ V, H } будет существовать пара взаимно простых чисел, для которой эта цепочка является протоколом.
В частности, с каждой строкой
φ в алфавите
{ V, H } мы можем однозначно связать вполне определенную вершину на
Stern-Brocot Tree по следующему правилу: стартуем с корня дерева и далее идем по последовательности красных и синих дуг дерева в соответствии со считывемыми символами строки
φ (строку читаем справа-налево): если читаем символ
V, то идем по красной дуге, а если читаем символ
H, то идем по синей дуге (см. рисунок ниже).
Вершина Дерева, в которую мы попадем таким образом в соответствии со строкой φ, будет помечена некоторой дробью с числителем a и со знаменателем b. Оказывается, что эти числа a и b образуют такую упорядоченную пару взаимно-простых чисел, что после запуска на ней алгоритма Антанаиресис протоколом его работы будет строка φ. В этом смысле Антанаиресис "порождает" Дерево, т. е. структура Stern-Brocot Tree полностью определяется особенностями функционирования этого алгоритма.
По поводу Stern-Brocot Tree см. также:
