Izpitno vprašanje DIRI2005 5300

Iz MaFiRaWiki

Predmet Dopolnilno izobraževanje iz računalništva in informatike (DIRI)

Vprašanje

|Vpr. 5300| S pomočjo osnovnih operacij nad skladom iz danega sklada odstrani najmanjši element. Če jih je več, odstrani tistega, ki je v skladu najdlje.


Odgovor in primer programčka sta pripravljena s pomočjo predstavitve Sklada v Javini knjižnici; s pomočjo razreda Stack.


Podatkovna struktura Sklad je v Javini knjižnici predstavljena z razredom Stack. Osnovne operacije s katerimi upravljamo s skladom so predstavljene z metodami razreda Stack. Razred - class Stack vsebuje metode, s pomočjo katerih upravljamo s skladom. S pomočjo metod razreda Stack vstavljamo elemente v sklad, odstranjujemo elemente iz sklada, preverjamo ali je sklad prazen, preverjamo kateri element je na vrhu sklada.

Metode razreda Stack delujejo tako kot je za podatkovno strukturo Sklad značilno. Upoštevana je osnovna lastnost sklada - element, ki je bil zadnji vstavljen v sklad kot prvi prihaja iz sklada. Podatkovna struktura Sklad je v Javini knjižnici torej predstavljena z razredom Stack, ki v celoti upošteva osnovno pravilo sklada, pravilo LIFO. LIFO - last in first out, zadnji noter prvi ven, tako se obnaša Sklad, tako se obnaša Sklad predstavljen v razredu Stack.


Metode razreda Stack, s katerimi so predstavljene osnovne operacije nad skladom:

  • metoda push() - vstavi(), z metodo push vstavljamo elemente v sklad,
  • metoda pop() - odstrani(), z metodo pop odstranjujemo elemente iz sklada. Metoda pop odstrani vrhnji element iz sklada in ga hkrati vrne kot rezultat,
  • metoda peek() - vrh(), z metodo peek ugotavljamo kateri element je na vrhu sklada,
  • metoda empty() - prazen(), z metodo empty ugotavljamo ali je sklad prazen.


Konstruktor razreda Stack, s katerim pripravimo konkreten sklad;

  • konstruktor Stack().

Konkreten sklad pripravimo s pomočjo konstruktorja Stack() iz razreda Stack. Pri pripravi konkretnega sklada napovemo kakšen sklad bomo pripravili, kakšne vrste elemente oziroma kakšne vrste podatkov bomo vstavljali v naš konkreten sklad. Ali bo to sklad celih števil, ali bo to sklad znakov,...

Zgled: priprava sklada celih števil

  • Stack<Integer> sklad = new Stack<Integer>()

Odgovor

V podanem primeru programčka pripravimo sklad števil. V sklad vstavimo 20 naključnih števil. Za izpis elementov sklada v takšnem vrstnem redu kot so bili vstavljeni si pripravimo pomožen sklad.

Algoritem 1: poiskati moramo najmanjši element sklada in mesto - položaj najmanjšega elementa v skladu. Pomagamo si s pripravo pomožnega sklada in prelaganjem elementov v pomožen sklad. Predpostavimo, da je najmanjši kar vrhnji element, odstranimo vrhnjega in ga primerjamo z naslednjim vrhjim elementom. V kolikor je nov vrhnji element manjši (ali enak kot je bil do sedaj najmanjši) postane le ta najmanjši. Preložimo cel sklad, poiščemo najmanjši element in mesto - položaj kje v skladu se je najmanjši element nazadje pojavil. Dobili smo pomožen sklad, z obrnjenim vrstnim redom elementov. Pri prelaganju elementov v osnovni sklad ne vstavimo sedaj tistega najmanjšega elementa, ki se pojavi kot prvi. Algoritem ohrani osnoven sklad, a brez minimalnega elementa, ki je v skladu najdlje.

Algoritem 2: poiščemo najmanjši element sklada. Pomagamo si s pripravo pomožnega sklada in prelaganjem elemementov v pomožen sklad. Predpostavimo, da je najmanjši kar vrhnji element, odstranimo vrhnjega in ga primerjamo z naslednjim vrhjim elementom. V kolikor je nov vrhnji element manjši (ali enak kot je bil do sedaj najmanjši) postane le ta najmanjši. Preložimo cel sklad. Dobili smo pomožen sklad, z obrnjenim vrstnim redom elementov. Pri prelaganju elementov v osnovni sklad ne vstavimo sedaj tistega najmanjšega elemeta, ki se pojavi kot prvi. V pomožnem skladu so elementi razporejeni v obratnem vrstnem redu kot v osnovnem skladu. Najmanjši (najmlajši) element v pomožnem skladu je najmanjši (najstarejši)element osnovnega sklada. Algoritem ohrani osnoven sklad, a brez minimalnega elementa, ki je v skladu najdlje. Algoritem je predstavljen z metodo odstrani_najmanjsi().

