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.
Jak w ogóle zabrać sie za to zadanie, czy tutaj ma znaczenie wysokość tego drzewa ?
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.
sorry te równanie miało wylglądać tak:
T(h, k) = {1 dla n = 1
{T(h-1, k)k dla n >= 2
Bardzo mi pomogłeś, z tymi przypadkami. Kompletnie o nich zapomniałem.
Wielkie dzięki