| Prethodna tema :: Sljedeća tema |
| Autor/ica |
Poruka |
grossi
Forumaš(ica)
Pridružen/a: 22. 04. 2004. (16:33:41)
Postovi: (5D)16
Spol: 
Lokacija: Delta Neretva
|
 Postano: 23:40 sub, 29. 5. 2004 Naslov: Rok 19.04.2004 |
    |
|
|
Nako duuuugog i uspjesnog padanja ispita odlucio sam prije sljedeceg pokusaja ipak rijesiti koji rok.
Imam dva zadatka koja mi nisu jasna.
1. rok 19.04.2004
Zad.5.
Neka je [b]n[/b] pozitivan cijeli broj veci od 1. Koliko ima permutacija
(a[size=7]1[/size],a[size=7]2[/size],...,a[size=7]n[/size]) brojeva 1,2,...,n tavih da postoji točno jedan indeks [i]i[/i] elementskupa(1,2,...n) za koji je a[size=9]i[/size]>a[size=9]i+1[/size]
Moje rjesenje:
:arrow: broj permutacija a[size=9]n[/size]= (n-1)*n/2 +1
2. Neki rok i moje vjezbe
Pustinjom putuje karavan od [b]n[/b] deva. Nakon oaze treba promijeniti redosljed deva tako da nijedna deva ne hoda iza one deve iza koje je hodala prije. NKN se to moze napraviti.
Moje rjesenje:
:arrow: D[size=9]n[/size] + D[size=9]n-1[/size]
gdje je Dn broj Deranzmana
__________________________
Hvala :?:
Nako duuuugog i uspjesnog padanja ispita odlucio sam prije sljedeceg pokusaja ipak rijesiti koji rok.
Imam dva zadatka koja mi nisu jasna.
1. rok 19.04.2004
Zad.5.
Neka je n pozitivan cijeli broj veci od 1. Koliko ima permutacija
(a1,a2,...,an) brojeva 1,2,...,n tavih da postoji točno jedan indeks i elementskupa(1,2,...n) za koji je ai>ai+1
Moje rjesenje:
 broj permutacija an= (n-1)*n/2 +1
