Započni novu temu Odgovori na temu  [ 10 Posta ] 
Autoru Poruka
 Tema posta: Algoritmi - problem
PostPoslato: 01.12.2012. 20:44:04 
Korisnikov avatar

Pridružio se: 02.11.2002. 15:44:31
Postovi: 4344
Lokacija: za kompjuterom
Godina: Dipl.
Smer: IS
Imam jedan zanimljiv algoritamski problem :)
Naime, imam listu koja nije sortirana (i nema duplikata). U listi se nalazi običan zapis(ili objekat, kako vam drago) koji ima dva polja (atributa). Jedno polje je string a drugo intidžer. Npr. da bi lakše zamislili, recimo da imamo listu osoba i pri tome svaka osoba ima ime kao prvo polje i starost u godinama kao drugo polje. Trebaju mi imena najstarijih osoba. Dakle vodite računa da se može desiti da samo jedna osoba bude najstarija, a može se desiti i da ih ima više.
Da li je moguće dobiti traženi rezultat kroz samo jednu iteraciju ili mora ipak kroz dve? Još uvek razmišljam, ali za sad ne mogu da smislim algoritam koji bi sve to radio kroz jednu iteraciju.

_________________
:: Sve prste na ruci, u jadu i muci partizanska složila je svest
I sad dokle treba, do sunca, do neba, visoko mi dižemo
pest! ::
:)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 01.12.2012. 21:55:11 
Korisnikov avatar

Pridružio se: 22.10.2004. 12:14:50
Postovi: 1481
Godina: Dipl.
Smer: IS
Moguce je u O(n) naci najstarije osobe ali uz dodatnu memoriju...

_________________
:zaljubljen: :srce:
We all have our time machines, don't we. Those that take us back are memories... And those that carry us forward, are dreams.


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 01.12.2012. 22:12:00 
Korisnikov avatar

Pridružio se: 02.11.2002. 15:44:31
Postovi: 4344
Lokacija: za kompjuterom
Godina: Dipl.
Smer: IS
tj uz "kvazi sortiranje". Na to si mislio? :)

_________________
:: Sve prste na ruci, u jadu i muci partizanska složila je svest
I sad dokle treba, do sunca, do neba, visoko mi dižemo
pest! ::
:)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 01.12.2012. 22:26:56 
Korisnikov avatar

Pridružio se: 22.10.2004. 12:14:50
Postovi: 1481
Godina: Dipl.
Smer: IS
Ne, bez sortiranja. Na sortiranje ti u startu ode O(nlogn) + ti ode makar O(n) na trazenje liste najvecih elemenata.

Evo koda za ovo moje uz ogranicenje da mozda i nije toliko dobro ali postuje to ogranicenje o jednom prolasku kroz listu:

Kod:
...sve inicijalizacije listi itd. itd. itd.

maxEl = unsortedArray[0];
oldestGuys = new ArrayList();
oldestGuys.add(maxEl);
for (int i=1; i<unsortedArray.size(); i++){
   if (unsortedArray[i] > oldestGuys[0]){
      clearOldestGuys();
      oldestGuys.add(unsortedArray[i]);
   }
   if (unsortedArray[i] == oldestGuys[0]){
      oldestGuys.add(unsortedArray[i]);
   }
}
return oldestGuys;


E sad najveci problem imas na liniji clearOldestGuys() jer tu u zavisnosti od programskog jezika treba da nadjes resenje kako ocistiti listu a da ne dobijes jos vremena za trosenje u algoritmu. Ako je u pitanju npr. Java onda prostom inicijalizacijom nove liste gubis staru listu i ostavljas GC da resi posao. U nekom drugom jeziku bi morao da prodjes kroz celu listu i da eliminises element po element liste. Tu u najgorem slucaju dolazis do O(n^2) gde resenje o dva prolaska kroz listu vise ne izgleda kao lose resenje :)

_________________
:zaljubljen: :srce:
We all have our time machines, don't we. Those that take us back are memories... And those that carry us forward, are dreams.


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 01.12.2012. 22:59:20 
Korisnikov avatar

