Izpitno vprašanje RAČ2PRA 6000

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vprašanje

Dana sta dva nepadajoče urejena sklada. Sestavi metodo, ki vrne nepadajoče urejen sklad iz elementov, ki so v obeh skladih.


Ideja


Naš program vsebuje dve metodi. Testno, v kateri bomo podali dva sklada s poljubnimi elementi iz katere bomo poklicali metodo uredi, ki bo elemente iz obeh skladov združila v en sklad.

Elementi v obeh skladih bodo urejeni nepadajoče. Če v enemu skladu ne bo elementov bomo vrnili drugi sklad, če v obeh skladih ne bo elemtov bomo vrnili prazen sklad. Naloge se bomo lotili tako, da bomo primerjali vrhnja elementa iz obeh skladov, tisti element, ki je večji ali enak ga prepišemo v pomožni sklad. Zanka se bo izvajala, dokler oba sklada vsebujeta vsaj en element. Če v skladu s ali v ostane še kaj elementov jih prepišemo v pomožni sklad pom.

V pomožnem skladu bodo elementi urejeni nenaraščajoče. Zato bomo na zadnjem koraku vse elemente "premetali" nazaj v prvotni sklad npr. s, da bodo urejeni tako kot na začetku. Sklad s je rezultat, ki ga metoda vrne. Sklad v pa je na koncu prazen.

Rešitev


  1. public class Sklad{
  2. public static Sklad<E> uredi(Sklad<E> s, Sklad<E> v) throws Exception{
  3. //ustvrimo nov pomožni sklad
  4. Sklad<E> pom = new Sklad<E>();
  5. //če v skladu s ni nobenega elementa, vrnemo sklad v
  6. if(s.prazen()) return v;
  7. //in če v skladu v ni nobenega elementa vrne sklad s
  8. if(v.prazen()) return s;
  9. else {
  10. //zanka se izvaja dokler sta oba sklada polna
  11. while(!s.prazen() && !v.prazen()){
  12. //če je vrhnji el v skladu s večji ali enak kot v skladu v ga shranimo v pom
  13. //sicer shranimo vrhnji el iz sklada v
  14. if(s.vrh() >= v.vrh()){
  15. pom.vstavi(s.vrh());
  16. s.odstrani();}
  17. else {pom.vstavi(v.vrh());
  18. v.odstrani();
  19. }
  20. }
  21. //zanka se zaključi ko je eden ali oba sklada prazna
  22. //če je v skladu v še kakšen el jih prepišemo v pom
  23. while(!s.prazen()){
  24. pom.vstavi(s.vrh());
  25. s.odstrani();
  26. }
  27. //če je v skladu s še kaj el jih prepišemo v pom
  28. while(!v.prazen()){
  29. pom.vstavi(v.vrh());
  30. v.odstrani();
  31. }
  32. }
  33. //Poskrbimo, da bodo elementi v istem relativnem vrstnem redu,
  34. //kot so bili v prvotnem skladu
  35. while(!pom.prazen()){
  36. s.vstavi(pom.vrh());
  37. pom.odstrani();
  38. }
  39. return s;
  40. }
  41. // Testna metoda:
  42. public static void main(String[] args) throws Exception{
  43. //definiramo sklad s:
  44. Sklad<Integer> s = new Sklad<Integer>();
  45. //v skladu morajo biti elementi urejeni nepadajoče
  46. s.vstavi(1);
  47. s.vstavi(3);
  48. s.vstavi(4);
  49. s.vstavi(5);
  50. s.vstavi(7);
  51. s.vstavi(10);
  52. s.vstavi(11);
  53. //definiramo sklad v
  54. Sklad<Integer> v = new Sklad<Integer>();
  55. //v skladu morajo biti elementi urejeni nepadajoče:
  56. v.vstavi(2);
  57. v.vstavi(4);
  58. v.vstavi(8);
  59. v.vstavi(9);
  60. v.vstavi(12);
  61. v.vstavi(13);
  62. //izpis obeh skladov
  63. System.out.println("Podan je prvi sklad: " + s);
  64. System.out.println("Podan je drugi sklad: " + v);
  65. System.out.println("Rezultat: " + uredi(s,v));
  66. }
  67. }

Izpis:
Podan je prvi sklad: -:- 11 -:- 10 -:- 7 -:- 5 -:- 4 -:- 3 -:- 1
Podan je drugi sklad: -:- 13 -:- 12 -:- 9 -:- 8 -:- 4 -:- 2
Rezultat: -:- 13 -:- 12 -:- 11 -:- 10 -:- 9 -:- 8 -:- 7 -:- 5 -:- 4 -:- 4 -:- 3 -:- 2 -:- 1

Osebna orodja