2. Neki rok i moje vjezbe
Pustinjom putuje karavan od n deva. Nakon oaze treba promijeniti redosljed deva tako da nijedna deva ne hoda iza one deve iza koje je hodala prije. NKN se to moze napraviti.
Moje rjesenje:
Dn + Dn-1
gdje je Dn broj Deranzmana
__________________________
Hvala 
|
|
| [Vrh] |
|
Kova
Forumaš(ica)
Pridružen/a: 27. 02. 2004. (23:13:50)
Postovi: (4B)16
Spol:
|
| Postano: 2:08 ned, 30. 5. 2004 Naslov: |
|
|
|
[quote]*Pustinjom putuje karavan od n deva. Nakon oaze treba promijeniti redosljed deva tako da nijedna deva ne hoda iza one deve iza koje je hodala prije. NKN se to moze napraviti.*
[/quote]
Numeriras deve onako kako su bile poslozene prije oaze, nakon oaze prva deva ne smije hodati ispred druge, druga ispred trece itd.
Racunamo broj slaganja deva takvih da neki par ili neki parovi deva hodaju jedna iza druge, npr. zavezes devu za prethodnicu i tretiras kao jedan element karavane. Dakle racunamo broj rasporeda u kojima su neki podnizovi karavane ostali vezani jos od prethodne etape.
Uvedimo oznake
S- skup svih rasporeda deva
|A_1| skup svih rasporeda u kojima prva hoda ispred druge
|A_2| skup svih rasporeda u kojima druga deva hoda ispred trece
.
.
|A_n| skup svih rasporeda u kojima n-1 deva hoda ispred n-te
Ti trebas izracunati |A_1c presjek A_2c presjek... presjek A_nc|
imas da je |S|= n!
|A_i|=(n-1)! za svaki i
|A_i presjek A_j|=(n-2)! za svaki par razlicitih i, j
|A_i pres A_j pres...pres A_k|=1! za svaku (n-1)-torku razlicitih i,j,..,k
pa je rezultat |A_1c pres A_2c pres...pres A_nc|=n! - (n-1 povrh 1)*(n-1)! +(n-1 povrh 2)*(n-2)! - (n-1 povrh 3)*(n-3)! +...+(-1)^(n-1)*(n-1 povrh n-1)*1!
Napomena :!:
|A_1c| komplement skupa |A_1|
| Citat: | *Pustinjom putuje karavan od n deva. Nakon oaze treba promijeniti redosljed deva tako da nijedna deva ne hoda iza one deve iza koje je hodala prije. NKN se to moze napraviti.*
|
Numeriras deve onako kako su bile poslozene prije oaze, nakon oaze prva deva ne smije hodati ispred druge, druga ispred trece itd.
Racunamo broj slaganja deva takvih da neki par ili neki parovi deva hodaju jedna iza druge, npr. zavezes devu za prethodnicu i tretiras kao jedan element karavane. Dakle racunamo broj rasporeda u kojima su neki podnizovi karavane ostali vezani jos od prethodne etape.
Uvedimo oznake
S- skup svih rasporeda deva
|A_1| skup svih rasporeda u kojima prva hoda ispred druge
|A_2| skup svih rasporeda u kojima druga deva hoda ispred trece
.
.
|A_n| skup svih rasporeda u kojima n-1 deva hoda ispred n-te
Ti trebas izracunati |A_1c presjek A_2c presjek... presjek A_nc|
imas da je |S|= n!
|A_i|=(n-1)! za svaki i
|A_i presjek A_j|=(n-2)! za svaki par razlicitih i, j
|A_i pres A_j pres...pres A_k|=1! za svaku (n-1)-torku razlicitih i,j,..,k
pa je rezultat |A_1c pres A_2c pres...pres A_nc|=n! - (n-1 povrh 1)*(n-1)! +(n-1 povrh 2)*(n-2)! - (n-1 povrh 3)*(n-3)! +...+(-1)^(n-1)*(n-1 povrh n-1)*1!
Napomena 
|A_1c| komplement skupa |A_1|
_________________
kova
|
|
| [Vrh] |
|
grossi
Forumaš(ica)
Pridružen/a: 22. 04. 2004. (16:33:41)
Postovi: (5D)16
Spol:
Lokacija: Delta Neretva
|
| Postano: 10:24 ned, 30. 5. 2004 Naslov: |
|
|
|
Jeli moje rjesenje dobro, aj provjeri molim te.
Mislim da je ali bi mi dugo trebalo da objasnim postupak. uglavnom uspostavljam bijekciju s brojem permutacija bez fiksne točke, to je Dn, ali po tome ispada da prva ne smije biti iza zadnje, pa ih udruzimo u jednu devu i ispermutiramo bez fiksne tocke, to je Dn-1. po principu sume rjesenje je Dn+Dn-1
Neka mi netko objasni ako je moje rijesenje krivo, i zasto.
Hvala ti puno. :roll:
Jeli moje rjesenje dobro, aj provjeri molim te.
Mislim da je ali bi mi dugo trebalo da objasnim postupak. uglavnom uspostavljam bijekciju s brojem permutacija bez fiksne točke, to je Dn, ali po tome ispada da prva ne smije biti iza zadnje, pa ih udruzimo u jednu devu i ispermutiramo bez fiksne tocke, to je Dn-1. po principu sume rjesenje je Dn+Dn-1
Neka mi netko objasni ako je moje rijesenje krivo, i zasto.
Hvala ti puno. 
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
|
| [Vrh] |
|
grossi
Forumaš(ica)
Pridružen/a: 22. 04. 2004. (16:33:41)
Postovi: (5D)16
Spol:
Lokacija: Delta Neretva
|
|
| [Vrh] |
|
grossi
Forumaš(ica)
Pridružen/a: 22. 04. 2004. (16:33:41)
Postovi: (5D)16
Spol:
Lokacija: Delta Neretva
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
| Postano: 19:38 ned, 30. 5. 2004 Naslov: |
|
|
|
[quote="grossi"]jesi li pogledao prvi zadatak. Kako ti se on cini[/quote]
Cini mi se da si prebrojao transpozicije i jos nesto, a to nije dobro. Pogledaj npr. ovo:
2 3 6 8 1 4 5 7
Uspostavi bijekciju s podskupovima od {1,2,..,n}, s time da neke treba izbaciti. Odgovor je 2^n-n-1.
| grossi (napisa): | | jesi li pogledao prvi zadatak. Kako ti se on cini |
Cini mi se da si prebrojao transpozicije i jos nesto, a to nije dobro. Pogledaj npr. ovo:
2 3 6 8 1 4 5 7
Uspostavi bijekciju s podskupovima od {1,2,..,n}, s time da neke treba izbaciti. Odgovor je 2^n-n-1.
_________________
Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
| [Vrh] |
|
grossi
Forumaš(ica)
Pridružen/a: 22. 04. 2004. (16:33:41)
Postovi: (5D)16
Spol:
Lokacija: Delta Neretva
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
| Postano: 6:59 pon, 31. 5. 2004 Naslov: |
|
|
|
Jednostavno je. To su permutacije koje se na jednom mjestu "prelome". Lijevo od indeksa i brojevi rastu, a desno takodjer. Znaci, ako znas brojeve lijevo mozes jednoznacno rekonstruirati permutaciju (samo ih sortiras i nadopises preostale brojeve u rastucem redoslijedu). To je bijekcija izmedju podskupova i takvih permutacija, ali nisu svi podskupovi dobri. Treba izbaciti {}, {1}, {1,2}, ... {1,2,...,n} jer od njih dobijes jedinicnu permutaciju.
Jednostavno je. To su permutacije koje se na jednom mjestu "prelome". Lijevo od indeksa i brojevi rastu, a desno takodjer. Znaci, ako znas brojeve lijevo mozes jednoznacno rekonstruirati permutaciju (samo ih sortiras i nadopises preostale brojeve u rastucem redoslijedu). To je bijekcija izmedju podskupova i takvih permutacija, ali nisu svi podskupovi dobri. Treba izbaciti {}, {1}, {1,2}, ... {1,2,...,n} jer od njih dobijes jedinicnu permutaciju.
_________________
Vedran Krcadinac
Ljudi su razliciti, a nula je paran broj.
|
|
| [Vrh] |
|
grossi
Forumaš(ica)
Pridružen/a: 22. 04. 2004. (16:33:41)
Postovi: (5D)16
Spol:
Lokacija: Delta Neretva
|
|
| [Vrh] |
|
krcko
Forumaš nagrađen za životno djelo
Pridružen/a: 07. 10. 2002. (15:57:59)
Postovi: (18B3)16
|
|
| [Vrh] |
|
|
