Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 22.05.2010, 18:44
гость

 
Сообщений: n/a

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

Помогите пожалуйста с решением или подскажите литературу. Просто я мало сталкивался с доказательством каких либо теорем. Помогите если не трудно.
  #2  
Старый 22.05.2010, 20:28
гость

 
Сообщений: n/a

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

Сообщение от гость Посмотреть сообщение
вес треугольника
что за бред? вырвали фразу откуда-то из контекста.
  #3  
Старый 22.05.2010, 22:20
гость

 
Сообщений: n/a

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

Вообщето это задача из книги Кормена "Алгоритмы. Построение и анализ."
Задача №16.4-2. так что это не бред
  #4  
Старый 22.05.2010, 23:14
гость

 
Сообщений: n/a

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

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

многоугольник выпуклый?
  #5  
Старый 22.05.2010, 23:23
гость

 
Сообщений: n/a

Ну если Вы такой образований и по физике и матиматике у Вас было 5 то могли бы и догадатся сразу что он выпуклый.
  #6  
Старый 22.05.2010, 23:37
гость

 
Сообщений: n/a

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

в выпуклом же просто проводите диагонали из некоторой вершины до всех остальных - вот и получите искомую триангуляцию
  #7  
Старый 23.05.2010, 03:42
гость

 
Сообщений: n/a

Я понимаю что можно триангулировать его так но доказать эту самую задачу что алгоритм можна упростить приняв за вес триугольника его площадь я немогу
  #8  
Старый 23.05.2010, 03:55
гость

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Пожалуйста помогите решить задачку Анюта Сортировка и поиск 0 03.01.2010 16:30
помогите решить задачку на паскале (подпрограмма Procedure) гость Реализация, исходники, языки 2 27.11.2008 18:44
помогите решить задачку по указателям и функциям. sercul Математические алгоритмы 1 17.11.2008 01:14
Помогите решить задачку в с++ MermaidAlyona Оффтопик 1 30.10.2008 13:15
помогите плиз решить задачку Daiver Математические алгоритмы 2 22.04.2007 18:45