Форум программистов, компьютерный форум, киберфорум
Наши страницы

C++

Войти
Регистрация
Восстановить пароль
 
nika_pnika1
0 / 0 / 0
Регистрация: 25.11.2015
Сообщений: 3
#1

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

22.05.2016, 15:20. Просмотров 238. Ответов 1

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

Сортировка текста двумя методами - C++ Builder
Приветствую! Необходимо написать программу сортирующую слова по алфавиту, по возрастанию и убыванию(а-я, я-а) двумя методами - пузырька и...

Площадь выпуклого многоугольника - C++
Доброго времени суток! Собственно, задача звучит как: "Расчет площади выпуклого многоугольника при вводимых координатах вершин". ...

Центр тяжести выпуклого многоугольника - C++
Итак народ , необходимо найти центр тяжести выпуклого многоугольника заданного своими вершинами в порядке обхода по часовой стрелке ...

Площадь выпуклого многоугольника методом триангуляции - C++
ребят помогите разработать программу для расчёта площади выпуклого многоугольника методом триангуляции (разбиения на треугольники) по...

Найти все точки, являющиеся вершинами выпуклого многоугольника - C++
Дано: множество координат точек на плоскости  (х1, у1), (х2, у2), ..., (хn, уn)  - пары целых чисел. Составить алгоритм и написать...

Есть файл, в котором заданные координаты вершин выпуклого многоугольника на плоскости - C++
Есть файл, в котором заданные координаты вершин выпуклого многоугольника на плоскости. Написать программу, которая проверяет все введенные...

1
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4306 / 2325 / 574
Регистрация: 18.10.2014
Сообщений: 3,962
25.05.2016, 08:29 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Задача уже разбиралась здесь: Разбить выпуклый многоугольник на треугольники

Там же приводится и переборное решение, и решение методом ДП.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2016, 08:29
Привет! Вот еще темы с ответами:

Даны точки на плоскости: расположить их так, чтобы они образовывали вершины выпуклого многоугольника - C++
На плоскости заданы N точек своими декартовыми координатами. Расположить эти точки в таком порядке, чтобы они образовывали вершины...

Решение нелинейных уравнений двумя методами - C++
Нужно две программы , которые решают данное уравнение x^3+3x^2+6x-1=0 двумя способами: 1.Методом хорд 2.Методом простой итерации

Оптимальный раскрой - C++
Убийственная задача, которую я не только не могу решить, я её даже понять не могу)) Тема циклы, т.е. нужно использовать при решении только...

раскрой поверхности - C++
вот нашёл исходники в интернете подскажите на чём скомпилить это можно? посмотреть хочется.


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru