Izpitno vprašanje RAČ2PRA 5900a

Iz MaFiRaWiki

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

Kaj pomeni to opozorilo?

Vprašanje

S pomočjo osnovnih operacij nad skladom iz danega sklada števil odstrani vsa soda števila.

Ideja

Npr. imamo dan sklad naslednjih števil

in iz njega želimo odstraniti vsa soda števila. Razmišljajmo čisto preprosto. Število je sodo, če je deljiv z dva in ima ostanek 0. Postopek našega "odstranjevanja" :

- pogledamo vrhnji element

- če je deljiv z dva ( je sodo ), ga odstranimo

- če ni deljiv z dva ( je liho ), ga damo v pomožen sklad

- to ponavljamo, vse dokler se nam sklad števil ne sprazni

- in na koncu pomožen sklad vstavimo nazaj v prvoten sklad in se s tem vrstni red števil ne spremeni


Naš prvoten sklad:


Pomožen sklad, v katere smo shranjevali liha števila:


Končen sklad ( pomožen sklad smo prestavili nazaj v prvoten sklad )


Odgovor

  1.  
  2. public class OdstraniSode {
  3. public static Sklad<Integer> odstraniSode(Sklad<Integer> s) throws Exception {
  4. // ustvarimo pomožen sklad, v katere bomo shranili vsa liha števila
  5. Sklad<Integer> pom = new Sklad<Integer>();
  6. // če je sklad s prazen, javi napako
  7. if(s.prazen()) {
  8. throw new Exception("Dan sklad je prazen!");
  9. }
  10. // če je sklad poln
  11. else {
  12. // gremo čez celoten sklad, dokler je v tem še kak element
  13. while(!s.prazen()) {
  14. // z x definiramo vrh sklada
  15. Integer x = s.vrh();
  16. // z zanko gledamo, če je element sod
  17. if(x % 2 == 0) {
  18. // če je sod, ga odstranimo iz sklada s
  19. s.odstrani();
  20. }
  21. // če element ni sod ( je lih )
  22. else {
  23. // ga vstavimo v pomožen sklad
  24. pom.vstavi(x);
  25. // in ga nato odstranimo iz sklada s
  26. s.odstrani();
  27. }
  28. }
  29. }
  30. // liha števila iz sklada pom preložimo v sklad s
  31. while(!pom.prazen()) {
  32. // prvi ( vrhnji ) element definiramo z x
  33. Integer x = pom.vrh();
  34. // v sklad s vstavimo element x
  35. s.vstavi(x);
  36. // in ga za tem odstranimo iz pomožnega sklada
  37. pom.odstrani();
  38. }
  39. return s;
  40. }
  41. // primer za preizkus delovanja programa
  42. public static void main(String[] args) throws Exception{
  43. Sklad<Integer> s = new Sklad<Integer>();
  44. s.vstavi(1);
  45. s.vstavi(3);
  46. s.vstavi(4);
  47. s.vstavi(6);
  48. s.vstavi(2);
  49. s.vstavi(5);
  50. System.out.println(s);
  51. odstraniSode(s);
  52. System.out.println(s);
  53. }
  54. }
Osebna orodja