|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vladimir Luzhkov 2:5030/1326 05 Apr 2002 20:01:24
To : Zapadinsky Anatoly \(ZAB\)
Subject : Re^2: Задача "Шнуpки"
--------------------------------------------------------------------------------
05 Apr 02 15:17, Zapadinsky Anatoly \(ZAB\) wrote to me:
VL>> Решение такй задачки я как-то разбирал, В итоге окончательно
VL>> пришел к следующему: необходимо по-очереди пытаться эти шнурки
VL>> затягивать. То есть берется первый шнурок, берутся 3 смежные
VL>> вершины и пытаемся 1-2-3 заменить на 1-3. При этом проверяем
VL>> треугольник 1-2-3 на предмет пересечения с каждым другим ребром
VL>> каждого шнурка. Если пересекается - не заменяем. Пройдя по одному
VL>> шнурку до отсутствия замыканий переходим на другой. И так
VL>> поочередно.
ZZ> Хм... У меня один знакомый уже дня 4 назад такое предложил, я ему
ZZ> нашёл пример на котором не работает, но как его описать я не знаю, кто
ZZ> хочет могу выслать *.max или *.bmp(gif) с разных сторон...
ZZ> Вот попытаюсь: есть треугольник (первый шнурок) в него пропущено
ZZ> кольцо из 6 вершин, так что по разные стороны от плоскости
ZZ> треугольника остаётся по 3 вершины, затем самые крайние вершины
ZZ> приподняты и занесены в другую сторону... Со стороны это так:
ZZ> \ /A
ZZ> \|/
ZZ> /|\
ZZ> / | \
ZZ> /--|--\
ZZ>B,C |
ZZ> А сверху:
ZZ> |
ZZ>B--|--
ZZ> \ | /
ZZ> \|/
ZZ> /|\ A
ZZ> \|/
ZZ> /|\
ZZ> / | \
ZZ>C--|--
ZZ> |
ZZ> Развязать можно, но все треугольники пересекают стороны другого
ZZ> шнурка...
Если я тебя правильно понял, ABC или противоположный (тот, который внутри) можно
замкнуть. Потом - дальше, и кольцо затягивается.
Проблему другую тут уже придумали - узлы.
Vladimir, vluzhkov@hotbox.ru
--- GoldED+/W32 1.1.5-0526
* Origin: Optima Station (2:5030/1326)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
