yourdomain.com

Добрый день! Не могли бы вы подсказать один момент в алгоритме? Нам дан алгоритм для нахождения минимальной охватывающей окружности (который выполняется за время О(n^2) : [url=http://www.personal.kent.edu/~rmuhamma/Com...r/centercli.htm]http://www.personal.kent.edu/~rmuhamma/Com...r/centercli.htm [/...

Преподаватель сказал, что можно всё-таки и нелинейные алгоритмы использовать.

[url=http://prografix.narod.ru/min_circle.html]http://prografix.narod.ru/min_circle.html[/url]

Не могли бы вы подсказать, как посчитать трудоёмкость данного алгоритма?

1133861 А вот и весь алгоритм: Алгоритм рекурсивный, за аргументы он берет два множества точек S и Q. Он считает минимальную окружность для S и Q, считая, что каждая точка Q лежит на границе возможной минимальной окружности. Так, сама задача решается вызовом алгоритма с S=исходным точкам, а Q — пус...

Так как дитохомический алгоритм основан на делении пополам, поэтому для оценки трудоемкости берется логарифм по основанию 2 от общего числа вариантов. Теперь всё понятно. Спасибо! Но если я правильно понимаю, то алгоритм этот с максимальным расстоянием всё-таки не является верным для данной задачи?...

Если для 1 точки взять расстояние до нее это будет 0 и записать в матрицу, для второй аналогично и.т.д. Следовательно на диаганали матрицы будут стоять нули. В остальном матрица симметрическая, поэтому все расстояния определять не надо. Поэтому исходные данные можно представить в виде треугольном м...

Спасибо всем большое за помощь! Попробую разобраться.

На русском есть описание алгоритма тут, но он не линейный

а какая трудоёмкость будет у этого алгоритма тогда?

Добрый вечер, товарищи! Не могли бы вы подсказать идею решения следующей задачи? Дано n точек на плоскости. Нужно построить окружность таким образом, чтобы она охватывала все эти точки, лежащие на плоскости, и чтобы радиус её был минимальным. И здесь требуется алгоритм, который будет решать эту зада...

подставляем точку в неравенства. ищем первое невыполняющееся и строим плоскость паралельную данной (из невыполняющегося неравенства) на растоянии вдвое короче от точки

а почему мы такое расстояние берём?...

Спасибо большое, сейчас попробую!

Добрый вечер! Не могли бы вы подсказать, как решать следующую задачку? Нужно вывести уравнение плоскости, отделяющей точку х0=(-1,2,1,-3) от множества $$X \in \mathbb{R}^4$$ : 5х1+х2-5х3-3х4<=1,-3x1-2x2+5x3+x4<=2,3x2+x3+2x4<=0,x1+x2+3x3-x4<=9Не совсем понимаю, по какому алгоритму здесь нужно действо...