Izpitno vprašanje DIRI2005 4400

Iz MaFiRaWiki

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

Vprašanje

|Vpr. 4400| 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 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 dva sklada števil; sklad_1 in sklad_2. V sklad_1 vstavimo števila od 1 do 10, v sklad_2 števila od 5 do 15. Za izpis elementov skladov v takšnem vrstnem redu kot so bili vstavljeni si pripravimo pomožna sklada.

Algoritem 1: Pripravimo nov sklad. Dokler eden izmed skladov ni prazen, primerjamo vrhnja elementa skladov. Večji (ali enak) element iz ustreznega sklada odstranimo in ga vstavimo v nov sklad. Neprazen sklad nato preložimo v nov sklad. Dobimo obrnjen vrstni red elementov zato moramo sklad še preložiti. Sklada, ki sta izvor podatkov sta po končanem algoritmu prazna. Elemente iz izvornih skladov smo preložili v nov skupen sklad. Algoritem je predstavljen z metodo uredi_zlij().

Algoritem 2: podoben kot algoritem 1, a z nekoliko manj prelaganj. Pripravimo nov sklad. Dokler eden izmed skladov ni prazen, primerjamo vrhnja elementa skladov. Večji (ali enak) element iz ustreznega sklada odstranimo in ga vstavimo v nov sklad. Nov sklad preložimo v sklad, ki je ostal neprazen. Dobimo že nov urejen sklad. Algoritem spremeni sklada, ki sta izvor podatkov. Eden izmed izvornih skladov je po končanem algoritmu prazen. Drug izvoren sklad predstavlja nov skupen sklad, ki po končanem algoritmu vsebuje naraščajoče urejene elemente iz obeh izvornih skladov.

Nov sklad izpišemo.


Prikaz delovanja algoritma 1 : primerjava vrhnjih elementov in prelaganje večjih v pomožen sklad.


Slika:Sklad_1_2.png Slika:Sklad_1_2_1.png Slika:Sklad_1_2_2.png Slika:Sklad_1_2_3.png Slika:Sklad_prosto.png

Slika:Sklad_prosto.png Slika:Sklad_1_2_7.png Slika:Sklad_1_2_8.png Slika:Sklad_1_2_9.png Slika:Sklad_prosto.png

Slika:Sklad_prosto.png Slika:Sklad_1_2_15.png Slika:Sklad_1_2_16.png Slika:Sklad_1_2_17.png Slika:Sklad_prosto.png


V programčku je realiziran algoritem 1.

  1. import java.util.* ;
  2. public class Primer4400_1
  3. {
  4. //metoda uredi_zlij
  5. public static void uredi_zlij (Stack<Integer> sklad_1, Stack<Integer> sklad_2, Stack<Integer> sklad_nov)
  6. {
  7. // Algoritem 1
  8. // priprava novega pomožnega, skupnega sklada
  9. Stack<Integer> sklad_nov_obrnjen = new Stack<Integer>();
  10. // primerjava vrhjih elementov skladov, večjega (ali enakega) vstavimo v nov pomožen sklad
  11. while (!sklad_1.empty() && !sklad_2.empty())
  12. {
  13. if ( sklad_1.peek() >= sklad_2.peek() )
  14. {
  15. sklad_nov_obrnjen.push(sklad_1.pop());
  16. }
  17. else
  18. {
  19. sklad_nov_obrnjen.push(sklad_2.pop()) ;
  20. }
  21. }
  22. // neprazen sklad še preložimo v nov pomožen sklad
  23. while (!sklad_1.empty())
  24. {
  25. sklad_nov_obrnjen.push(sklad_1.pop());
  26. }
  27. while (!sklad_2.empty())
  28. {
  29. sklad_nov_obrnjen.push(sklad_2.pop());
  30. }
  31.  
  32. // polnjenje novega sklada
  33. while (!sklad_nov_obrnjen.empty())
  34. {
  35. sklad_nov.push(sklad_nov_obrnjen.pop());
  36. }
  37. }
  38.  
  39. public static void main(String args[])
  40. {
  41. int element;
  42. // priprava sklada 1
  43. Stack<Integer> sklad_1 = new Stack<Integer>();
  44. element = 1 ;
  45. // polnjenje sklada 1
  46. while ( element <= 10 )
  47. {
  48. sklad_1.push(element);
  49. element ++ ;
  50. }
  51. // priprava sklada 2
  52. Stack<Integer> sklad_2 = new Stack<Integer>();
  53. element = 5;
  54. // polnjenje sklada 2
  55. while ( element <= 15 )
  56. {
  57. sklad_2.push(element);
  58. element ++ ;
  59. }
  60. //izpis pripravljenih skladov
  61. //izpis sklada 1
  62. //priprava pomoznega sklada 1
  63. Stack<Integer> sklad_obrnjen_1 = new Stack<Integer>();
  64. // polnjenje pomoznega sklada 1
  65. while (!sklad_1.empty())
  66. {
  67. sklad_obrnjen_1.push(sklad_1.pop());
  68. }
  69. System.out.println();
  70. System.out.println();
  71. System.out.println("Izpis sklada 1 :");
  72. while (!sklad_obrnjen_1.empty())
  73. {
  74. System.out.print(sklad_obrnjen_1.peek() + " ");
  75. sklad_1.push(sklad_obrnjen_1.pop());
  76. }
  77. //izpis sklada 2
  78. //priprava pomoznega sklada 2
  79. Stack<Integer> sklad_obrnjen_2 = new Stack<Integer>();
  80. // polnjenje pomoznega sklada 2
  81. while (!sklad_2.empty())
  82. {
  83. sklad_obrnjen_2.push(sklad_2.pop());
  84. }
  85. System.out.println();
  86. System.out.println();
  87. System.out.println("Izpis sklada 2 :");
  88. while (!sklad_obrnjen_2.empty())
  89. {
  90. System.out.print(sklad_obrnjen_2.peek() + " ");
  91. sklad_2.push(sklad_obrnjen_2.pop());
  92. }
  93.  
  94. // Algoritem 1
  95. // priprava novega sklada
  96.  
  97. Stack<Integer> sklad_nov = new Stack<Integer>();
  98.  
  99. // klic metode uredi_zlij
  100. uredi_zlij (sklad_1, sklad_2, sklad_nov);
  101. // izpis novega sklada
  102. Stack<Integer> sklad_nov_obrnjen = new Stack<Integer>();
  103. while (!sklad_nov.empty())
  104. {
  105. sklad_nov_obrnjen.push(sklad_nov.pop());
  106. }
  107. System.out.println();
  108. System.out.println();
  109. System.out.println("Izpis novega sklada  :");
  110. while (!sklad_nov_obrnjen.empty())
  111. {
  112. System.out.print(sklad_nov_obrnjen.peek() + " ");
  113. sklad_nov.push(sklad_nov_obrnjen.pop());
  114. }
  115. System.out.println();
  116. System.out.println();
  117. }
  118. }

Izpis testnega programčka :

>java Primer4400_1
 
Izpis sklada 1 :
1 2 3 4 5 6 7 8 9 10
 
Izpis sklada 2 :
5 6 7 8 9 10 11 12 13 14 15
 
Izpis novega sklada :
1 2 3 4 5 5 6 6 7 7 8 8 9 9 10 10 11 12 13 14 15
Osebna orodja