Форум программистов, компьютерный форум CyberForum.ru

Раскрой выпуклого многоугольника двумя методами С++ - C++

Восстановить пароль Регистрация
 
nika_pnika1
0 / 0 / 0
Регистрация: 25.11.2015
Сообщений: 3
22.05.2016, 15:20     Раскрой выпуклого многоугольника двумя методами С++ #1
Помогите перваку с курсачем по АСА
Раскрой выпуклого многоугольника на треугольники методом полного перебора и методом динамического программирования.
Т.е. Нужно найти минимальную стоимость разреза многоугольника на треугольники(минимальную сумму длин не пересекающихся диагоналей)
Метод полного перебора заключается в том, чтобы перебрать все возможные варианты и
выбрать наилучший. Этот метод всегда позволяет вычислить оптимальное решение, а также
определить все возможные оптимальные решения, если их несколько.
Однако этот метод обладает очень большой временной сложностью.
Динамическое программирование — это метод решения оптимизационных задач, в
результате которого основная задача разбивается на множество пересекающихся подзадач.
Под пересекающимися задачами здесь понимается пересекающееся условие.
При этом в алгоритмах динамического программирования одна и та же задача не должна
решаться дважды. Решение задачи записывается, и потом используется, если оно
необходимо.
Динамическое программирование — это решение задач с использованием дополнительной
памяти (хранятся промежуточные решения).
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.05.2016, 15:20     Раскрой выпуклого многоугольника двумя методами С++
Посмотрите здесь:

Площадь выпуклого многогранника методом триангуации по формуле Герона C++
C++ Builder Сортировка текста двумя методами
C++ Оптимальный раскрой
C++ раскрой поверхности
C++ Написать программу для вычисления площади выпуклого
Подскажите пожалуйста по программе для вычисления площади выпуклого четырехугольника C++
C++ Решение нелинейных уравнений двумя методами
C++ Вычислить площадь выпуклого четырёхугольника ABCD
Даны точки на плоскости: расположить их так, чтобы они образовывали вершины выпуклого многоугольника C++
Площадь выпуклого многоугольника методом триангуляции C++
C++ Центр тяжести выпуклого многоугольника
Найти все точки, являющиеся вершинами выпуклого многоугольника C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TheCalligrapher
С чаем беда...
Эксперт С++
 Аватар для TheCalligrapher
3121 / 1561 / 423
Регистрация: 18.10.2014
Сообщений: 2,886
25.05.2016, 08:29     Раскрой выпуклого многоугольника двумя методами С++ #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Задача уже разбиралась здесь: Разбить выпуклый многоугольник на треугольники

Там же приводится и переборное решение, и решение методом ДП.
Yandex
Объявления
25.05.2016, 08:29     Раскрой выпуклого многоугольника двумя методами С++
Ответ Создать тему

Метки
c++, триангуляция
Опции темы

Текущее время: 19:51. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru