2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Задача на деревья и думаю DP
Сообщение31.05.2014, 09:37 
Задача звучит так:
Фермер Джон хочет купить стадо коров. В новом стаде каждая корова
родит ровно 2х коровят ). Родственные связи между коровами могут
быть легко продемонстрированы бинарным деревом с N вершинами. Эти
деревья обладают таким свойством:
1. Степень каждой вершины 0 или 2. Степень - это количество непосредственных потомков.
2. Высока дерева ровно K. Высота это максимальное количество узлов из корня до листьев.
Листья это вершины у которых нет детей.

Сколько сущесвует разных деревьев у которых N вершин, и высота которых равна K. Деревья
различаются по структуре.
Например:
При N=5 и K=3, ответ равен 2.
Изображение


Не знаю как подобраться к задаче.
Пробовал решать перебором, строил по очереди деревья, но получилось
очень очень медленно.

 
 
 
 Re: Задача на деревья и думаю DP
Сообщение31.05.2014, 20:06 
Аватара пользователя
Да, это динамика. Вспомните, как решается задача о количестве правильных скобочных последовательностей динамически. Сначала мы ищем кол-во правильных скобочных последовательностей длины до $(2n - 2)$ включительно, а затем перебираем положения первой открывающей и соответствующей ей закрывающей скобке и подсчитываем ответ для $2n$.

То что я написал нужно приспособить к деревьям и понять, как подсчитать деревья не любой высоты, а только заданной.

 
 
 
 Re: Задача на деревья и думаю DP
Сообщение01.06.2014, 07:36 
Да, точно ведь дерево можно представить как скобочную последовательность.
Тогда, кажется, деревья из примера будут в виде:

$( ( ( ) ( ) ) ( ) )$

$( ( ) ( ( ) ( ) ) )$

Значит надо посчитать точное количество разных скобочных последовательностей
c 2N скобками, где максимальная вложенность равна K?

 
 
 
 Re: Задача на деревья и думаю DP
Сообщение01.06.2014, 10:49 
Аватара пользователя
Не совсем так, ибо, хотя бы насколько я понял, коров всегда нечетное число, а скобок всегда четное. Во-вторых, если уж так рассуждать, то первой открывающей должна соответствовать последняя скобка, иначе будут коровы, не являющиеся потомками первой.
Не пытайтесь в программировании мыслить как математик. Не нужно сводить задачу к уже решенной, как в математике. Так вы не постигните дзена DP. Есть общие приемы, которые стоит усвоить, а далее идет индивидуальная специфика каждой задачи.

Я подсказал вам, что нужно думать аналогично. Насчет отслеживания глубины деревьев - тут как вы организуете динамику. Мне представляется, что ответ будет лежать в $k$-ой ячейке таблицы динамики, т.е. нужно считать не просто "сколько правильных деревьев я могу построить", а "сколько правильных деревьев глубины $m$ я могу построить". Да, работать это будет медленней, но что-то вы с ограничениями задачи промолчали.

 
 
 
 Re: Задача на деревья и думаю DP
Сообщение01.06.2014, 13:39 
Ограничения на входные данные
$2 < N < 200$

$1 < K <100$

 
 
 
 Re: Задача на деревья и думаю DP
Сообщение01.06.2014, 17:41 
Аватара пользователя
Нормально, у меня получается оценка $O(N^2K)$, что обычные компьютеры считают в пределах одной секунды.

 
 
 
 Re: Задача на деревья и думаю DP
Сообщение07.12.2014, 15:29 
Foxer в сообщении #870589 писал(а):
Нормально, у меня получается оценка $O(N^2K)$, что обычные компьютеры считают в пределах одной секунды.

Спасибо, у меня тоже получилось )

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group