Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Raspored vojnika

[es] :: Matematika :: Raspored vojnika

Strane: 1 2

[ Pregleda: 4112 | Odgovora: 23 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

miki069

Član broj: 161528
Poruke: 1951
*.dynamic.sbb.rs.



+370 Profil

icon Raspored vojnika11.02.2017. u 22:47 - pre 86 meseci
Imamo 20 vojnika.
Svi vojnici su različite visine.
Treba ih rasporediti u dve vrste sa po 10 vojnika (komanda u JNA je bila "u dve vrste Zbor!").
Svaki vojnik iz prve vrste mora biti niži od vojnika iza njega.
Na koliko načina se mogu rasporediti?

Vrtim se ceo dan bez ideje.


 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika12.02.2017. u 01:16 - pre 86 meseci
Da li je ovo problem sa projecteuler.net ili sličnog sajta?

Sada mi je malo suviše kasno da rešavam, a s obzirom da je tebi trebao ceo dan, čisto sumnjam da mogu noćas da ga rešim, ali evo kako bih ja rešio (odnosno pokušao da rešim).

Ono što je očigledno je da je broj rasporeda manji od 20! a veći od 10!
20! je broj permutacija 20 vojnika, ali nisu sve permutacije dozvoljene. Sada ću da objasnim zašto je veće od 10!

Postoji raspored (parova) vojnika takav da je prvi element para manji od drugog elementa para (a rešenje je (1,2), (3,4), ... (19,20) gde manji broj pretstavlja nižeg vojnika) pa je i svaki raspored parova koji je njihova permutacija rešenje problema, tako da postoji bar 10! rešenja.

Dakle, nađemo sva takva rešenja gde je prvi element prvog para manji od prvog elementa drugog para i tako do poslednjeg para.
Drugo ograničenje, pošto nečemo da tražimo sve permutacije uvek će skup parova biti sortiran po prvom elementu para.
Ovo je nešto što već može da se reši brute force metodom.

Iz skupa brojeva 1..20 uzeti minimalni element (1), i probati da li postoji rešenje za (1,2)...(1..20)
svaki put kada napravimo par, obrisati iz skupa brojeve koji smo uzeli i rešiti problem za k-2 elemenata.
Na kraju pomnožiti sa 10!

 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika12.02.2017. u 01:28 - pre 86 meseci
Možda može i bez programiranja.

Posmatrajmo niz od dvadeset različitih brojeva sortiran od najmanjeg do najvećeg.

Prvi par mora da ima minimalni element iz skupa kao prvi, a drugi može da bude bilo koji od preostalih brojeva, dakle 19 kombinacija.

rešenje je 10!*19*(broj rešenja za preostalih 18 brojeva)

U skupu od 18 brojeva, prvi par ima kao prvi element minimalni element, i bilo koji drugi od preostalih 17, znači ukupno 17 parcijalnih rešenja).

Na kraju ispada da je rešenje 10!*19*17*15*13*11*9*7*5*3*1=2375880867360000
(wolfram alpha mi je to izmnožio).
 
Odgovor na temu

Predrag Supurovic
Pedja YT9TP
Užice

Član broj: 157129
Poruke: 6275

Sajt: pedja.supurovic.net


+1570 Profil

icon Re: Raspored vojnika12.02.2017. u 07:59 - pre 86 meseci
Ovako na brzinu, ako se izuzmu situacije da dva ili više vojnika mogu biti iste visine, onda postoji samo jedan redosled: svi vojnici se poredjaju u jednu vrstu po visini a onda svaki drugi predje u drugu vrstu.
 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.



+2789 Profil

icon Re: Raspored vojnika12.02.2017. u 09:00 - pre 86 meseci
Podeli ih u 10 parova na proizvoljan način. Niži ide ispred, a viši iza.

Prvi par možeš izabrati na 20*19/2 načina. Oni će biti najlevlji.

Drugi par možeš izabrati na 18*17/2 načina.

I tako dalje.

Na kraju dobijaš 20!/2^10=2375880867360000.

