Квадрат отражённый

Реализация структуры на основе множества Кантора.
26 апреля 20173f999bca2e09533f466a56a541996a22772ed1b5Андрей Вуколов186816

На одном из мастер-классов мне попалась задача под названием "Вавилонская башня". Текст её звучит так:

«Вавилонская башня-2»

Вавилоняне решили построить удивительную башню — расширяющуюся к верху и содержащую бесконечное число этажей и комнат. Она устроена следующим образом — на первом этаже одна комната, затем идет два этажа, на каждом из которых по две комнаты, затем идёт три этажа, на каждом из которых по три комнаты и так далее:
#         ...
#     12  13  14
#      9  10  11
#      6   7   8
#        4   5
#        2   3
#          1
#

Эту башню решили оборудовать лифтом. Для этого нужно научиться по номеру комнаты определять, на каком этаже она находится и какая она по счёту на этом этаже.


Введение и теория

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

                          |** **
            |8 11 14|   |17 **
    |3  5| |7 10 13|  |16 **
|1| |2  4| |6  9 12|   |15 **

...и дальше "развернуть" представление в массив:

1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 **

При первом же взгляде на составленную гистограмму становится понятно, что ячейки в ней разделены на элементарные группы - квадраты (их границы я специально отметил вертикальной чертой). Длина стороны каждого такого квадрата в ячейках возрастает на единицу после заполнения ячейками предыдущего квадрата. То есть выполнены условия геометрического подобия и размеры квадратов связаны между собой монотонно возрастающей линейной функциональной зависимостью. Каждый новый квадрат, таким образом, оказывается подобен всем предыдущим, и структура развивается до бесконечности, то есть проявляет свойства фрактала. С другой стороны, такую же самоподобную структуру очень легко представить в виде своеобразного дерева, "n-арность" (число возможных элементов, являющихся потомками текущего) которого возрастает на единицу с добавлением каждой новой группы узлов (квадрата).

Посмотрев ещё раз на гистограмму, приведённую выше, очень легко понять, что подобные псевдо-древовидные фракталы на самом деле есть одномерные множества, которые строятся с помощью ввода искусственных ограничений на длину элементарных отрезков обычного числового луча. Все они являются частными случаями одномерного фрактала (в каноническом виде представляемого как древовидная структура из элементарных отрезков, длина которых уменьшается втрое с каждым новым уровнем), называемого множеством Кантора и изображаемого в виде двухмерной слоистой диаграммы ("пылящие" отрезки).

Пылящие отрезки

В нём каждая элементарная группа (квадрат или отрезок) также подобна всем предыдущим и представляет собой самостоятельное замкнутое одномерное множество. Классическим случаем представления множества Кантора в двухмерном пространстве является известная фрактальная фигура - треугольник Серпинского.

Треугольник Серпинского

Причешем задачу. Декомпозиция

Изначальная наша задача, таким образом, сводится к определению по номеру текущей ячейки трёх целых беззнаковых чисел:

  • Номера квадрата (элементарной группы) в их собственной последовательности;
  • Номера этажа ("слоя" или столбца гистограммы) в общей последовательности;
  • Номера ячейки внутри текущего этажа.

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

          Квадрат
----------------------------------------------------------------
 1     2         3             4     | Место на этаже|
__________________|** **____4                     |
________|8_11_14|_|17 **____3                    |
___|3_5|_|7_10_13|_|16 **____2                    |
|1|_|2_4|_|6__9_12|_|15 **____1                    |
---------------------------------------------------------------
 1   2  3    4  5  6       7       Этаж (столбец)

Теперь пришло время "причесать" задачу в одномерной постановке. Не забываем, что на входе у нас беззнаковое целое число. Расставим в развёрнутой последовательности границы квадратов...

1 | 2  3  4  5 | 6  7  8  9 10 11 12 13 14 | 15 16 17 **

...и этажей:

1 | 2  3 | 4  5 | 6  7  8 | 9 10 11 | 12 13 14 | 15 16 17 18 | **

Номер ячейки, заданный на входе, может находиться в этой последовательности в любом месте, кроме границ.

