thefish
Python algo Посмотрел тут очередной видосик Саввы:
youtube.com
(он там хуесосит Минобр на научной базе)


И вспомнил, что мне попадалась статья по применению Гейла-Шепли к подбору жён :)
sciencedirect.com

PS Даже есть реализация алгоритма на питоне :D
github.com
13oz
code dev juick_ppl ? algo
Интересно, а что толкнуло Вирта на использование Oberon в качестве языка, на котором он писал примеры для своих "Алгоритмов и структур данных"? Не вижу никаких причин, кроме желания сделать свой язык более популярным.
13oz
algo что бы сохранить всю информацию с предыдущих шагов, нужно работать с некой древесной структурой... эм... моцк?))))
Drino
math graph ? programming algo Никак не могу понять, как искать максимальную (по количеству рёбер) общую связную подструктуру двух графов поиском с возвратом. Объясните кто-нибудь, пожалуйста.
На всякий случай поясню — под подструктурой я понимаю какой-то подграф, возможно без некоторых рёбер.
folex
ятупой ? algo Если мы делаем такой 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
a_star_search AI ? algo Никак не догоню понятие "допустимости эвристической функции" для алгоритма поиска 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)
?
KennyHORROR
old_code algo precode Хех. После некоторых раздумий решил себе завести свою базу реализаций алгоритмов. Для начала хотя бы, чтобы был precode. Возможно дальше начну пополнять не только кодом... Как же слегка тяжело было смотреть на код своего блога, который я писал примерно 1.5 года назад... Почти ничего не понятно. А особенно учитывая что он был закрыт на неопределенный срок после падения веника у хостера, то накатывался он обратно теми версиями файлов что были найдены и было слегка геморно понять почему не пашет CSS, до того как обнаружил что там самый древний билд =).
GunnerKade
math CS algo У алгоритма Евклида нахождения НОД натуральных чисел X и Y, есть замечательная геометрическая интерпретация. Пусть дан прямоугольник размерами X на Y, тогда если последовательно отрезать от него квадраты максимально возможного размера, то в итоге останется квадрат размером НОД(X,Y).
Если бы мне в школе дали такую интерпретацию алгоритма, я бы надолго его запомнил.
Такой алгоритм с отсечением квадратов будет конечным для любого исходного прямоугольника с рациональными длинами сторон. Если же длины сторон заданы рациональным и иррациональным числом, то алгоритм никогда не завершится.
Если взять стороны в отношении 1 : 1.618 ( золотое сечение, 1 : \frac{1+\sqrt{5}}{2} ), разрезать этот прямоугольник согласно описанному алгоритму, при этом проводя в каждом квадрате по четверти окружности, то в итоге все эти дуги соединятся в кривую — спираль Архимеда. dl.dropbox.com
Кстати, впервые такой способ начертания спирали Архимеда я увидел в фильме Pi, что произвело на меня впечатление. Разумеется, можно начертить спираль для прямоугольника с любым другим соотношением сторон, однако, она не будет такой же однородной как спираль Архимеда.
GunnerKade
C++ math algo Не думал, что мне когда-нибудь пригодятся знания с первого курса, конкретно про классическое доказательство равномощности множества рациональных и натуральных чисел.
Нужно было найти взаимнооднозначное соответствие между координатами узлов сетки неизвестных размеров и множеством чисел {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.