Обсуждение:Дискретная математика, алгоритмы и структуры данных — различия между версиями
Novik (обсуждение | вклад) (→Числа Каталана: Новая тема) |
Novik (обсуждение | вклад) (→Числа Каталана) |
||
| Строка 2: | Строка 2: | ||
: Сортировки разбиты. Вероятно, стоит ещё динамическое программирование разбить на разделы, да и вообще так имеет смысл поступать с любым достаточно большим разделом [[Участник:Shersh|Дмитрий Коваников]] 18:28, 26 сентября 2014 (GST) | : Сортировки разбиты. Вероятно, стоит ещё динамическое программирование разбить на разделы, да и вообще так имеет смысл поступать с любым достаточно большим разделом [[Участник:Shersh|Дмитрий Коваников]] 18:28, 26 сентября 2014 (GST) | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Задача разбиения выпуклого $n$-угольника на треугольники не пересекающимися диагоналями== | ==Задача разбиения выпуклого $n$-угольника на треугольники не пересекающимися диагоналями== | ||
<wikitex> | <wikitex> | ||
Версия 02:17, 17 октября 2014
Комбинаторику и, наверное, сортировки хочется разбить на подразделы. Вот только как бы это разумно сделать?
- Сортировки разбиты. Вероятно, стоит ещё динамическое программирование разбить на разделы, да и вообще так имеет смысл поступать с любым достаточно большим разделом Дмитрий Коваников 18:28, 26 сентября 2014 (GST)
Задача разбиения выпуклого $n$-угольника на треугольники не пересекающимися диагоналями
<wikitex> Ответ на задачу при $n$ = 3 тривиален: никаких диагоналей проводить не надо. В четырёх угольнике можно провести любую из двух диагоналей, так что способов два. В пятиугольнике — из любой вершины две диагонали, 5 способов. При $n$ = 6 — первый не вполне очевидный ответ: 14 способов (см. рис.); чтобы не запутаться, сторона BC выделена и отдельно нарисованы разрезания, в которых к ней примыкают соответственно треугольники $BCA$, $BCF$, $BCE$ и $BCD$.
Рассмотрим выпуклый $n$-угольник, разрезанный диагоналями на треугольники. Легко доказать, что количество диагоналей проведенных из одной вершины равно $n$−3. </wikitex>
