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

Генерация случайного дерева

В ходе работы над дипломом мне пришлось столкнуться с необходимостью генерации дерева. Так как я точно не знаю, какое именно дерево будет описывать мою задачу (деревом представляется булева функция общего вида), я решил, что будет логично прогнать алгоритмы на достаточно большом количестве случайных деревьев. Итак, генерация случайного дерева.

В качестве структуры данных, для хранения была выбрана матрица смежности. Будем считать, что дерево — ориентированный граф с полустепенью захода у каждой вершины равной 1 (кроме корня: у него 0). Также нам нужно сделать так, чтобы у нас был всего один корень (то есть нам нужно именно дерево, а не лес).
Матрица смежности — это булева матрица, в (i, j) вершине которого содержится информация о том, присутствует ли в графе ребро изходящее из i и входящее в j. Из этого легко получить условия, которые мы должны наложить на матрицу, чтобы она описывала именно дерево.

1. В столбце i (i > 0) должна стоять одна и только одна единица на месте j (j < i). Таким образом мы обеспечим полустепень захода равную 1 для всех вершин графа, кроме корня. Будем, для удобства считать, что корнем является нулевая вершина.
2. Ниже главной диагонали (и на ней) должны стоять нули, это обеспечит ориентированность дерева, и тот факт, что вершины с большим номером будут являтся детьми, только вершинам с меньшим номером.

Ниже я привожу небольшу программку для примера, генерирующую случайное дерево и выводящую результат в dot-cовместимом формате.

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>

int
main(int argc, char** argv)
{
    using namespace std;
    srand(time(NULL));
    vector<vector<int> > matrix;
    #define size 1000
    matrix.resize(size);
    for (int i = 0; i < size; i++) {
        matrix[i].resize(size);
        for (int j = 0; j < size; j++) {
            matrix[i][j] = 0;
        }
    }
    for (int i = size - 1; i > 0; i--) {
        /**
         * (rand() % i) - случайное число в множестве [0, i)
         * i-тый столбец
         */
        matrix[rand() % i][i] = 1;
    }
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (matrix[i][j] == 1) {
                cout << i << " -> " << j << ";" << endl;
            }
        }
    }
}

И на закуску небольшой пример:

0 1 0 0 0
0 0 1 1 0
0 0 0 0 1
0 0 0 0 0
0 0 0 0 0

Дерево, представленное этой матрицей будет выглядеть так:

Обратите внимание, что четвертая и пятая строки в матрице содержат только нули. На графе они стали листьями. Столбец содержащий одни нули (1-ый) является корнем.

Wikipedia лежит

По всей видимости, сейчас сайт открытой энциклопедии wikipedia.org лежит. При попытке обращения через браузер подгрузка страницы останавливается на "Ожидание ответа", при попытке доступа через telnet срабатывает timeout.

Задача

Предположим, что некий велосипедист проезжает круг со скоростью 30 километров в час. А потом едет тот же круг второй раз. С какой скоростью он должен двигаться, чтобы средняя скорость за два круга составляла 60 километров в час?

P.S. Подсказка для решающих: предположите, что длина круга 30 километров.

О взаимодействии flex и bison

flex — генератор лексических анализаторов, bison — синтаксических. Оба эти пакета действуют по одной и той же схеме: они берут описание грамматики (для flex этот файл содержит описание лексем с помощью регулярных выражений, для bison — описание грамматики в формате близком к BNF) и выдают файлы, содержащие C-программу, которая занимается разбором входного текста. Исторически сложилось так, что работают они в связке, а мануалы для них отдельные. Схема синтаксического разбора входного текста выглядит так:

1. Лексер (результат работы flex) предоставляет для bison функцию yylex(); которая возвращает код следующей лексемы распознанной во входном файле yyin.
   
2. Парсер (результат работы bison) берет входные лексемы от flex (вызов yylex() происходит внутри функции yyparse(); и распознав то или иное правило, вполняет указанное действие.
   

Проблемы при запуске ANTLRWorks в Ubuntu 8.04

Генератор синтаксических анализаторов ANTLR выгодно отличается от других программ из этого класса наличием IDE. Она носит название ANTLRWorks. Проблем при запуске может и не быть (если установлены все нужные пакеты), но у меня они возникли. Итак, для того, чтобы запустить её из-под Ubuntu 8.04 (на других не пробовал) нужно:
1. Скачать саму программу с официального сайта. Она представляет из себя простой *.jar пакет.
2. Иметь установленным пакет sun-java6-jdk (sudo apt-get install sun-java6-jdk).
3. И (самый коварный момент) НЕ должен быть установлен пакет java-gcj-common (и остальные, начинающиеся с этого префикса). Как только я удалил эти пакеты программа запустилась.

Запустить программу можно так:

java -jar antlrworks-1.3.1.jar

Tips & Tricks #1: Забытый Dev-Cpp

Недавно я установил новый QtSDK. Компиляция простого GUI проекта приводила к нелогичным ошибкам:

undefined reference to `_Unwind_Resume'
undefined reference to `__gxx_personality_v0'

Решение оказалось чрезвычайно простым. Давным-давно я ставил на комп Dev-Cpp, и конечно же, не догадывался, что qmake берет MinGW именно оттуда. Удаление Dev-Cpp решило проблему. MinGW «стал браться» из нужного места (папки mingw в папке с QtSDK) и все заработало. Чтение maillist-а и makefile решает любые проблемы.

Проблемы с install-info при установке пакетов в Ubuntu

При установке некоторых пакетов в Ubuntu (8.04) начала возникать ошибка:

install-info: No dir file specified; try --help for more information.
dpkg: не удалось обработать параметр <название пакета> (--configure):
 подпроцесс post-installation script возвратил код ошибки 1
При обработке следующих пакетов произошли ошибки:
 <название пакета>

Осмотр пре- и постинсталляционных скриптов пакетов, при установке которых возникали ошибки (кэш пакетов находится в папке /var/cache/apt/archives), показал, что ошибка возникает именно на команде install-info.

Некоторые google-мучения подсказали, что нужно проверить версии установленных приложений.

numlock@oligocheta:~$ whereis install-info
install-info: /usr/sbin/install-info /usr/local/bin/install-info /usr/share/man/man8/install-info.8.gz
numlock@oligocheta:~$ /usr/sbin/install-info --version
Debian install-info version 1.14.25.
...
numlock@oligocheta:~$ /usr/local/bin/install-info --version
install-info (GNU texinfo) 4.13
...

Я попытался поменять местами значения переменной PATH '/usr/sbin:' и '/usr/local/bin:'. но это не привело к должному эффекту. Поэтому я просто переименовал символическую ссылку install-info в install-info-gnu (в папке /usr/local/bin), чтобы dpkg находил не его, а версию для Debian.

numlock@oligocheta:~$ sudo mv /usr/local/bin/install-info /usr/local/bin/install-info-gnu

Все заработало.

Рецепт взят из Naveen Kumar Molleti's Tech Blog