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

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

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

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

Оптитмальная триангуляция.
Помогите решить задачу из книги Кормен "Алгоритмы. Построение и анализ". Задача №16.4-2

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

Как доказать именно то что алгоритм можна упростить.
  #2  
Старый 23.05.2010, 16:17
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Да уж. У кого нет первого издания Кормена, тот и не поймет о чем задача (во втором издании этой темы и задачи нет).

В данном случае любая триангуляция подойдет, т.к. один хрен сумма площадей треугольников равна площади исходного многоугольника
  #3  
Старый 23.05.2010, 16:25
гость

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

http://samouchka.net/2007/07/02/algo..._i_analiz.html
вот ссылка на скачивание кормена и ещё куча таких есть я не думаю что это большая проблема. мне вот доказать бы эту задачу ну просто позарез нада скоро сдавать а я всё сижу немогу сделать. эти задачи нам дают не обясняя нормально теории переходят к другой теме а ты делай как хош
  #4  
Старый 23.05.2010, 16:27
гость

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

Сообщение от MBo Посмотреть сообщение
В данном случае любая триангуляция подойдет, т.к. один хрен сумма площадей треугольников равна площади исходного многоугольника
Ого то понятно что сума площадей равна площади многоугольника как доказать что алгоритм нахождения триангуляции упростится
  #5  
Старый 23.05.2010, 16:49
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

>алгоритм нахождения триангуляции упростится
Вместо динамического программирования линейный алгоритм, в котором даже ничего искать не нужно - например, триангулируем из одной вершины ко всем (кроме соседних).
  #6  
Старый 23.05.2010, 18:46
гость

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

Сообщение от MBo Посмотреть сообщение
Вместо динамического программирования линейный алгоритм, в котором даже ничего искать не нужно - например, триангулируем из одной вершины ко всем (кроме соседних).
А вот с этого места можна подробнее пожалуйста
  #7  
Старый 23.05.2010, 18:46
гость

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

Для чайников
  #8  
Старый 24.05.2010, 17:15
гость

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

пожалуйста помогите доказать ну ОЧЕНЬ НАДА!!! Я думаю для вас это 5 мин времени а я буду сто лет розбиратся.
  #9  
Старый 24.05.2010, 17:19
гость

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

MBO привел вам доказательство, "възжайте" в него.

Цитата:
один хрен сумма площадей треугольников равна площади исходного многоугольника
это практически и все доказательство. что вам еще надо?
  #10  
Старый 24.05.2010, 17:42
гость

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

Спасибо большое Вы пролили свет в мою голову. это было доходчивое обяснение. Теперя точно понял почему алгоритм упростится
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Триангуляция/ректангуляция :-) полигона ekozhevnikov Вычислительная геометрия 3 17.06.2009 18:00
триангуляция по набору точек в 3D Максим Костин Графы 0 28.01.2009 20:30
Триангуляция поверхности в 3d гость Вычислительная геометрия 2 07.03.2008 15:34
n-мерная триангуляция Anna Математические алгоритмы 1 03.05.2007 19:36
триангуляция делоне Denich Математические алгоритмы 1 23.10.2006 17:07