Izpitno vprašanje DIRI2005 6100

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 18:28, 27 marec 2008
PeterMarcic (Pogovor | prispevki)

← Prejšnja različica
Trenutna različica
PeterMarcic (Pogovor | prispevki)

Vrstica 15: Vrstica 15:
-Metode razreda Stack, s katerimi so predstavljene osnovne operacije nad skladom:+'''Metode''' razreda Stack, s katerimi so predstavljene osnovne operacije nad skladom:
-*metoda push() - vstavi(), z metodo push vstavljamo elemente v sklad+*metoda push() - vstavi(), z metodo push vstavljamo elemente v sklad,
-*metoda pop() - odstrani(), z metodo pop odstranjujemo elemente iz sklada+*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 peek() - vrh(), z metodo peek() ugotavljamo kateri element je na vrhu sklada,
-*metoda empty() - prazen(), z metodo empty() ugotavljamo ali je sklad prazen+*metoda empty() - prazen(), z metodo empty() ugotavljamo ali je sklad prazen.
-Konstruktor razreda Stack, s katerim pripravimo konkreten sklad+'''Konstruktor''' razreda Stack, s katerim pripravimo konkreten sklad;
-*konstruktor Stack()+*konstruktor Stack().
Konkreten sklad pripravimo s pomočjo konstruktorja Stack() iz razreda 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 Pri pripravi konkretnega sklada napovemo kakšen sklad bomo pripravili, kakšne vrste elemente oziroma
Vrstica 29: Vrstica 29:
sklad znakov,... sklad znakov,...
-Zgled Priprava sklada celih števil +'''Zgled:''' priprava sklada celih števil
*Stack<Integer> sklad = new Stack<Integer>() *Stack<Integer> sklad = new Stack<Integer>()
---- ----
- 
== Odgovor == == Odgovor ==
Vrstica 39: Vrstica 38:
V podanem primeru programčka pripravimo sklad števil. Sklad pripravimo tako, da imamo elemente podvojene ali celo potrojene. Za izpis elementov sklada v takšnem vrstnem redu kot so bili vstavljeni si pripravimo pomožen sklad. V podanem primeru programčka pripravimo sklad števil. Sklad pripravimo tako, da imamo elemente podvojene ali celo potrojene. Za izpis elementov sklada v takšnem vrstnem redu kot so bili vstavljeni si pripravimo pomožen sklad.
-'''Algoritem:''' dokler osnovni sklad ni prazen, elemente prelagamo v nov pomožen sklad. Vrhnji element preložimo v nov pomožen sklad in ga odstranimo iz sklada. Naslednji vrhnji element primerjamo s predhodnim vrhnjim elementom. V kolikor sta elementa enaka vrhnji element iz sklada odstranimo, sicer ga preložimo v nov pomožen sklad. Hkrati postane vrhnji element, element s katerim nato primerjamo naslednje elemente sklada. Dobljen sklad je v obratnem vrstnem redu kot osnoven sklad, zato ga še preložimo. Algoritem ohrani osnoven - prvoten sklad, a brez podvojenih elementov. Algoritem je predstavljen z metodo '''odstrani_podvojeni()'''.+'''Algoritem:''' Pomagamo si s pripravo pomožnega sklada in prelaganjem elemementov v pomožen sklad. Dokler osnovni sklad ni prazen, elemente prelagamo v pomožen sklad. Vrhnji element preložimo v nov pomožen sklad in ga odstranimo iz sklada. Naslednji vrhnji element primerjamo s predhodnim vrhnjim elementom. V kolikor sta elementa enaka vrhnji element iz sklada odstranimo, sicer ga preložimo v pomožen sklad. Hkrati postane vrhnji element, element s katerim nato primerjamo naslednje elemente sklada. Dobljen sklad je v obratnem vrstnem redu kot osnoven sklad, zato ga še preložimo. Algoritem ohrani osnoven - prvoten sklad, a brez podvojenih elementov. Algoritem je predstavljen z metodo '''odstrani_podvojeni()'''.
Nov sklad izpišemo. Nov sklad izpišemo.
 +'''Prikaz delovanja algoritma :'''
 +
 +----
 +<table>
 +<tr valign="bottom">
 +<td colspan="10"></td>
 +<td>[[Slika:Sklad_61_1.png]]</td>
 +<td colspan="10"></td>
 +<td>[[Slika:Sklad_61_2.png]]</td>
 +</tr>
 +</table>
 +----
 +
 +
 +'''Algoritem realiziran v programčku.'''
