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

Индукция. Дан выпуклый n угольник (заданный координатами своих вершин в порядке обхода). - C++

Восстановить пароль Регистрация
 
Fylhtq1997
 Аватар для Fylhtq1997
110 / 33 / 4
Регистрация: 31.03.2012
Сообщений: 81
31.03.2012, 23:22     Индукция. Дан выпуклый n угольник (заданный координатами своих вершин в порядке обхода). #1
Пожалуйста напешите программу на С ++:
Дан выпуклый n угольник (заданный координатами своих вершин в порядке обхода). Его разрезают на треугольники диагоналями, для чего необходимо п -3 диагонали. Стоимостью разрезания назовем сумму длин всех использованных диагоналей. Найти минимальную стоимость разрезания
Спасибо!

Добавлено через 3 часа 17 минут
Алгоритм этой задачи такой, а как его написать на С++:
Решение: Будем считать, что вершины пронумерованы от 1 до n и идут по часовой стрелке. Пусть k, l - номера вершин, причем l>k. Через A(k,l) обозначим многоугольник, отрезаемый от нашего хордой k--l. (Эта хорда разрезает многоугольник на 2, один из которых включает сторону 1--n; через A(k,l) мы обозначаем другой.) Исходный многоугольник естественно обозначить A(1,n). При l=k+1 получается "двуугольник" с совпадающими сторонами.
Через a(k,l) обозначим стоимость разрезания многоугольника A(k,l) диагоналями на треугольники. Напишем рекуррентную формулу для a(k,l). При l=k+1 получается двуугольник, и мы полагаем a(k,l)=0. При l=k+2 получается треугольник, и в этом случае также a(k,l)=0. Пусть l > k+2. Хорда k--l является стороной многоугольника A(k,l) и, следовательно, стороной одного из треугольников, на которые он разрезан. Противоположной вершиной i этого треугольника может быть любая из вершин k+1,...,l-1, и минимальная стоимость разрезания может быть вычислена как
min {(длина хорды k--i)+(длина хорды i--l)+a(k,i)+a(i,l)}
по всем i=k+1,..., i=l-1. При этом надо учесть, что при q=p+1 хорда p--q - не хорда, а сторона, и ее длину надо считать равной 0 (по стороне разрез не проводится).
Составив таблицу для a(k,l) и заполняя ее в порядке возрастания числа вершин (равного l-k+1), мы получаем программу, использующую память порядка n*n и время порядка n*n*n (однократное применение рекуррентной формулы требует выбора минимума из не более чем n чисел).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.03.2012, 23:22     Индукция. Дан выпуклый n угольник (заданный координатами своих вершин в порядке обхода).
Посмотрите здесь:

Два треугольника заданы координатами своих вершин. Вычислить их площади C++
C++ Треугольник задается координатами своих вершин. С++
C++ Найти площадь треугольника заданного координатами своих вершин
C++ Треугольник задан координатами своих вершин. Найти (выдает ошибку)
C++ Является ли четырехугольник, заданный координатами вершин, прямоугольником
C++ Функции: найти высоты треугольника, заданного координатами своих вершин
Создать класс 4-угольник, заданный координатами вершин. Определить производные классы трапеция и треугольник C++
C++ Создать класс 4-угольник, заданный координатами вершин. Определить производные классы трапеция и треугольник

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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