Чтобы добавлять сообщения и комментарии, .

@13oz:
13oz

Интересно, а что толкнуло Вирта на использование Oberon в качестве языка, на котором он писал примеры для своих "Алгоритмов и структур данных"? Не вижу никаких причин, кроме желания сделать свой язык более популярным.

@13oz:
13oz

что бы сохранить всю информацию с предыдущих шагов, нужно работать с некой древесной структурой... эм... моцк?))))

@Drino:
Drino

Никак не могу понять, как искать максимальную (по количеству рёбер) общую связную подструктуру двух графов поиском с возвратом. Объясните кто-нибудь, пожалуйста.
На всякий случай поясню — под подструктурой я понимаю какой-то подграф, возможно без некоторых рёбер.

@zhu:
zhu

1. Design and Analysis of Algorithms охуенен
2. Первый Programming question 6/6

@folex:
folex

Если мы делаем такой DFS:
while(!s.empty())
{
v = s.top();
s.pop();
for(int i = 0; i < tree.at(v).first.size(); ++i)
{
int current = tree.at(v).first.at(i);
if(!used.at(current))
{
s.push(current);
}
}
}

//для справки: vector<pair<vector<int>, char> > tree;

То как на каждой итерации знать, на какой глубине мы сейчас?
Ничего кроме слежения за кол-вом элементов в стеке, и при изменении оного учитывать, что переходим в новую ветку/закончили какую-то ветку (в графе), и в зависимости от этого сбрасывать глубину (дерьмо-то какое), в голову не приходит.

@xeningem:
xeningem

Никак не догоню понятие "допустимости эвристической функции" для алгоритма поиска A*.
Т.е. определение-то я знаю — "h(n) никогда не переоценивает стоимость достижения цели", но как-то не чувствую.
К примеру — для плоскости h((x,y), (x', y')) = sqrt((x-x')^2+(y-y')^2), где (x,y) — координаты точки, а (x', y') — координаты цели. Тут понятно, что не превышает.
Для шахматной доски — то же самое, только функция будет уже (наверное):
h((x,y), (x', y')) = abs(x-x')+abs(y-y') (по диагоналям не ходим), или h((x,y), (x', y')) = ceil(sqrt((x-x')^2+(y-y')^2)) (если по диагоналям ходим).
А будет ли примемлимой (для шахматной доски) такая функция:
h((x,y), (x', y')) = max(sqrt((x-x')^2+(y-y')^2)-2, 0)
?

@DJm00n:
DJm00n

upload.wikimedia.org интересное представление пузырьковой сортировки.

@dream-x:
dream-x

compression-pointers.ru

@dream-x:
dream-x

osp.ru

@KennyHORROR:
KennyHORROR

Хех. После некоторых раздумий решил себе завести свою базу реализаций алгоритмов. Для начала хотя бы, чтобы был precode. Возможно дальше начну пополнять не только кодом... Как же слегка тяжело было смотреть на код своего блога, который я писал примерно 1.5 года назад... Почти ничего не понятно. А особенно учитывая что он был закрыт на неопределенный срок после падения веника у хостера, то накатывался он обратно теми версиями файлов что были найдены и было слегка геморно понять почему не пашет CSS, до того как обнаружил что там самый древний билд =).

@folone:
folone

Годный сайтец: e-maxx.ru

@GunnerKade:
GunnerKade

У алгоритма Евклида нахождения НОД натуральных чисел X и Y, есть замечательная геометрическая интерпретация. Пусть дан прямоугольник размерами X на Y, тогда если последовательно отрезать от него квадраты максимально возможного размера, то в итоге останется квадрат размером НОД(X,Y).
Если бы мне в школе дали такую интерпретацию алгоритма, я бы надолго его запомнил.
Такой алгоритм с отсечением квадратов будет конечным для любого исходного прямоугольника с рациональными длинами сторон. Если же длины сторон заданы рациональным и иррациональным числом, то алгоритм никогда не завершится.
Если взять стороны в отношении 1 : 1.618 ( золотое сечение, 1 : \frac{1+\sqrt{5}}{2} ), разрезать этот прямоугольник согласно описанному алгоритму, при этом проводя в каждом квадрате по четверти окружности, то в итоге все эти дуги соединятся в кривую — спираль Архимеда. dl.dropbox.com
Кстати, впервые такой способ начертания спирали Архимеда я увидел в фильме Pi, что произвело на меня впечатление. Разумеется, можно начертить спираль для прямоугольника с любым другим соотношением сторон, однако, она не будет такой же однородной как спираль Архимеда.

@GunnerKade:
GunnerKade

Не думал, что мне когда-нибудь пригодятся знания с первого курса, конкретно про классическое доказательство равномощности множества рациональных и натуральных чисел.
Нужно было найти взаимнооднозначное соответствие между координатами узлов сетки неизвестных размеров и множеством чисел {0,1,2,...}. Вобщем, обходим сетку змейкой, и, таким образом, получаем то, что нужно. ru.wikipedia.org
И чтобы не забыть, код перевода туда и обратно:
int toN(int row, int col)
{
int d = col + row;
return ((d+1)*d)/2 + col;
}

void toR(int ind, int& row, int& col)
{
int sum=0, i=0;
while(ind > sum+i)
sum += ++i;

col = ind — sum;
row = i — col;
}
ind, row, col — 0-based
Попробуйте избавиться от цикла в toR.
P.S.: Странно — нет ни одного сообщения с тегом algo.