[struktury] Rekurencja dla drzewa

0

Jest takie zadanie:

Niech T(h,k) będzie maksymalną liczba liści drzewa o wysokości h, gdzie każdy węzeł ma dzieci w liczbie k lub mniejszej.
1) Znajdź równanie rekurencyjne dla T(h,k)
2) Rozwiąż je dwoma sposobami

Jak w ogóle zabrać sie za to zadanie, czy tutaj ma znaczenie wysokość tego drzewa ?

0

Wysokość drzewa ma jak najbardziej znaczenie. Równanie rekurencyjne mogłoby wyglądać tak:

T(h, k) = {1 dla n = 1
{T(h-1, k) dla n >= 2

Nie mam pojęcia jak się rozwiązuje rekurencyjne równania, ale łatwo zauważyć po prostu że ilość wierzchołków jest opisaną zależnością: T(h, k) = k^(h-1)
Od razu mówię, że jakimś wielkim specjalistą nie jestem ale mam nadzieje że cię chociaż naprowadziłem na właściwe rozwiązanie.

0

sorry te równanie miało wylglądać tak:
T(h, k) = {1 dla n = 1
{T(h-1, k)k dla n >= 2

0

Bardzo mi pomogłeś, z tymi przypadkami. Kompletnie o nich zapomniałem.
Wielkie dzięki

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0