Izpitno vprašanje DIRI2005 6100

Iz MaFiRaWiki

(Razlika med različicami)

Različica od 18:28, 27 marec 2008

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 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: 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().

Nov sklad izpišemo.

import java.util.* ;
public class Primer6100
{
	public static Stack<Integer> odstrani_podvojeni (Stack<Integer> sklad)
	{
		int element;
		// priprava pomožnega sklada
		Stack<Integer> sklad_pomozen = new Stack<Integer>();
		// Algoritem
		element = sklad.peek() ;
		sklad_pomozen.push(sklad.pop());
		while (!sklad.empty())
		{
			if ( sklad.peek() == element )
			{
				sklad.pop();
			}
			else
			{
				sklad_pomozen.push(sklad.pop());
				element = sklad.peek();
			}
		}
		while (!sklad_pomozen.empty())
		{
			sklad.push(sklad_pomozen.pop());
		}
		return sklad ;
	}
 
	public static void main(String args[])
	{
		int element;
		// priprava sklada
		Stack<Integer> sklad = new Stack<Integer>();
		element = 1 ;
		// polnjenje sklada
		while ( element <= 10 )
		{
			sklad.push(element);
			sklad.push(element);
			sklad.push(element);
			element ++ ;
		}
		//izpis pripravljenega sklada
		//priprava pomoznega sklada
		Stack<Integer> sklad_obrnjen = new Stack<Integer>();
		// polnjenje pomoznega sklada
		while (!sklad.empty())
		{
			sklad_obrnjen.push(sklad.pop());
		}
		System.out.println();
		System.out.println("Izpis sklada :");
		System.out.println();
		while (!sklad_obrnjen.empty())
		{
			System.out.print(sklad_obrnjen.peek() + " ");
			sklad.push(sklad_obrnjen.pop());
		}
		System.out.println();
		System.out.println();
 
 		System.out.println();
		System.out.println("Izpis sklada brez podvojenih elementov :");
		System.out.println();
 
		// klic metode odstrani_podvojeni
		sklad = odstrani_podvojeni(sklad);
 
		// izpis novega sklada, oziroma sklada brez podvojenih elementov
		while (!sklad.empty())
		{
			sklad_obrnjen.push(sklad.pop());
		}
		while (!sklad_obrnjen.empty())
		{
			System.out.print(sklad_obrnjen.peek() + " ");
			sklad.push(sklad_obrnjen.pop());
		}
		System.out.println();
		System.out.println();
	}
}

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

Vzpostavljeno iz "http://wiki.fmf.uni-lj.si/wiki/Izpitno_vpra%C5%A1anje_DIRI2005_6100"

Izpitno vprašanje DIRI2005 6100

Iz MaFiRaWiki

Različica od 18:28, 27 marec 2008

Vprašanje

Odgovor

Pogledi

Osebna orodja

Navigacija

posebne strani

Išči

Orodjarna

 |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.