To je isto što je i prethodnik napisao.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika12.02.2017. u 10:34 - pre 86 meseci
Elegantno, Nedeljko, nema šta!
Vidi se šta je matematičar. Ja sam problemu pristupio kao da je to nešto što treba da se isprogramira, pa sam razišljao o strukturama podataka i rekurzivnom algoritmu, a ti si ga pogodio pravo u centar
 
Odgovor na temu

anon115774

Član broj: 115774
Poruke: 1656



+920 Profil

icon Re: Raspored vojnika12.02.2017. u 13:02 - pre 86 meseci
Da ali to je pod pretpostavkom da ne postoje dva vojnika iste visine. A sta ako su svi potpuno iste visine? Onda postoji 0 nacina :)
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika12.02.2017. u 13:06 - pre 86 meseci
Pogledaj drugu rečenicu postavke zadatka:

Citat:
Svi vojnici su različite visine.

 
Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.ptt.rs.



+2789 Profil

icon Re: Raspored vojnika12.02.2017. u 19:59 - pre 86 meseci
djoka_l

Pa, sad, poklapa se sa tvojim.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika12.02.2017. u 21:03 - pre 86 meseci
To sam odgovorio Informeru na ovu primedbu:
Citat:
Informer: Da ali to je pod pretpostavkom da ne postoje dva vojnika iste visine. A sta ako su svi potpuno iste visine? Onda postoji 0 nacina :)
 
Odgovor na temu

miki069

Član broj: 161528
Poruke: 1951
*.dynamic.sbb.rs.



+370 Profil

icon Re: Raspored vojnika12.02.2017. u 21:34 - pre 86 meseci
Hvala puno.

Razumeo sam.


Zadatak je sa kolokvijuma.

Bivši Mašinski fakultet u Kragujevcu.
Sada Fakultet inžinjerskih nauka.
Novi smer.
Softversko inžinjerstvo.

Četvrti zadatak u prilogu.


[Ovu poruku je menjao miki069 dana 13.02.2017. u 06:52 GMT+1]
Prikačeni fajlovi
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.dynamic.sbb.rs.



+557 Profil

icon Re: Raspored vojnika13.02.2017. u 11:15 - pre 86 meseci
A može i ovako (pretpostavka): 20 vojnika se na 20 pozicija može rasporediti na 20! načina, bez obzira kako su te pozicije rasporedjene, razbacane, u jednoj liniji ili u dve vrste kao što se zahteva u zadatku, kako će vojnici biti rasporedjeni u dve vrste to možemo uočiti 10 parova od kojih se zahteva da uvek vojnik iz prve vrste u paru bude niži od vojnika iz druge vrste u paru, pošto baratamo sa 10 parova, i za sad imamo svih 20! načina rasporeda možemo one parove vojnika koji su se dobro rasporedili (niži u prvoj vrsti a viši u drugoj) da označimo sa 0 one parove koji su se rasporedili loše (viši u prvoj, niži u drugoj) sa 1, kada sad pogledamo dve vrste, tj, deset parova jasno je da se oni mogu rasporediti uzimajući u obzir orijentaciju parova kao i njihov položaj u samom stroju na 1024 različita načina jer 2^ 10= 1024 ( na primer ako su od deset parova 7 dobro okrenuti a samo neka tri kako ne treba to bi se vizuelno moglo predstaviti ovako: 0010001100 – dakle treći, sedmi I osmi par nam ne odgovara kako su stali) od kojih nama samo jedan način rasporeda odgovara a to je onaj kad su svih deset parova označeni sa 0 tj u svakom je niži vojnik u prvoj vrsti a viši u drugoj, I zbog toga pošto nam samo jedna kombinacija od mogućih 1024 odgovra: 20!/1024 = 2375880867360000 što se poklapa sa prethodna 2 rešenja.
Nemoj da pricas?
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.dynamic.sbb.rs.



+557 Profil

