2019-gate-computer-science-and-it-practice.pdf/Q06-alg1 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(→‎Вопрос: Q06-alg1-31d68c)
 
(не показана одна промежуточная версия этого же участника)
Строка 15: Строка 15:
 
* Бинарное дерево — структура где у каждого узла, не больше двух потомков (левый и правый).
 
* Бинарное дерево — структура где у каждого узла, не больше двух потомков (левый и правый).
  
−
* База рекурсии — пустое дерево, 0 узлов, одно.
+
;База рекурсии: пустое дерево, 0 узлов, одно.
−
* **Рекурсия**: Дерево на n-узлов делаем так
+
;Рекурсия: Дерево на n-узлов делаем так
−
** выбираем один узел как корневой (выбор рута — n вариантов)
+
* выбираем один узел как корневой (выбор рута — n вариантов)
−
** дальше рекурсивно строим левое и правое дерево.
+
* дальше рекурсивно строим левое и правое дерево.
−
*** Левое поддерево — выбор k-узлов  <m>0 \leq k n-1</m>.
+
** Левое поддерево — выбор k-узлов  <m>0 \leq k \leq n-1</m>.
−
*** Правое поддерево — оставшиеся n-1-k
+
** Правое поддерево — оставшиеся n-1-k
−
* получается рекурсивная формула <m>
+
 
 +
Получается рекурсивная формула <m>
 
C_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k}
 
C_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k}
 
</m>, совпадающая с определением [https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 Чисел Каталана].
 
</m>, совпадающая с определением [https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9A%D0%B0%D1%82%D0%B0%D0%BB%D0%B0%D0%BD%D0%B0 Чисел Каталана].

Текущая версия на 23:16, 24 декабря 2024

Вопрос: Q06-alg1-31d68c

Сколько существует различных бинарных деревьев с 8 узлами?

Ответы

  • 256
  • 128
  • Правильный ответ: 248
  • 64

Объяснение

Непонятно.

Обычно число бинарных деревьев выводится через Числа Каталана.

  • Бинарное дерево — структура где у каждого узла, не больше двух потомков (левый и правый).
База рекурсии
пустое дерево, 0 узлов, одно.
Рекурсия
Дерево на n-узлов делаем так
  • выбираем один узел как корневой (выбор рута — n вариантов)
  • дальше рекурсивно строим левое и правое дерево.
    • Левое поддерево — выбор k-узлов .
    • Правое поддерево — оставшиеся n-1-k

Получается рекурсивная формула , совпадающая с определением Чисел Каталана.

Но тут в ответе явно ждут формулу (как она выводится?), которая бьется до 4 с числами каталана, но начиная с 5 — расходится.

Исходники — вопрос 6 на 219 странице книги «2019-gate-computer-science-and-it-practice.pdf»

Источник — «https://discopal.ispras.ru/index.php?title=2019-gate-computer-science-and-it-practice.pdf/Q06-alg1&oldid=34899»