| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Помогите с реализацией алгоритма в код |
| Автор: AlonZo 28.10.2005, 20:55 |
| Условие: Перечислить все способы разрезать n-угольник на треугольники, проведя n - 2 его диагонали. Вершины пронумерованы. Нашёл алгоритм,который похож на нужный мне, но код по нему не знаю как написать (ламмер я! :-) ): Дан выпуклый n-угольник (заданный координатами своих вершин в порядке обхода). Его разрезают на треугольники диагона- лями, для чего необходимо n-2 диагонали (докажите индукцией по n). Стоимостью разрезания назовем сумму длин всех использованных диагоналей. Найти минимальную стоимость разрезания. Число действий должно быть ограничено некоторым многочленом от n. (Пе- ребор не подходит, так как число вариантов не ограничено многоч- леном.) Решение. Будем считать, что вершины пронумерованы от 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. При этом надо учесть, что при i=k+1 хорда k--i - не хорда, а сторона, и ее длину надо считать равной 0 (по стороне разрез не проводится). Составив таблицу для a(k,l) и заполняя ее в порядке возрас- тания числа вершин (равного l-k+2), мы получаем программу, ис- пользующую память порядка n*n и время порядка n*n*n (однократное применение рекуррентной формулы требует выбора минимума из не более чем n чисел). |
| Автор: eskaflone 5.11.2005, 22:08 | ||
приведенный алгоритм находит не количество разбиений ,а стоимость минимального разбиения (сумма длин диагоналей)
количество разбиений равно сумме количества разбиений когда из первой вершины проведены хорды во все вершины от 3 до n - 1 плюс количество разбиений когда из первой вершины не проведено ни одной хорды. ЗЫ проверьте пожалуйста все ли учтено в формуле. |