Обсуждение:Дискретная математика, алгоритмы и структуры данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Числа Каталана: Новая тема)
(→‎Задача разбиения выпуклого $n$-угольника на треугольники не пересекающимися диагоналями)
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
 
Комбинаторику и, наверное, сортировки хочется разбить на подразделы. Вот только как бы это разумно сделать?
 
Комбинаторику и, наверное, сортировки хочется разбить на подразделы. Вот только как бы это разумно сделать?
 
: Сортировки разбиты. Вероятно, стоит ещё динамическое программирование разбить на разделы, да и вообще так имеет смысл поступать с любым достаточно большим разделом [[Участник:Shersh|Дмитрий Коваников]] 18:28, 26 сентября 2014 (GST)
 
: Сортировки разбиты. Вероятно, стоит ещё динамическое программирование разбить на разделы, да и вообще так имеет смысл поступать с любым достаточно большим разделом [[Участник:Shersh|Дмитрий Коваников]] 18:28, 26 сентября 2014 (GST)
−
 
−
== Числа Каталана ==
 
−
 
−
<wikitex>
 
−
{{Определение
 
−
|id = def1
 
−
|definition =Числа Каталана {{---}} последовательность чисел, выражающих:
 
−
*количество не изоморфных упорядоченных бинарных деревьев с корнем и $n + 1$ листьями;
 
−
*количество способов соединения $2n$ точек на окружности $n$ не пересекающимися хордами;
 
−
*количество разбиений выпуклого $n$-угольника на треугольники не пересекающимися диагоналями;
 
−
*количество способов полностью разделить скобками $n + 1$ множитель;
 
−
*количество корректных скобочных последовательностей, состоящих из $n$ открывающих и $n$ закрывающих скобок;}}
 
−
 
−
Первые несколько чисел Каталана:
 
−
 
−
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, ...
 
−
</wikitex>
 
−
==Задача разбиения выпуклого $n$-угольника на треугольники не пересекающимися диагоналями==
 
−
<wikitex>
 
−
Ответ на задачу при $n$ = 3 тривиален: никаких
 
−
диагоналей проводить не надо. В четырёх угольнике можно провести любую из
 
−
двух диагоналей, так что способов два. В пятиугольнике — из любой вершины две
 
−
диагонали, 5 способов. При $n$ = 6 — первый не вполне очевидный ответ: 14 способов (см. рис.); чтобы
 
−
не запутаться, сторона BC выделена и отдельно нарисованы разрезания, в которых
 
−
к ней примыкают соответственно треугольники $BCA$, $BCF$, $BCE$ и $BCD$.
 
−
 
−
Рассмотрим выпуклый $n$-угольник, разрезанный диагоналями на треугольники. Легко доказать, что количество диагоналей проведенных из одной вершины равно $n$−3.
 
−
</wikitex>
 

Текущая версия на 02:18, 17 октября 2014

Комбинаторику и, наверное, сортировки хочется разбить на подразделы. Вот только как бы это разумно сделать?

Сортировки разбиты. Вероятно, стоит ещё динамическое программирование разбить на разделы, да и вообще так имеет смысл поступать с любым достаточно большим разделом Дмитрий Коваников 18:28, 26 сентября 2014 (GST)
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Обсуждение:Дискретная_математика,_алгоритмы_и_структуры_данных&oldid=40385»