Forum@DeGiorgi :: Pogledajte temu

through

[^/[Print]\]

Forum@DeGiorgi -> Čistilište

#1: Problem kraljica Autor/ica: Ryssa,

Postano: 20:03 čet, 20. 2. 2014
—
Evo jedan kombinatorni problem pa ako se nekome da probati razmislit ili da me nekako uputi...imamo šahovsku ploču dimenzija 8x8...Na početku biramo k kraljica koje postavljamo na ploču tako da se niti jedna kraljica ne napada...Polja na koja stavljamo k kraljica biramo sami i ako kraljicu stavimo na nedopušteno mjesto (gdje je izložena drugim kraljicama) program javlja da je mjesto nedopušteno i dopušta da ponovno biramo mjesto. Dakle na šahovskoj ploči imamo k fiksnih kraljica. Program treba izračunati koliko maximalno kraljica može biti na šahovskoj ploči ako znamo da je k kraljica već postavljeno na ploču.

#2: Autor/ica: goranm,

Postano: 23:34 čet, 20. 2. 2014
—
Nije jasno zelis li:

Ako je ovo prvo, onda je to jednostavna setnja po 8x8 matrici. Ako je ovo drugo, onda broj ovisi o rasporedu. Postoji jedan raspored za k=4 kraljica u kojem je maksimalan broj 7 i drugi za koji je maksimalan broj 8.

#3: Autor/ica: Ryssa,

Postano: 10:45 pet, 21. 2. 2014
—
Mislila sam na ovaj prvi slučaj kada imamo k fixnih kraljica i njih više ne premiještamo nego nas zanima koliko se još može dodati kraljica da se međusobno ne napadaju. Program samo vraća ukupan mogući br kraljica na ploči (k fixnih + max br kraljica koje možemo dodati). Je li to onda modificirani slučaj problema 8 kraljica (rekurzija) i koristi li se backtracking? Naime uvjet je da se program izvede u 2 sec.

#4: Autor/ica: goranm,

Postano: 12:07 pet, 21. 2. 2014
—

Ryssa (napisa):

Naime uvjet je da se program izvede u 2 sec.

Postoji li uvjet na slozenost? Jer isti program na dva razlicita racunala cesto nema isto vrijeme izvodjenja.

Nisam pretjerano upoznat s efikasnoscu raznih pristupa tako da je bolje da neki racunarac predlozi pristup jer meni na pamet ne pada ista sto je elegantnije od brute-force metode (u najgorem slucaju, k=1, treba ispitati barem 90000 kombinacija (priblizan broj dobiven vrlo traljavim argumentom, vrlo lako moguce da je stvaran broj puno manji)).

#5: Autor/ica: Ryssa,

Postano: 13:16 pet, 21. 2. 2014
—
Nema uvjeta na složenost, samo da vrijeme izvršavanja mora biti max 2 sec, valjda se to misli na neko prosječno današnje računalno, ne znam. Hvala ipak Smile

#6: Autor/ica: satja,

Postano: 0:13 sub, 22. 2. 2014
—
Prekrizis sva napadnuta polja. Na sve nacine odaberes gdje ces staviti prvu kraljicu (na neko polje koje nije prekrizeno), prekrizis polja koja ona napada i daljnje kraljice postavljas na isti nacin rekurzivno. To je mnogo efikasnije nego da odmah biras sve mogucnosti i onda provjeravas nenapadanje.

Moze se to jos optimizirati. U globalnoj varijabli pamtis najbolje dosad pronadjeno rjesenje (M) i ako vidis da u trenutnoj grani rekurzije imas (broj_postavljenih_kraljica + broj_neprekrizenih_polja) <= M, tu granu mozes odmah odrezati jer iz nje neces poboljsati rjesenje. Osim toga, jasno je da ne mozes postaviti vise od 8 - K kraljica pa ako rekurzija dodje do te dubine, mozes prekinuti sve daljnje trazenje jer je sigurno pronadjen optimum.

Forum@DeGiorgi -> Čistilište

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Stranica 1 / 1.