to post messages and comments.

← All posts tagged algo

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

Не думал, что мне когда-нибудь пригодятся знания с первого курса, конкретно про классическое доказательство равномощности множества рациональных и натуральных чисел.
Нужно было найти взаимнооднозначное соответствие между координатами узлов сетки неизвестных размеров и множеством чисел {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.