Корень n-ой степени из числа

Для вычисления корня n-ой степени из какого-либо действительного числа x достаточно вот таких простых преобразований:

Т.е. на языке, скажем C++, это будет выглядеть так:

double res = exp((1/n) * log(x));

Сбалансированность дерева

Иногда (при работе с деревьями очень часто) бывает нужно понять, насколько дерево сбалансированно. Проблема в том, что эта характеристика более-менее понятна в отношении бинарных деревьев (для них она равна отношению мощности левого и правого поддеревьев), а для «обычных» деревьев, в общем-то, не понятно, что на
что делить.

Итак, пусть T — «обычное» ориентированное дерево, и из каждой вершины может исходить n ребер. В зависимоти от задачи, можно считать сбалансированность разными способами:

Если n четно, тогда сбалансированность можно считать по следующей формуле:

 

где — мощность поддерева, с корнем в j-той вершине данного дерева. Нумерация здесь соответсвует обходу в ширину, а корень дерева имеет нулевой индекс. То есть, мы берем все ребра исходящие из корня дерева и делим это множество на два. Ссуммируем мощность подмножеств, которые начинаются с вершин, в которые входят эти ребра, и делим одну сумму на другую.
Если n нечетно, тогда формула видоизменяется следующим образом:

Смысл формулы здесь не изменился, но мы учитываем также половину мощности «центрального» поддерева и в делимом и в делителе.

Также сбалансированностью можно считать следующую величину:

где — мощность множества уровней дерева, которые содержат листья, а — количество уровней всего.

Генерация случайного разбиения

У Кнута в 4-ой части Искусства программирования есть описание алгоритма генерации всех разбиений n-элементного множества на m-частей (раздел 7.2.1.4). Положим, что нам нужно найти какое-нибудь случайное разбиение (например, мне это понадобилось для генерации случайного дерева заданной несбалансированности). Конечно, мы будем использовать случайные числа.
Смысл следующий: берем массив из m элементов и заполняем его случайными числами в диапазоне от 0 до n. Последнему элементу присваиваем значение n. Мы получили массив, в котором содержатся "метки" — значения указывающие на то, в каком именно месте будет разбито наше множество.
Затем сортируем массив, последовательно начиная с m-1-ого элемента находим разность между i-м и i-1-м элементами и записываем её в i-ую ячейку массива. Нулевой элемент массива оставляем без изменений.
Проблема в том, что этот алгоритм не гарантирует, что в результирующем массиве не будут отсутствовать нулевые элементы. С этим можно бороться последующей балансировкой. Заводим специальную переменную (например, diff) для сохранения количества "балансировок" и пока эта переменная не станет равна нулю ходим по массиву и совершаем следующие действия:

1. Если наткнулись на ячейку содержащую ноль, прибавляем к её значению единицу, а из переменной единицу вычитаем.
2. Если diff меньше нуля, а текущий элемент массива больше нуля, то прибавляем diff единицу, а из текущего элемента её вычитаем.

Вот как это выглядит у меня:

void
getPartition(unsigned n, unsigned m)
{
    if (n < m) {
        throw out_of_range("N must be greater then M");
    }
    unsigned sum = 0;
    vector< unsigned > partition;
    partition.resize(m);
    // заполнение массива случайными значениями
    for (unsigned i = 0; i < m; i++) {
        partition[i] = rand() % n;
    }
    partition[partition.size() - 1] = n;
    // сортировка
    sort(partition.begin(), partition.end());
    // вычитаение
    for (unsigned i = m - 1; i > 0; i--) {
        partition[i] = partition[i] - partition[i - 1];
    }
    int diff = 0;
    // балансировка
    do {
        for (unsigned i = 0; i < m; i++) {
            if (partition[i] < 1) {
                partition[i]++;
                diff--;
            }
            if (diff < 0) {
                if (partition[i] > 1) {
                    partition[i]--;
                    diff++;
                }
            }
        }
    } while (diff != 0);
    // вывод на экран вместе с суммой всех элементов для проверки
    for (unsigned i = m - 1; i > 0; i--) {
        cout << partition[i] << " ";
        sum += partition[i];
    }
    sum += partition[0];
    cout << partition[0] << " " << sum;
    cout << endl;
}

Tips & Tricks #2. Удаленный рабочий стол Ubuntu 10.04 по RDP.

Однажды у меня возникла необходимость подключиться стандартным "Удаленным рабочим столом" Windows к Ubuntu-машине. Сама Windows использует для этих целей протокол RDP, серверная часть которого в *nix-системах представлена продуктом xrdp.
Итак, для начала, устанавливаем сам xrdp:

sudo apt-get install xrdp

После этого, мы уже можем подключаться к нашему серверу, но по-умолчанию используется протокол VNC. С этим видом подключения у меня возникли проблемы переключения раскладок клавиатуры (по умолчанию удаленная сессия видела только одну раскладку en_US). Настроить переключение удалось только с бубном и через IBus, а не через xkb. К тому же подключение более чем 5 машин вешало сеть. Я решил по-пробовать rdp.
Оказалось, что для этого требуется бинарник x11rdp, который в стандартный пакет не входит. Гугл сказал мне, что исходники можно взять здесь:

svn://server1.xrdp.org/srv/svn/repos/main/x11rdp_xorg71

Итак, качаем исходник куда-нибудь, а потом собираем.

cd ~/
mkdir temp
cd temp
svn co svn://server1.xrdp.org/srv/svn/repos/main/x11rdp_xorg71
cd x11rdp_xorg71
sudo mkdir /opt/x11
sudo ./buildx.sh /opt/x11

В последней строчке мы сказали собирающему скрипту, чтобы он положил все собранное в каталог /opt/x11. У меня во время сборки скрипт вывалился с ошибкой и пожаловался, что нет библиотеки zlib. Ставим:

sudo apt-get install zlib1g-dev

и запускаем скрипт заново. Он не будет повторять ту работу, что уже сделал.
После сборки идем в каталог /opt/x11/bin, и просто копируем оттуда файл x11rdp в каталог /usr/bin.
Для того, чтобы подключение через x11rdp было подключением по-умолчанию идем в каталог /etc/xrdp и в файле xrdp.ini помещаем блок настроек [xrdp6] перед блоком [xrdp1]. Все, теперь можно подключаться к нашей Ubuntu-машине, с помощью стандартного клиента Windows.

P.S. Если пользователь ни разу не логинился непосредственно на сервер (например, если это доменный пользователь), то ему также придется добавить русскую раскладку клавиатуры и настроить сочетание клавиш для переключения. Все это можно сделать через Система->Параметры->Клавиатура.