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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Добавление в хип http://www.cyberforum.ru/cpp-beginners/thread535424.html
Правильно ли я написал добавление в хип? #include <iostream> using namespace std; class heap { private: int *mas; int size,maxsize; public: heap() { mas=new int; size=0; maxsize=10;...
C++ Шифрование методом Вижинера Ребята помогите пожалуйста, может у кого-то завалялся исходный код этой программки или похожий, тема довольно распространенная, но мне нужно шифрование с подключением исходный файлов и вводом ключа.... http://www.cyberforum.ru/cpp-beginners/thread535417.html
C++ Процессы и потоки (функция GetProcess)
вот код навороченого диспетчера процессов, OpenThread выдаёт ошибку , почему ? #include "stdafx.h" #include <cstdlib> #include <iostream> #include "windows.h" #include "winbase.h" #include...
C++ Работа с потоками winapi
Как корректней работать с потоками? Я сделал так: Запускаем поток HANDLE myrobo; myrobo=CreateThread(NULL, 0, MyroboThread, NULL, 0, NULL); DWORD WINAPI MyroboThread(LPVOID) { Robo *r =...
C++ Вывод числа double из консоли в Messagebox http://www.cyberforum.ru/cpp-beginners/thread535392.html
"Осуществить заданные в командной строке арифметические действия (сложение и вычитание) над целыми числами и вывести в простейшее диалоговое окно (MessageBox) получившийся результат, либо сообщение...
C++ Запись текста в файл txt Здравствуйте , подскажите как реализовать запись в файл, у меня что то не получается har name; puts("Введите термин:"); cin>>name; strcat(name,".txt"); fstream f;... подробнее

Показать сообщение отдельно
Fylhtq1997
110 / 33 / 4
Регистрация: 31.03.2012
Сообщений: 81

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

31.03.2012, 23:22. Просмотров 799. Ответов 0
Метки (Все метки)

Пожалуйста напешите программу на С ++:
Дан выпуклый 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 чисел).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru