Izpitno vprašanje RAČ2PRA 4400

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka MonikaDraškovič.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Imamo dva sklada, v katerih so elementi urejeni naraščajoče. Sestavi algoritem, ki s pomočjo osnovnih operacij nad skladom sestavi nov sklad, kjer so elementi (iz prvih dveh skladov) prav tako urejeni naraščajoče.

Odgovor

Ideja rešitve:
Imamo torej dva sklada urejena naraščajoče. Najprej preverimo, če sklada nista prazna. Če sta, vrnemo izjemo "Sklada sta prazna", saj v tem primeru nimamo kaj početi. V nasprotnem primeru pa vemo, da podatkovna struktura Sklad deluje po principu LIFO. (Za podrobnejšo predstavirev sklada glej: Sklad). Ker bi radi na koncu dobili skad, ki bo prav tako urejen naraščajoče, rabimo dva nova sklada, pomožnega in izhodnega. V pomožnega bomo prelagali elemente tako, da bodo v padajočem vrstnem redu. Torej na vsakem koraku primerjamo vrhnja elementa obeh skladov. Manjšega vstavimo v pomožni sklad in hkrati odstranimo iz sklada iz katerega smo element vzeli. To ponavljamo, dokler en izmed skladov ne ostane prazen. Elemente iz tistega sklada, v katerem so še ostali, preložimo v pomožnega. Na koncu pa tega obrnemo oz. preložimo v izhodni sklad, da bodo elementi v naraščajočem vrstnem redu.


  1. public static Sklad<Integer> zlijNarascajoce(Sklad<Integer> s1, Sklad<Integer> s2)
  2. throws Exception {
  3. //pomožni sklad
  4. Sklad<Integer> pom = new Sklad<Integer>();
  5. //sklada sta prazna, vrnemo izjemo
  6. if(s1.prazen() && s2.prazen()) {
  7. throw new Exception("Sklada sta prazna.");
  8. }
  9. //sklada nista prazna
  10. while(!s1.prazen() && !s2.prazen()) {
  11. //če je element iz sklada s1 manjši od elementa iz sklada s2
  12. //s1 vstavimo v pomožen sklad
  13. if(s1.vrh() <= s2.vrh()) {
  14. pom.vstavi(s1.vrh());
  15. s1.odstrani();
  16. }
  17. //če je element iz sklada s2 manjši od elementa iz sklada s1
  18. //s2 vstavimo v pomožen sklad
  19. else {
  20. pom.vstavi(s2.vrh());
  21. s2.odstrani();
  22. }
  23. }
  24. //sklad s1 še ni prazen, zato preložimo elem. v pom
  25. while(!s1.prazen()) {
  26. pom.vstavi(s1.vrh());
  27. s1.odstrani();
  28. }
  29.  
  30. //sklad s2 še ni prazen, zato preložimo elem. v pom
  31. while(!s2.prazen()) {
  32. pom.vstavi(s2.vrh());
  33. s2.odstrani();
  34. }
  35. //obrnemo sklad, da bo urejen naraščajoče
  36. while(!pom.prazen()) {
  37. s.vstavi(pom.vrh());
  38. pom.odstrani();
  39. }
  40. return s;
  41. }

Tesni primer:

  1. public static void main(String[] args) throws Exception {
  2.  
  3. Sklad<Integer> ena = new Sklad<Integer>();
  4. ena.vstavi(7);
  5. ena.vstavi(7);
  6. ena.vstavi(5);
  7. ena.vstavi(3);
  8. ena.vstavi(2);
  9.  
  10. Sklad<Integer> dva = new Sklad<Integer>();
  11. dva.vstavi(6);
  12. dva.vstavi(5);
  13. dva.vstavi(4);
  14. dva.vstavi(3);
  15.  
  16.  
  17. System.out.println("Sklad prvi: " + ena);
  18. System.out.println("Sklad drugi: " + dva);
  19. System.out.println("Sklad zlit_naraščajoče: " +zlijNarascajoce(ena, dva));
  20. }

Dobljeni izpis:

 >java ZlijNaraščajoče
Sklad prvi: 2 3 5 7 7
Sklad drugi: 3 4 5 6
Sklad zlit_naraščajoče: 2 3 3 4 5 5 6 7 7
Osebna orodja