Алгоритмы, методы, исходники / Форум

Алгоритмы, методы, исходники / Форум (http://forum.algolist.ru/)
-   Математические алгоритмы (http://forum.algolist.ru/algorithm-maths/)
-   -   Помогите решить задачку (http://forum.algolist.ru/algorithm-maths/3836-pomogite-reshit-zadachku.html)

гость 22.05.2010 18:44

Помогите решить задачку
 
Задача: Профессор предполагает, что для случая, когда вес треугольника равен его площади, алгоритм нахождения оптимальной триангуляции можна упростить. Не обманывает ли он?

Помогите пожалуйста с решением или подскажите литературу. Просто я мало сталкивался с доказательством каких либо теорем. Помогите если не трудно.

гость 22.05.2010 20:28

Ну так требуй доказательств у своего профессора!

Цитата:

Сообщение от гость (Сообщение 12161)
вес треугольника

что за бред? вырвали фразу откуда-то из контекста.

гость 22.05.2010 22:20

что за бред? вырвали фразу откуда-то из контекста.[/quote]

Вообщето это задача из книги Кормена "Алгоритмы. Построение и анализ."
Задача №16.4-2. так что это не бред

гость 22.05.2010 23:14

Цитата:

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

Цитата:

Сообщение от гость (Сообщение 12168)
Вообщето это задача из книги Кормена "Алгоритмы. Построение и анализ."
Задача №16.4-2.

а вот с этого упоминания и следовало начинать.

многоугольник выпуклый?

гость 22.05.2010 23:23

Ну если Вы такой образований и по физике и матиматике у Вас было 5 то могли бы и догадатся сразу что он выпуклый.

гость 22.05.2010 23:37

триангулировать можно и невыпуклые.

в выпуклом же просто проводите диагонали из некоторой вершины до всех остальных - вот и получите искомую триангуляцию

гость 23.05.2010 03:42

Я понимаю что можно триангулировать его так но доказать эту самую задачу что алгоритм можна упростить приняв за вес триугольника его площадь я немогу

гость 23.05.2010 03:55

а чего там доказывать. в триангуляции по определению треугольники должны быть непересекающимися и целиком покрывать исходную фигуру => сумма их площадей должна быть равна площади многоугольника => сумма весов также равна ей. меньше нельзя иначе какая-то часть многоугольника не была бы покрытой


Часовой пояс GMT +4, время: 17:54.