Nov sklad izpišemo.


Prikaz delovanja algoritma 2 :


Slika:Sklad_53_1.png Slika:Sklad_53_2.png


V programčku je realiziran algorietm 2 :

  1. import java.util.* ;
  2. public class Primer5300
  3. {
  4. // Metoda odstrani_najmanjsi
  5. public static void odstrani_najmanjsi (Stack<Integer> sklad)
  6. {
  7. int element_min;
  8. boolean odstrani;
  9. // Priprava pomožnega sklada
  10. Stack<Integer> sklad_pomozen = new Stack<Integer>() ;
  11. // Algoritem 2
  12. // sklad preložimo v pomožen sklad in poiščemo najmanjši element v skladu
  13. // iskanje najmanjšega elementa v skladu
  14. odstrani = true ;
  15. element_min = sklad.peek() ;
  16. while (!sklad.empty())
  17. {
  18. if ( sklad.peek() > element_min )
  19. {
  20. sklad_pomozen.push(sklad.pop());
  21. }
  22. else
  23. {
  24. element_min = sklad.peek() ;
  25. sklad_pomozen.push(sklad.pop());
  26. }
  27. }
  28. // elemente iz pomožnega sklada preložimo v sklad
  29. // ne preložimo najmanjšega elementa, ki se pojavi prvi
  30. // prvi najmanjši element v pomožnem skladu, je zadnji najmanjši element v skladu
  31. // odstranimo torej najmanjši element, ki je najdlje v skladu
  32. while (!sklad_pomozen.empty())
  33. {
  34. if ( (sklad_pomozen.peek() == element_min) && odstrani )
  35. {
  36. sklad_pomozen.pop();
  37. odstrani = false ;
  38. }
  39. else
  40. {
  41. sklad.push(sklad_pomozen.pop());
  42. }
  43. }
  44. }
  45.  
  46. public static void main(String args[])
  47. {
  48. // priprava sklada
  49. Stack<Integer> sklad = new Stack<Integer>();
  50. int element;
  51. int stevec;
  52. stevec = 1 ;
  53. // polnjenje sklada
  54. while ( stevec <= 20 )
  55. {
  56. element = 1 + (int)(20*Math.random());
  57. sklad.push(element);
  58. stevec ++ ;
  59. }
  60. // izpis pripravljenega sklada
  61. // priprava pomoznega sklada
  62. Stack<Integer> sklad_obrnjen = new Stack<Integer>();
  63. // polnjenje pomoznega sklada
  64. while (!sklad.empty())
  65. {
  66. sklad_obrnjen.push(sklad.pop());
  67. }
  68. System.out.println();
  69. System.out.println();
  70. System.out.println("Izpis sklada:");
  71. while (!sklad_obrnjen.empty())
  72. {
  73. System.out.print(sklad_obrnjen.peek() + " ");
  74. sklad.push(sklad_obrnjen.pop());
  75. }
  76. System.out.println();
  77.  
  78. // klic metode odstrani_najmanjsi
  79. odstrani_najmanjsi(sklad) ;
  80.  
  81. // izpis novega sklada, oziroma sklada brez najmanjsega elementa
  82. // polnjenje pomožnega sklada
  83. while (!sklad.empty())
  84. {
  85. sklad_obrnjen.push(sklad.pop());
  86. }
  87. System.out.println();
  88. System.out.println();
  89. System.out.println("Izpis sklada, brez (najstarejsega)najmanjsega elementa :");
  90. while (!sklad_obrnjen.empty())
  91. {
  92. System.out.print(sklad_obrnjen.peek() + " ");
  93. sklad.push(sklad_obrnjen.pop());
  94. }
  95. System.out.println();
  96. System.out.println();
  97. }
  98. }

Izpis testnega programčka :

>java Primer5300
 
Izpis sklada :
3 13 3 10 10 16 20 1 11 13 12 9 1 8 6 19 3 8 1 13
 
Izpis sklada brez (najstarejsega)najmanjsega elementa :
3 13 3 10 10 16 20 11 13 12 9 1 8 6 19 3 8 1 13
Osebna orodja