Алгоритм динамического программирования - PullRequest
Новая
       29

Алгоритм динамического программирования

0 голосов
/ 10 ноября 2011

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

R (м) / 2 <= L (м) <= 2 * R (м), </p>

где L (m) - количество узлов в левом поддереве m, а R (m) - количество узлов в правом поддереве m.

(a) Напишите рекуррентное соотношение для подсчета числа полубалансных бинарных деревьев с N узлы.

(b) Предоставить алгоритм динамического программирования для вычисления повторения в (a).

Как мне сделать рекуррентное соотношение для этого?

Имеет ли право следующее: 

if(node==NULL)
return;
if(given relation is true)
count++
else find for right tree;
     find for left tree;

Полагаю, он просит больше о рекуррентном отношении, например, функции или что-то в этом роде .?

Кроме того, как мне решить проблему с помощью динамического программирования? Полагаю, мне не нужно ничего хранить, если я применил приведенный выше фрагмент кода.

Пожалуйста, помогите.

1 Ответ

0 голосов
/ 11 ноября 2011

Подсказка: Пусть C(n) будет числом полубалансных деревьев с n узлами. Если вам известны значения для C(1), C(2), ..., C(n), то легко вычислить C(n+1), взяв корневой узел и разделив оставшиеся узлы n на левое и правое поддеревья по указанному условию.

Количество узлов в поддеревьях может быть от n/3 до 2*n/3, так как эти значения удовлетворяют условию R(n)/2 <= L(n) <= 2*R(n).

Обновление:

C(n) = sum from n/3 to 2n/3 L(n)*R(n)

...