icon Re: Raspored vojnika13.02.2017. u 11:19 - pre 86 meseci
Edit: ekhm, ovaaaaaj…ja nešto uopšte nisam siguran da je ovo tačno rešenje iako sam dobio isti rezultat, i iako ima pridruženu neku kao logiku, ovo je više bilo kako obrazložiti dobijeni rezultat nego rešavanje jer: … rezultat je veći od 10! * 10! – kao kad bi podelili vojnike na dve grupe 10 nižih I deset viših i onda permutovali sve u svojim vrstama, dobro ovaj rezultat se uklapa I u ovaj uslov, ali sad kad počnem da prebacujem neke vojnike koji su prvobitno bili u drugoj vrsti u prvu max može 5 vojnika da bude I to ne uvek bilo kojih ako su na primer 16, 17 i 19 u prvoj vrsti to je nemoguća situacija jer 18 i 20 nije dovoljno da sva tri iz prve vrste budu pokrivena, a to nigde nemam u računici…
Na primer gde grešim ako ovako pokušam da rešim šaljući vojnike jedan po jedan u stroj a popunjavajući pozicije prvi u prvoj vrsti, pa prvi u drugoj vrsti, pa drugi u prvoj vrsti itd…:
Na prvu poziciju može da dodje bilo koji od 19 vojnika (samo ne može najvišlji on nikad ne može da bude u prvoj vrsti), na prvo mesto u drugoj opet 19 (sad može najvišlji, ali ne može više onaj što je već rasporedjen uprvu vrstu), preostaje 18 od kojih 17 može na tu poziciju i istom logikom 17 na drugu sve u svemu 19*19*17*17*15*15… itd … = 428670161650355625 što je veći rezultat nego do sada, ali i dalje manje od 20!

I na kraju ali ne najmanje važno: ja kao raspisivao nešto, deluje mi da postupak radi za 4 vojnika i za 6, a već za 8 ne radi, po ovoj dosadašnjoj računici trebalo bi da mogu da se rasporede na 2520 različitih načina a ja sam „prebrojao“ da mogu na 1728 načina koji zadovoljavaju uslov zadatka...? Dobro nisam baš brojao ali baš da fali oko 1000 kombinacija...?

I uopšte sav mi je ovaj zadatak nešto smutljiv ne mogu da se razaberem šta je tačno rešenje.


Nemoj da pricas?
 
Odgovor na temu

miki069

Član broj: 161528
Poruke: 1951
*.adsl.eunet.rs.



+370 Profil

icon Re: Raspored vojnika13.02.2017. u 13:41 - pre 86 meseci
Zadatak je kristalno jasan.

To što smo se ja i ti smutili pokušavajući da kombinujemo ko ide u prvu vrstu, pa da ih permutujemo, je naš problem.
Na taj način je zadatak nerešiv, jer se ne mogu permutovati u svim kombinacijama.
Mogu samo u nekim, a u nekima ne. Tako prebrojavanje je nemoguća misija.

Pogledaj Nedeljkovo rešenje.
Sve je kristalno jasno.

I Đokino rešenje je OK, ali je malo komplikovanije i teže za razumeti.


Zadatak na kolokvijumu nije bio sa 2*10 vojnika, nego 2*n vojnika.
Ali se lako generalizuje koristeći data rešenja.
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika13.02.2017. u 14:33 - pre 86 meseci
Tako je.
Nedeljkovo i moje rešenje je identično, osim što sam ga ja bespotrebno zakomplikovao sa permutacijama i sortiranjima.

Jasno je da je broj načina na koji PRVI par može da se izabere jednak broju kombinacija bez ponavaljanja 20 (2k) elemenata 2. klase. Drugi par je broj kombinacija bez ponavljanja 18 (2k-2) elemenata 2. klase. I tako dalje do poslednjeg para.

Kada se to lepo izmnoži, gore se lepo namesti 20! (odnosno (2k)!), a dole, u imeniocu 2^10 (odnosno 2^k).

Rešenje je, u opštem slučaju za 2k vojnika, (2k)!/2^k
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika13.02.2017. u 14:45 - pre 86 meseci
Uzgred, rešenje može da bude i "generalnije":

