FONForum
http://www.fonforum.org/

Algoritmi - problem
http://www.fonforum.org/viewtopic.php?f=8&t=19483		 Stranica 1 od 1
Autoru:  runner [ 01.12.2012. 20:44:04 ]
Tema posta:  Algoritmi - problem
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.
Autoru:  Darth Neman [ 01.12.2012. 21:55:11 ]
Tema posta:  Re: Algoritmi - problem
Moguce je u O(n) naci najstarije osobe ali uz dodatnu memoriju...
Autoru:  runner [ 01.12.2012. 22:12:00 ]
Tema posta:  Re: Algoritmi - problem
tj uz "kvazi sortiranje". Na to si mislio? :)
Autoru:  Darth Neman [ 01.12.2012. 22:26:56 ]
Tema posta:  Re: Algoritmi - problem
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 :)
Autoru:  runner [ 01.12.2012. 22:59:20 ]
Tema posta:  Re: Algoritmi - problem
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
Autoru:  zlatko [ 01.12.2012. 23:26:35 ]
Tema posta:  Re: Algoritmi - problem
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.
Autoru:  Darth Neman [ 01.12.2012. 23:31:23 ]
Tema posta:  Re: Algoritmi - problem
@runner:
moze prostije... da krenes da vodis racuna kako ubacujes elemente u tu listu pa da ona bude uvek sortirana... :D
Autoru:  jos samo malo [ 03.12.2012. 01:43:54 ]
Tema posta:  Re: Algoritmi - problem
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.
Autoru:  runner [ 03.12.2012. 04:45:18 ]
Tema posta:  Re: Algoritmi - problem
e vidiš, ovo drugo je zanimljivo rešenje :)
Autoru:  jos samo malo [ 03.12.2012. 08:14:43 ]
Tema posta:  Re: Algoritmi - problem
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. :)
Stranica 1 od 1 Sva vremena su u UTC + 1 sat
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/