<java>import java.util.* ; <java>import java.util.* ;
public class Primer6100 public class Primer6100
{ {
- public static Stack<Integer> odstrani_podvojeni (Stack<Integer> sklad)+ public static void odstrani_podvojeni (Stack<Integer> sklad)
{ {
int element; int element;
Vrstica 53: Vrstica 67:
Stack<Integer> sklad_pomozen = new Stack<Integer>(); Stack<Integer> sklad_pomozen = new Stack<Integer>();
// Algoritem // Algoritem
 + // določitev primerjalnega elementa
element = sklad.peek() ; element = sklad.peek() ;
 + // v pomozni sklad vstavimo vrhnji element iz skladain ga iz njega tudi odstranimo
sklad_pomozen.push(sklad.pop()); sklad_pomozen.push(sklad.pop());
while (!sklad.empty()) while (!sklad.empty())
Vrstica 59: Vrstica 75:
if ( sklad.peek() == element ) if ( sklad.peek() == element )
{ {
- sklad.pop();+ sklad.pop(); // ker je nov vrhnji element enak primerjalnemu, je podvojen, zato ga le odstranimo
} }
else else
{ {
- sklad_pomozen.push(sklad.pop());+ sklad_pomozen.push(sklad.pop()); // v pomožen sklad vstavimo vrhnji element iz sklada
- element = sklad.peek();+ element = sklad.peek(); // primerjalni element postane vrhnji element
} }
} }
Vrstica 71: Vrstica 87:
sklad.push(sklad_pomozen.pop()); sklad.push(sklad_pomozen.pop());
} }
- return sklad ; 
} }
Vrstica 88: Vrstica 103:
element ++ ; element ++ ;
} }
- //izpis pripravljenega sklada+ // izpis pripravljenega sklada
- //priprava pomoznega sklada+ // priprava pomoznega sklada
Stack<Integer> sklad_obrnjen = new Stack<Integer>(); Stack<Integer> sklad_obrnjen = new Stack<Integer>();
// polnjenje pomoznega sklada // polnjenje pomoznega sklada
Vrstica 96: Vrstica 111:
sklad_obrnjen.push(sklad.pop()); sklad_obrnjen.push(sklad.pop());
} }
 + System.out.println();
System.out.println(); System.out.println();
System.out.println("Izpis sklada :"); System.out.println("Izpis sklada :");
- System.out.println(); 
while (!sklad_obrnjen.empty()) while (!sklad_obrnjen.empty())
{ {
Vrstica 106: Vrstica 121:
System.out.println(); System.out.println();
System.out.println(); System.out.println();
- 
- System.out.println(); 
System.out.println("Izpis sklada brez podvojenih elementov :"); System.out.println("Izpis sklada brez podvojenih elementov :");
- System.out.println(); 
// klic metode odstrani_podvojeni // klic metode odstrani_podvojeni
- sklad = odstrani_podvojeni(sklad);+ odstrani_podvojeni(sklad);
// izpis novega sklada, oziroma sklada brez podvojenih elementov // izpis novega sklada, oziroma sklada brez podvojenih elementov
Vrstica 130: Vrstica 142:
Izpis testnega programčka: Izpis testnega programčka:
<java-simple>>java Primer6100 <java-simple>>java Primer6100
 +
Izpis sklada : Izpis sklada :
1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10
 +
Izpis sklada brez podvojenih elementov : Izpis sklada brez podvojenih elementov :
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
</java-simple> </java-simple>

Trenutna različica

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

Vprašanje

|Vpr. 6100| Dan je nepadajoče urejen sklad. S pomočjo osnovnih operacij izbriši vse podvojene elemente v skladu.


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. Sklad pripravimo tako, da imamo elemente podvojene ali celo potrojene. Za izpis elementov sklada v takšnem vrstnem redu kot so bili vstavljeni si pripravimo pomožen sklad.

Algoritem: Pomagamo si s pripravo pomožnega sklada in prelaganjem elemementov v pomožen sklad. Dokler osnovni sklad ni prazen, elemente prelagamo v pomožen sklad. Vrhnji element preložimo v nov pomožen sklad in ga odstranimo iz sklada. Naslednji vrhnji element primerjamo s predhodnim vrhnjim elementom. V kolikor sta elementa enaka vrhnji element iz sklada odstranimo, sicer ga preložimo v pomožen sklad. Hkrati postane vrhnji element, element s katerim nato primerjamo naslednje elemente sklada. Dobljen sklad je v obratnem vrstnem redu kot osnoven sklad, zato ga še preložimo. Algoritem ohrani osnoven - prvoten sklad, a brez podvojenih elementov. Algoritem je predstavljen z metodo odstrani_podvojeni().

Nov sklad izpišemo.


Prikaz delovanja algoritma :


Slika:Sklad_61_1.png Slika:Sklad_61_2.png


Algoritem realiziran v programčku.

  1. import java.util.* ;
  2. public class Primer6100
  3. {
  4. public static void odstrani_podvojeni (Stack<Integer> sklad)
  5. {
  6. int element;
  7. // priprava pomožnega sklada
  8. Stack<Integer> sklad_pomozen = new Stack<Integer>();
  9. // Algoritem
  10. // določitev primerjalnega elementa
  11. element = sklad.peek() ;
  12. // v pomozni sklad vstavimo vrhnji element iz skladain ga iz njega tudi odstranimo
  13. sklad_pomozen.push(sklad.pop());
  14. while (!sklad.empty())
  15. {
  16. if ( sklad.peek() == element )
  17. {
  18. sklad.pop(); // ker je nov vrhnji element enak primerjalnemu, je podvojen, zato ga le odstranimo
  19. }
  20. else
  21. {
  22. sklad_pomozen.push(sklad.pop()); // v pomožen sklad vstavimo vrhnji element iz sklada
  23. element = sklad.peek(); // primerjalni element postane vrhnji element
  24. }
  25. }
  26. while (!sklad_pomozen.empty())
  27. {
  28. sklad.push(sklad_pomozen.pop());
  29. }
  30. }
  31.  
  32. public static void main(String args[])
  33. {
  34. int element;
  35. // priprava sklada
  36. Stack<Integer> sklad = new Stack<Integer>();
  37. element = 1 ;
  38. // polnjenje sklada
  39. while ( element <= 10 )
  40. {
  41. sklad.push(element);
  42. sklad.push(element);
  43. sklad.push(element);
  44. element ++ ;
  45. }
  46. // izpis pripravljenega sklada
  47. // priprava pomoznega sklada
  48. Stack<Integer> sklad_obrnjen = new Stack<Integer>();
  49. // polnjenje pomoznega sklada
  50. while (!sklad.empty())
  51. {
  52. sklad_obrnjen.push(sklad.pop());
  53. }
  54. System.out.println();
  55. System.out.println();
  56. System.out.println("Izpis sklada :");
  57. while (!sklad_obrnjen.empty())
  58. {
  59. System.out.print(sklad_obrnjen.peek() + " ");
  60. sklad.push(sklad_obrnjen.pop());
  61. }
  62. System.out.println();
  63. System.out.println();
  64. System.out.println("Izpis sklada brez podvojenih elementov :");
  65.  
  66. // klic metode odstrani_podvojeni
  67. odstrani_podvojeni(sklad);
  68.  
  69. // izpis novega sklada, oziroma sklada brez podvojenih elementov
  70. while (!sklad.empty())
  71. {
  72. sklad_obrnjen.push(sklad.pop());
  73. }
  74. while (!sklad_obrnjen.empty())
  75. {
  76. System.out.print(sklad_obrnjen.peek() + " ");
  77. sklad.push(sklad_obrnjen.pop());
  78. }
  79. System.out.println();
  80. System.out.println();
  81. }
  82. }

Izpis testnega programčka:

>java Primer6100
 
Izpis sklada :
1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10
 
Izpis sklada brez podvojenih elementov :
1 2 3 4 5 6 7 8 9 10
Osebna orodja