Potapanje podmornicaTrebam rasporediti n podmornica razlicitih duzina na tabli kooridnata x,y.
Raspored podmornica treba biti slucajan ali i uspjesno postavljen ako je to moguce.
Ako imam 5x5 tablu i podmornicu duzine 1 ,program treba da je svaki put random postavi na neko polje.
Problemi dolaze tek kada na malu tablu treba postaviti veliki broj podmornica. (tj. kad mi ne ostaje puno praznih polja a i tada treba voditi racuna o slucajnosti).Recimo, ako imam tablu 2x4, dvije podmornice duzine 3 i jednu podmornicu duzine 2 program treba random da ih rasporedi (postoje dva slucaja za resenje).
Sa tim se nekako i moguce izboriti.Ono sto mene muci je recimo:
tabla 2*6 i tri podmornice sa duzinom 4.
Kako provjeravati takve slucajeve?
Inace moj algoritam radi ovako nekako:
1. provjeri da li je ukupna duzina podmornica veca od table
2. sortiraj podmornice po velicini
3. postavi najvecu podmornicu random na tablu
4. postavljaj sledecu (manju) na tablu
5. ako je nemoguce,ponovo tacka 3.
Brzina izvrsavanja i nije toliko losa, kada je tabla dovoljno velika. (Verovatno niko ni nece igrati podmornica tako da su mu 80% polja pokrivena,ali eto resio sam da rijesim korektno zadatak :).
Ima li neko ideju kako postaviti constraint za onaj slucaj gore?
Ima li uopste u teoriji algoritama neki slican problem?
Vjerovatno se moze rjesiti problem dinamickim programiranjem jako brzo,ali ono sto meni muci je randomizacija svega.
Free advice is seldom cheap.
