Forum@DeGiorgi :: Pogledajte temu - par zadataka s kolokvija (mog)

Search
Engleski Open in this window (click to change)

Forum za podršku nastavi na PMF-MO

par zadataka s kolokvija (mog)
WWW:

Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Diskretna matematika

Prethodna tema :: Sljedeća tema

Autor/ica

Poruka

saskvač
Forumaš(ica)

Pridružen/a: 06. 12. 2006. (22:05:44)
Postovi: (6)₁₆

Sarma	=	la pohva - posuda
1	=	1 - 0

Lokacija: Odjel za matematiku, OS

Postano: 22:36 čet, 7. 12. 2006 Naslov: par zadataka s kolokvija (mog)

Odredi broj svih monotonih f-ja sa skupa {1,2,3,....,n} u samog sebe. Pravokutnik dimenzija 2xn, n iz N, treba poplocati pravokutnicima dimenzija 2x1 i 2x2. Na kolko je to nacina moguce uciniti? bar koji hint..? :cry: Odredi broj svih monotonih f-ja sa skupa {1,2,3,....,n} u samog sebe. Pravokutnik dimenzija 2xn, n iz N, treba poplocati pravokutnicima dimenzija 2x1 i 2x2. Na kolko je to nacina moguce uciniti? bar koji hint..? _________________ Ne ide mi.

[Vrh]

Ignavia
Forumaš(ica)

Pridružen/a: 02. 10. 2004. (19:22:39)
Postovi: (235)₁₆
Spol: muško

Sarma	=	la pohva - posuda
91	=	108 - 17

Lokacija: prijestolnica

Postano: 22:48 čet, 7. 12. 2006 Naslov: Re: par zadataka s kolokvija (mog)

[quote="saskvač"]
Pravokutnik dimenzija 2xn, n iz N, treba poplocati pravokutnicima dimenzija 2x1 i 2x2. Na kolko je to nacina moguce uciniti?
[/quote]

to je onaj najtipicniji zadatak rekurzivni, mozda si krivo prepisao?
broj nacina na koji mozes poplocat pravokutnik duljine n ovisi o tome sto je zadnja plocica, ak je 2x1, onda mozes na f(n-1) nacina, a ak je 2x2, onda na f(n-2). znaci to su disjunktni slucajevi i pokupio si sve mogucnosti, pa imas rekurziju f(n)=f(n-1)+f(n-2)
jos pocetne uvjete:
f(1)=1 jer stane samo mala, i f(2)=2 jer mozes stavit ili dve male ili jednu velku

saskvač (napisa):

Pravokutnik dimenzija 2xn, n iz N, treba poplocati pravokutnicima dimenzija 2x1 i 2x2. Na kolko je to nacina moguce uciniti?

to je onaj najtipicniji zadatak rekurzivni, mozda si krivo prepisao?
broj nacina na koji mozes poplocat pravokutnik duljine n ovisi o tome sto je zadnja plocica, ak je 2x1, onda mozes na f(n-1) nacina, a ak je 2x2, onda na f(n-2). znaci to su disjunktni slucajevi i pokupio si sve mogucnosti, pa imas rekurziju f(n)=f(n-1)+f(n-2)
jos pocetne uvjete:
f(1)=1 jer stane samo mala, i f(2)=2 jer mozes stavit ili dve male ili jednu velku

_________________
moj prostor
Smoking

[Vrh]

Ignavia
Forumaš(ica)

Pridružen/a: 02. 10. 2004. (19:22:39)
Postovi: (235)₁₆
Spol: muško

Sarma	=	la pohva - posuda
91	=	108 - 17

Lokacija: prijestolnica

Postano: 23:05 čet, 7. 12. 2006 Naslov: Re: par zadataka s kolokvija (mog)

[quote="saskvač"]Odredi broj svih monotonih f-ja sa skupa {1,2,3,....,n} u samog sebe.
[/quote]

broj takvih funkcija je jednak broju uredjenih n-torki (a_1,...,a_n) t.d. za i<=j je a_i<=a_j
a sad pak te n-torke, broj takvih je jednak broju n-kombinacija s ponavljanjem n-clanog skupa, jer kad odaberes n-clani multiskup na skupu {1,2, ..., n} jednoznacno je odredjeno kak ces oblikovat svoju n-torku, iliti to je bijektivno pridruzivanje. znaci imas multiskup, i n-torku dobijes tako da za a_1 uzmes najmanji, onda za a_2 najmanji od preostalih itd.
e, sad broj tih n-clanih multiskupova na skupu od n elemenata je poznat -> (n+n-1 povrh n)=(2n-1 povrh n)

(jer opcenito je broj r-kombinacija s ponavljanjem n-clanog skupa jednak (n+r-1 povrh r) )

:disco:

saskvač (napisa):

Odredi broj svih monotonih f-ja sa skupa {1,2,3,....,n} u samog sebe.

broj takvih funkcija je jednak broju uredjenih n-torki (a_1,...,a_n) t.d. za i⇐j je a_i⇐a_j
a sad pak te n-torke, broj takvih je jednak broju n-kombinacija s ponavljanjem n-clanog skupa, jer kad odaberes n-clani multiskup na skupu {1,2, ..., n} jednoznacno je odredjeno kak ces oblikovat svoju n-torku, iliti to je bijektivno pridruzivanje. znaci imas multiskup, i n-torku dobijes tako da za a_1 uzmes najmanji, onda za a_2 najmanji od preostalih itd.
e, sad broj tih n-clanih multiskupova na skupu od n elemenata je poznat → (n+n-1 povrh n)=(2n-1 povrh n)

(jer opcenito je broj r-kombinacija s ponavljanjem n-clanog skupa jednak (n+r-1 povrh r) )

Disco

_________________
moj prostor
Smoking

[Vrh]

Prethodni postovi:

	Forum@DeGiorgi: Početna -> Kolegiji 2. godine -> Diskretna matematika	Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

Forum(o)Bir:

Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum