Počet koster žebříku

[Eubie]

Ahoj všem,
nemáte někdo prosím vás páru, jak se spočte počet min. koster žebříku na n vrcholech (nejlíp rekurzivní vzorec). Snažil jsem se na to přijít a ne a ne.

[Tresko]

Mali sme to na cvikach a ukazoval nam to takto:
Rebrik vyzera takto nejako:

Kód: Vybrat vše

---A----*-----*-----*----     ---*
   |    |     |     |            |
   |    |     |     |     ...    |
   |    |     |     |            |
---B----*-----*-----*----     ---*

- Rn bude rebrik s "n" horizontalnymi prieckami
- f(n) bude pocet kostier Rn
- g(n) bude poct pokryti Rn pomocou 2 kostier takych, ze A, B su v roznych kostrach

(to f(n) by malo byt skor f s dolnym indexom n, ale to by bolo neprehladne, preto som radsej zvolil f(n), aj ked je to stale postupnost!)

g(0) = 0 f(0) = 0
g(1) = 1 f(1) = 1
g(2) = 3 f(2) = 4

rekurencny vztah (kreslil nam aj obrazky, ale to sa mi momenalne nechce... ) vyjde takto
g(n+1) = g(n) + 2*f(n)
f(n+1) = g(n) + 3*f(n)

vytvarajuce funkcie:
g(x) = x*g(x) + 2x*f(x) + x
f(x) = x*g(x) + 3x*f(x) + x
----------------------------------
g(x) - f(x) = -x*f(x) // 1.rovnica - 2.rovnica
g(x) = (1-x) * f(x)

f(x) = x*(1-x)*f(x) + 3x*f(x) + x // dosadenie do 2.rovnice za g(x)
...
f(n) = A* (2+2*sqrt(3))^n + B*(2-2*sqrt(3))^n.

Snad to bude stacit...

[Eubie]

Díky!
Jen pro upřesnění, já myslel, že žebřík je tohle:
* --- * --- *
|
|
* --- * --- *
tj. musí mít všechny konce nespojený příčkou. Neví někdo přesnou definici? Internet je na tyhle definice poněkud skoupý.

[David Nohejl]

Pomuze to? http://mathworld.wolfram.com/LadderGraph.html

[Eubie]

No paráda, děkuju.

[Medved]

Cus.
Koukam koukam a neni mi moc jasne, co znamena to g(n). Prece A a B musi byt vzdycky v kazde kostre (kdyz je to kostra, tak tam jsou vsechny vrcholy). Jak je tedy mysleno, ze A a B jsou ve ruznych kostrach?

a proc treba g(1) = 1 a g(2) = 3?

Dik...

Mali sme to na cvikach a ukazoval nam to takto:
Rebrik vyzera takto nejako:

Kód: Vybrat vše

---A----*-----*-----*----     ---*
   |    |     |     |            |
   |    |     |     |     ...    |
   |    |     |     |            |
---B----*-----*-----*----     ---*

- Rn bude rebrik s "n" horizontalnymi prieckami
- f(n) bude pocet kostier Rn
- g(n) bude poct pokryti Rn pomocou 2 kostier takych, ze A, B su v roznych kostrach

[hippies]

pokryti dvema kostrama bych chapal jako kostra -1 hrana

[Medved]

Stejne mi to neni moc jasne, kde se tam ty cisla berou

[Xerxes]

Nedávno nám cvičící zadal tento problém jako domácí úlohu. Řešení (to, co jsem mu posílal na email) je v příloze. S prvním souborem jsem si docela vyhrál, ale dostal jsem odpověď, že rekurentní vzorec nestačí, tak jsem to (už docela narychlo) dopočítal pomocí VF... (thx Tresko, tvůj příspěvek mě postrčil - co se týče těch VF - správným směrem).

Netvrdím, že je to dobře, ale cvičící to (podle všeho) uznal a výsledný vzorec pro několik prvních n (ručně ověřeno pro 0 - 5) sedí...

P.S.: Pojem "pokrytí dvěma kostrami" mě nenapadl, místo něj jsem útvar nazval poněkud obludně a provizorně "skorokostra". Nejlepší názvy stejně vymyslel spolužák Ondra T., který používá pojmy "žebřík", "starý žebřík" a "rozpadlý žebřík" a celé zadání opředl úsměvným "příběhem". Nechceš sem své řešení poslat, Ondro?

kg_du3.pdf

Původní rekurentní vzorec

(33.46 KiB) Staženo 238 x

Převod na nerekurentní vzorec pomocí VF 1/2

Převod na nerekurentní vzorec pomocí VF 2/2