Алгоритм

Самым простым способом нахождения требуемых "координат" ячейки в нашей гистограмме поначалу кажется простой цикл, на каждой итерации которого текущий номер ячейки проверялся бы на "переход" той или иной границы (не нужно забывать и о том, что граница квадрата всегда является границей этажа, но не наоборот). Время выполнения у этого простейшего алгоритма, в лучшем случае, линейно зависит от сообщённого номера ячейки. В худшем же случае номер текущего квадрата вычисляется с помощью нахождения целой части квадратного корня методом середин отрезков, что увеличивает время выполнения до квадратичного. Очевидно, что с номерами ячеек в диапазоне до двух миллиардов такой алгоритм работать не будет.

Более удачным выбором будет алгоритм, сводящийся к следующим простым шагам:

  1. Лететь по квадратам гистограммы до тех пор, пока заданный номер ячейки не окажется внутри текущего;
  2. Внутри найденного квадрата лететь по столбцам, пока заданный номер ячейки не окажется приписанным к текущему;
  3. Вычислить позицию как приращение номера начальной ячейки столбца, необходимое для попадания точно в требуемый номер ячейки развёрнутой последовательности.

По времени выполнения этот алгоритм оптимален, поскольку по мере приближения к искомой ячейке приращение значения текущего счётчика ячеек сначала идёт пропорционально квадрату номера итерации. Как только получен искомый квадрат, приращение должно пойти на число ячеек, равное номеру этого квадрата в гистограмме. В искомом столбце приращение уже равно единице.

Поиск квадрата - изюминка. Он идёт тем быстрее, чем дальше искомая ячейка от начала последовательности. Чем больше заданный для поиска номер ячейки, тем больше такой алгоритм выигрывает во времени у других.

Реализация

Python

box = 0 #Начинаем с нуля, чтобы не пропустить первый квадрат
pos = 1 #Позиция ячейки в одномерной последовательности
etage = 1 #Номер столбца гистограммы ("этаж")

while (pos + (box * box)) <= room: #Идём по квадратам, ищем нужный
    pos += (box * box) #pos хранит номер первой ячейки в текущем квадрате
    etage += box #Счётчик столбцов прирастает на число этих столбцов в квадрате
    box += 1 #Квадраты считаются по одному


onetage = 1 #Храним приращение номера столбца внутри текущего квадрата
while (pos + (onetage * box)) <= room :
    pos += onetage * box #pos хранит номер первой ячейки в текущем столбце
    onetage += 1 #Увеличиваем приращение
etage += onetage - 1 #Регистрируем найденный столбец


place = 1 #Храним приращение номера ячейки в текущем столбце
while (pos + place) <= room :
    place += 1
pos += place - 1

#Вывод данных
print('\tEtage:\t%s\n\tPlace:\t%s' % (etage, place) )
print('Position in the sequence: %s' % (pos))

C++ (без комментариев)

void Babalon(unsigned int room)
{
    unsigned int box = 0;
    unsigned int etage = 1;
    unsigned int pos = 1;
    while((pos + (box * box)) <= room)
    {
            pos += (box * box);
            etage += box;
            box++;
    }
    unsigned int onetage = 1;
    while((pos + (onetage * box)) <= room)
    {
        pos += onetage * box;
        onetage++;
    }
    etage += onetage - 1;
    unsigned int place = 1;
    while((pos + place) <= room) place++;
    pos += place - 1;
    std::cout << "\tEtage:\t" << etage << "\n\tPlace:\t" << place << std::endl;
    std::cout << "Position in the sequence: " << pos << std::endl;
}

Заключение

Алгоритм, который я описал здесь, применим практически для любой списочной (через массив или связную последовательность) реализации множества Кантора. Это один из самых быстрых алгоритмов поиска элемента в так называемых расходящихся (с монотонно и бесконечно увеличивающимся размером элементарного блока) последовательностях и рядах. Кроме того, математика оставила нам здесь ещё одну скрытую возможность для обобщения и оптимизации, которую я намеренно не стал раскрывать. 

Приглашаю обсудить эту тему в комментариях!