Na koliko načina može da se rasporedi kn vojnika u k vrsta tako da su vojnici ispred niži (viši) od onih iza, a rešenje je (kn)!/(k!)^n
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.dynamic.sbb.rs.



+557 Profil

icon Re: Raspored vojnika13.02.2017. u 20:25 - pre 86 meseci
Verujem ja vama al verujte i vi meni, na primer u rešenju koje sam predložio nedostaje ako su svi kontra postavljeni ali obe vrste gledaju na suprotnu stranu na primer sad prema poligonu umesto kao malopre prema izlazu iz kasarne onda ispada da su ponovo dobro postrojeni. Za 8 vojnika posle onih 4!*4! što je 576 kombinacija imaju situacije kad recimo spustiš 5 u prvu vrstu iza tog vojnika mogu biti 6, 7 ili 8 to je još 3 puta po 360 kombinacija i kad spustiš 6 ili 7 i zajedno 5 i 6 ili 5 i 7 (6 i 7 oba ne mogu u prvi red jer 8 ne može da se nadje iza obojice) to je još 3 * 24 kombinacije sve ukupno 1728 nema šansi da namaknem na 2520 koliko rešenje kaže da bi trebalo da bude...? Evo ne znam a voleo bih još nekako da mogu da proverim.
Nemoj da pricas?
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika13.02.2017. u 21:23 - pre 86 meseci
Veruj mi, druže majore, kombinacije bez ponavljanja eliminšu problem sortiranja. Ako kažeš da je nešto kombinacija 20 elemenata 2. klase, to je kao da od skupa od dvadeset elemenata izabereš sve podskupove sa dva elementa. A skupovi {a, b} i {b, a} su isti jer redosled nije važan.
 
Odgovor na temu

MajorFatal
Milija Jakic
opravljam oluke, 1337LAB
Bg

Član broj: 36595
Poruke: 1325
*.dynamic.sbb.rs.



+557 Profil

icon Re: Raspored vojnika13.02.2017. u 21:44 - pre 86 meseci
Pa nije važan kad biraš a vidiš da je ovde važan kad ih postrojiš, a ovi zadaci su mi klimavo postavljeni ili dozvoljavaju klimava rešenja jer ništa ne govore o orijentaciji odakle gledaš stroj i slično gde je isti okrenut itd... verovaću kad ispišeš 2520 kombinacija za 8 vojnika.

Gde je greška ovde? "Na primer gde grešim ako ovako pokušam da rešim šaljući vojnike jedan po jedan u stroj a popunjavajući pozicije prvi u prvoj vrsti, pa prvi u drugoj vrsti, pa drugi u prvoj vrsti itd…:
Na prvu poziciju može da dodje bilo koji od 19 vojnika (samo ne može najvišlji on nikad ne može da bude u prvoj vrsti), na prvo mesto u drugoj opet 19 (sad može najvišlji, ali ne može više onaj što je već rasporedjen uprvu vrstu), preostaje 18 od kojih 17 može na tu poziciju i istom logikom 17 na drugu sve u svemu 19*19*17*17*15*15… itd … = 428670161650355625 što je veći rezultat nego do sada, ali i dalje manje od 20!"?
Nemoj da pricas?
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Raspored vojnika13.02.2017. u 21:54 - pre 86 meseci
Pa grešiš.

Ako si izabrao prvog vojnika u prvoj vrsti, tada u drugu vrstu ne možeš da izabereš BILO KOG od preostalih 19 nego samo one koji su viši od njega. Recimo izabereš vojnika 19, onda iza njega može samo vojnik 20. Pa onda nije 19*19 nego 19*1.

Biraš PAR (dva vojnika) i onda kažeš nižem da stane napred. A par se bira na jedan od načina.
 
Odgovor na temu

[es] :: Matematika :: Raspored vojnika

Strane: 1 2

[ Pregleda: 4112 | Odgovora: 23 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.