Matematické Fórum

yellowzelo · 14. 03. 2011 15:04

Ahoj,
potreboval by som matematickú funkciu, ktorá mi vypočíta počet listov stromu nasledujúceho typu: http://www.sdilej.eu/pics/b3df0d51d2e07 … 899286.jpg

Na obrázku je nakreslený s parametrami:
max_branching = 4
deep = 3

Potrebujem to však pre ľubovoľné hodnoty max_branching a deep.

Ak by ste vedeli niekto s tým pomôcť bol by som veľmi vďačný.
Ďakujem.

musixx · 14. 03. 2011 15:51 — Editoval musixx (14. 03. 2011 17:00)

↑ yellowzelo: Bavme se o max_branch = 4, zobecnění je celkem vidět a nechám to na tobě (alespoň teda ten rekurentní tvar). Bavme se dále o

o
|
|
o

jako o jednolistu, o

o
/ \
/ \
o o

jako o dvoulistu, o

o
/ | \
/ | \
o o o

jako o trojlistu atd. (pro max_branch = 4 končíme zřejmě čtyřlistem).

Označme dále $S_c(i)$ počet $c$ -listů v i-tém patře stromu. Je tam celkem tedy $S_1(i)+S_2(i)+S_3(i)+S_4(i)$ uzlů v i-tém patře. Máme tedy dáno, že
$S_1(1)=0\\S_2(1)=0\\S_3(1)=0\\S_4(1)=1$ .
Pak si zbývá rozmyslet, proč
$S_1(n)=S_1(n-1)+S_2(n-1)+S_3(n-1)+S_4(n-1)$
$S_2(n)=S_2(n-1)+S_3(n-1)+S_4(n-1)$
$S_3(n)=S_3(n-1)+S_4(n-1)$
$S_4(n)=S_4(n-1)$

EDIT: Tak to tedy zkusme sečíst...
Pro $n>1$ tedy je
$S_4(n)=1$
$S_3(n)=S_3(n-1)+S_4(n)$
$S_2(n)=S_2(n-1)+S_3(n)$
$S_1(n)=S_1(n-1)+S_2(n)$
odkud
$S_3(n)=S_3(n-1)+1=n-1$
a proto
$S_2(n)=S_2(n-1)+n-1=\sum_{i=1}^{n-1}i=\frac{n(n-1)}2$
a proto
$S_1(n)=S_1(n-1)+S_2(n)=\sum_{j=1}^n\sum_{i=1}^{j-1}i=\frac{(n-1)n(n+1)}6$
odkud v n-tém patře je $\frac{n(n^2-1)}6+\frac{n(n-1)}2+(n-1)+1$ listů, tedy třeba lépe upraveno $\frac{n(n+1)(n+2)}6$ -- resp. EDIT2 a vlastně není co počítat...

EDIT2: Je snadné si rozmyslet, v jakém vztahu je $S_1(n)$ a počet uzlů v přechozím patře stromu (tato čísla jsou si rovna).

EDIT3: Myslím, že Marian tady o těch částečných součtech kdysi psal hezkou poznámku, ale nějak ji nemůžu najít. Třeba někdo doplní...

yellowzelo · 14. 03. 2011 16:40

Ďakujem.

A je možné prepísať dané rekurentné rovnice na nerekurentný tvar? Ak áno môžeš aspoň v skratke povedať ako?
Moje snahy o to zatiaľ stroskotali. :-)

musixx · 14. 03. 2011 16:50

↑ yellowzelo: Doplnil jsem svůj předchozí příspěvek...

Matematické Fórum

#1 14. 03. 2011 15:04

počet listov stromu

#2 14. 03. 2011 15:51 — Editoval musixx (14. 03. 2011 17:00)

Re: počet listov stromu

#3 14. 03. 2011 16:40

Re: počet listov stromu

#4 14. 03. 2011 16:50

Re: počet listov stromu

Zápatí