Ahoj, mam pro vas takovy pekny prikladecek, nad kterem se muzete ve volnych chvilich rozmyslet, pripadne muzeme pristi hospodu ci jine setkani to zkusit vyresit ;)
Mejme kruh a na nej postupne pridavame body. Kazdy bod spojime s kazdym dalsim bodem na kruhu, cimz rozdelujeme kruh na casti. Body umistujeme tak, aby se nam v jednom bode krizily maximalne 2 cary. Spocitejme pocet casti, pokud umistime n bodu + postup.
Konkretne:
1 bod..... 1 cast
2 body... 2 casti
3 body... 4 casti
4 body... 8 casti
5 bodu... 16 casti
6 bodu.......31 casti (HA! mysleli jste ze 32, co? :P )
n bodu...... x casti
(Prikladam obrazek pro 6 bodu)
Takze v hospode jsme tento problem probrali ze vsech stran ;) Ale byli jsme schopni dojit pouze k rekurentnimu vzorecku, kdy jsme spocitali, kolik pribyde casti, kdyz se ke k stavajicich prida jeden bod.
OdpovědětVymazatVzorecek vychazel z myslenky, ze z (k+1). bodu vychazi k car, ktere protinaji stavajici cary a spocitali jsme, kolik tech pruseciku je + pripocetli k tomu jeste k, protoze u kazde nove cary vznikla nova cast se stenou kruznice, at uz se to nekde protlo nebo ne.
Rekurentni vzorecek z toho tedy vysel
k car....... P(k) casti
k+1 car..... P(k) + k + P(novych pruseciku)
Nerekurentni reseni je velmi jednoduche a pruzracne jasne, ale vyzaduje dva myslenkove skoky :)
0. myslenkovy skok => ono k vyjadruje pocet novych car (to je ten lehci skok, tak se nepocita ;)
Novy rekurentni vzorecek je
P(k) = P(k-1) + P(novych car) + P(novych pruseciku)
1. myslenkovy skok => u P(k-1) je to to same v blede ruzovem, cili to mohu postupne nahrazovat
P(k) = P(k-2) + P(novych car pro k-1) + P(novych pruseciku pro k-1) + P(novych car) + P(novych pruseciku)
...atd
cili vidime (dukaz je triviali a ponecham jako domaci cviceni!), ze vlastne
P(k) = P(vsech car) + P(vsech pruseciku) + 1
(ta jednicka je tam z toho duvodu, ze mame jednu cast pro 0 i 1 bodu a da se tam zpetne pridat, je to vlastne osetreni chovani se naseho vzorecku uplne na zacatku)
Ted uz je to jen o tom, jak spocitat pocet vsech car a vsech pruseciku na kruhu, kde mame n bodu.
P(vc) -> kazda (prave jedna) cara je jednoznacne dana prave dvema body, tj. = (n nad 2)
P(vp) -> 2. myslenkovy skok je, ze kazdy (prave jeden) prusecik je jednoznacne dan prave 4 bodama (nakreslete si to), tj. = (n nad 4)
tedy: P(n) = (n nad 2) + (n nad 4) + 1
Jednoduche, ze? ;)
tak uz jsem to vzdala (konecne;) a koukla se na to vase slavne reseni;)
OdpovědětVymazat-tak prvni myslenkovy skok bych zvladla
- n nad 2 se tam taky naslo
- ale 2. myslenkovy skok, to uz jsem sama skocit nezvladla....kdyz ja tam mela takovou krasnou sumu..;)
...hlavne ze ted uz muzu klidne spat;)
esta