메인 콘텐츠로 건너뛰기
Učilnica FRI 23/24
  • 홈
  • 더 보기
닫기
검색 입력 전환
한국어 ‎(ko)‎
English ‎(en)‎ Slovenščina ‎(sl)‎ Македонски ‎(mk)‎ Русский ‎(ru)‎ 한국어 ‎(ko)‎
손님 계정으로 접속
로그인
홈
Course Activities
과제물들 퀴즈 포럼모음 학습자료
Recent Courses
You are not enrolled in any courses
  1. aps2uni
  2. Izziv 2

Izziv 2

완료 조건
Opened: 월요일, 11 3월 2024, 7:00 AM
Due: 일요일, 17 3월 2024, 11:59 PM

Implementirajte program (v programskem jeziku Java), ki bo štel primerjave pri iskanju $k$-tega elementa (quickselect) z uporabo različni strategij za izbiro delilnega elementa (pivota). Štejte vsako primerjavo, kjer je udeležen nek element tabele.

Implementirajte štiri strategije izbire pivota:

1. prvi element v tabeli

2. naključni element v tabeli

3. srednji element izmed treh naključno izbranih

4. mediana (pivot dobljen z algoritmom mediana median)


Testiranje:

Testirali boste delovanje teh strategij na dveh različnih vrstah tabel. Prva vrsta bodo naključno generirane tabele, druga vrsta pa že urejene tabele.

Za neko tabelo dolžine n generirajte 10% pozicij (k) elementov, ki bi jih radi našli (iščemo torej k-ti element) . Npr. za neko tabelo dolžine 1000, generirajte 100 naključnih števil med 1 in 1000 (to je naš k) in poiščite k-ti elementov v tabeli. Pri vsakem iskanju beležite koliko primerjav je bilo narejenih, na koncu pa izračunajte povprečno število primerjav.

Pri naključnih tabelah za neko dolžino n generirajte 1000 takih testiranj, vsakič z drugo naključno tabelo, končni rezultat pa bo povprečno število primerjav preko vseh teh tabel.

Pri urejeni tabeli je lahko primer zgolj eden (ni potrebno generirati velikega števila tabel in jih urejati, lahko delate s tabelo od 1 do n), še vedno pa naj velja, da preizkusite poiskati 10% naključnih pozicij v tej tabeli.


Izhod:

Na standardni izhod izpišite dve tabeli:

1. tabela povprečnega števila primerjav pri naključnih tabelah (za vse strategije, za velikosti tabel 100, 1000, 10000 in 100000)

2. tabela povprečnega števila primerjav pri že urejenih tabelah (za vse strategije, za velikosti tabel 100, 1000, 10000 in 100000)

Primer formata tabele (zgolj za razumevanje, lahko format prilagodite svojim željam):


10^210^310^410^5
prviXXXX
naključniXXXX
mediana trehXXXX
mediana medianXXXX

Pri čemer X označuje meritve, ki jih boste dobili.







◄ Kviz 2
Prosojnice ►
손님 계정으로 접속 (로그인)
Get the mobile app Obvestilo o avtorskih pravicah
Moodle 제공