2019-gate-computer-science-and-it-practice.pdf/Q06-alg1 — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (→Вопрос: Q06-alg1-31d68c) |
||
| Строка 19: | Строка 19: | ||
* выбираем один узел как корневой (выбор рута — 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 | ||
Текущая версия на 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»