Pridružio se: 02.11.2002. 15:44:31
Postovi: 4344
Lokacija: za kompjuterom
Godina: Dipl.
Smer: IS
da, da na to sam mislio samo nisam našao najspretniji izraz... možda bi bilo bolje da sam nazvao "trenutno grupisanje" :D jer ti tu zapravo grupišeš osobe sa istim godinama starosti, s tim što se pravi grupa samo za trenutno najveću godinu starosti, ali se ide u rastućem redosledu (zato me povuklo na sortiranje).
Međutim još ne mogu da prihvatim činjenicu da stvarno ne može prostije od dve iteracije (ili ove varijante sa grupisanjem u Java slučaju)! :D

_________________
:: Sve prste na ruci, u jadu i muci partizanska složila je svest
I sad dokle treba, do sunca, do neba, visoko mi dižemo
pest! ::
:)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 01.12.2012. 23:26:35 
Moderator
Korisnikov avatar

Pridružio se: 13.11.2001. 08:45:08
Postovi: 4717
Lokacija: Novi Bgd.
Godina: Dipl.
Smer: IS
Darth je dao dobar odgovor. U javi se clearOldestGuys() može uraditi sa pozivom na clear() ali ta metoda iterira nad svim njenim elementima. Lakše je odbaciti ceo objekat liste.

_________________
Oni hipotetički kostrukti o kojima se može govoriti kao o konzistentnim i relativno trajnim dinamičkim sistemima koji objašnjavaju veći deo procesa motivacije, obuhvatajući i ciljeve i motive kroz njihove međusobne relacije, čime se mogu uslovno..


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 01.12.2012. 23:31:23 
Korisnikov avatar

Pridružio se: 22.10.2004. 12:14:50
Postovi: 1481
Godina: Dipl.
Smer: IS
@runner:
moze prostije... da krenes da vodis racuna kako ubacujes elemente u tu listu pa da ona bude uvek sortirana... :D

_________________
:zaljubljen: :srce:
We all have our time machines, don't we. Those that take us back are memories... And those that carry us forward, are dreams.


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 03.12.2012. 01:43:54 

Pridružio se: 06.09.2012. 20:55:36
Postovi: 6
Godina: Apsolvent
Smer: IS
Darth Neman je napisao:
@runner:
moze prostije... da krenes da vodis racuna kako ubacujes elemente u tu listu pa da ona bude uvek sortirana... :D

Ovo. :)

Ili, cuvas mapu gde je key godina starosti a value lista imena i broj koji oznacava trenutno najstarije osobe.


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 03.12.2012. 04:45:18 
Korisnikov avatar

Pridružio se: 02.11.2002. 15:44:31
Postovi: 4344
Lokacija: za kompjuterom
Godina: Dipl.
Smer: IS
e vidiš, ovo drugo je zanimljivo rešenje :)

_________________
:: Sve prste na ruci, u jadu i muci partizanska složila je svest
I sad dokle treba, do sunca, do neba, visoko mi dižemo
pest! ::
:)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
PostPoslato: 03.12.2012. 08:14:43 

Pridružio se: 06.09.2012. 20:55:36
Postovi: 6
Godina: Apsolvent
Smer: IS
Zaboravih, za ubacivanje u listu tako da je sortirana je potrebno da se ne koristi lista vec neka forma binary tree-ja, inace je i ovo O(n^2).

Ili, samo uporedis sa prvim elementom iz liste i ubacis sa leve strane ako je >=. Ako je < ionako ti ne treba.

Naravno, ako imas GC onda je prvo ponudjeno resenje sa ponovnom inicijalizacijom liste jednostavnije, a mi ovde dzaba pricamo. :)


Share on FacebookShare on TwitterShare on Google+
Vrh
 Profil  
Odgovori sa citatom  
Prikaži postove u poslednjih:  Poređaj po  
Započni novu temu Odgovori na temu  [ 10 Posta ] 


Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 5 gostiju


Ne možete postavljati nove teme u ovom forumu
Ne možete odgovarati na teme u ovom forumu
Ne možete monjati vaše postove u ovom forumu
Ne možete brisati vaše postove u ovom forumu
Ne možete slati prikačene fajlove u ovom forumu

Pronađi:
Idi na:  
cron
Copyleft FONForum 2001-2014 | Powered by phpBB © phpBB Group