2019-gate-computer-science-and-it-practice.pdf/Q06-alg1 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
* Бинарное дерево — структура где у каждого узла, не больше двух потомков (левый и правый). | * Бинарное дерево — структура где у каждого узла, не больше двух потомков (левый и правый). | ||
| − | + | ;База рекурсии: пустое дерево, 0 узлов, одно. | |
| − | + | ;Рекурсия: Дерево на n-узлов делаем так | |
| − | + | * выбираем один узел как корневой (выбор рута — n вариантов) | |
| − | + | * дальше рекурсивно строим левое и правое дерево. | |
| − | + | ** Левое поддерево — выбор k-узлов <m>0 \leq k n-1</m>. | |
| − | + | ** Правое поддерево — оставшиеся n-1-k | |
| − | + | ||
| + | Получается рекурсивная формула <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 Чисел Каталана]. | ||
Версия 22:06, 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»