Cvičenia z programovania 2 - utorok 8:10 akvárium X

!!! POZOR !!! od 13.6. do 16.6. sa nebudú dať odovzdávať projekty !!! POZOR !!!

Projekty

Rozcvičky

Domáce úlohy

Označenie komponentov

Reprezentácia grafu obsahuje okrem reprezentácie vrcholov a hrán aj:

		type
		  TGraf = class
			... // vasa oblubena reprezentacia grafu
			Komponent: array of Integer;
			procedure UrobKomponenty;
		  end;
  		

Pridaj most

Naprogramujte funkciu grafu (function TGraf.PridajMost: Boolean;), ktorá nájde a pridá takú chýbajúcu hranu do grafu, aby klesol počet komponentov. Ak sa to podarí, vráti true. Ak sa hrana do grafu už pridať nedá, lebo graf je súvislý, vráti false.

Vizuálna aplikácia na grafy

Naprogramujte oknovú aplikáciu, ktorá bude vizualizovať vrcholy a hrany grafu na 2d grafickej ploche. Aplikácia musí vedieť minimálne korektne vykresliť nejaký graf s väčším počtom vrcholov (desiatky), či už náhodný, alebo zo súboru. Body navyše budú za možnosť pridávať/uberať do grafu vrcholy, hrany a ohodnotenia a drag'n'drop ovládanie polohy vrcholov, prípadne iné vylepšenia. Posielajte mi skomprimovaný celý projekt.

Porovnanie sortov

Vytvorte mini-aplikáciu (grafickú alebo konzolovú) na porovnávanie efektivity rôznych algoritmov usporiadania. Využite nasledovnú štruktúru procedurálnych typov (ak sa vám nezdá, môžete si ju upraviť, ale myšlienku treba zachovať):

  	type TPole = array of TPrvok;
  	// zaznam o priebehu jedneho behu sortovacieho algoritmu
  	type TStatistika = record sort: TSort; N, porovnania, vymeny: integer; end;
  	
	// porovna prvky na indexoch i,j; vrati true ak su spravne usporiadane(a[i]<a[j]), false ak su v zlom poradi(a[i]>=a[j]). urcuje poradie prvkov
	type TPorovnaj = function(var ai,aj: TPrvok; var stat: TStatistika): boolean;
	// vymeni prvky na indexoch i,j.
  	type TVymen = procedure(var pole: TPole; i,j: integer; var stat: TStatistika);
  	// usporiadaj premennu pole, prvky pritom porovnavaj pomocou funkcie porovnaj a vymienaj pomocou funkcie vymen. statistiku vrat v premennej stat.
  	type TSort = procedure(var pole: TPole; porovnaj: TPorovnaj; vymen: TVymen; var stat: TStatistika);
  	
  	// usporiadaj prvky pola niekolkymi sortami a vrat pole statistik. vsetky sorty budu zacinat z rovnakeho poradia.
  	function sortBenchmarkTest(var pole: TPole; sort: array of TSort): array of TStatistika;
  		

	procedure minsort(var pole: TPole; porovnaj: TPorovnaj; vymen: TVymen; var stat: TStatistika);
	var i,j,min_j: integer;
	begin
		stat.N := length(pole); // pocet prvkov
		for i:=low(pole) to high(pole)-1 do begin
			min_j := i;
			for j:=i+1 to high(pole) do
				if porovnaj(pole[j],pole[min_j], stat) then // ak j-ty prvok je mensi ako min_j-ty
					min_j := j;
			vymen(pole, i,j, stat);
		end;		
	end;
	
	function vzostupne(var ai,aj: TPrvok; var stat: TStatistika): boolean;
	begin
		inc(stat.porovnania);
		Result := (ai < aj);
	end;
	
	// ak by sme porovnavali datumy, tak napriklad takto
	function datumVzostupne(var ai,aj: TPrvok; var stat: TStatistika): boolean;
	begin
		inc(stat.porovnania);
		Result := false;
		if (ai.rok < aj.rok) then Result := true
		else if (ai.rok = aj.rok) then
			if (ai.mesiac < aj.mesiac) then Result := true
			else if (ai.mesiac = aj.mesiac) then
				if (ai.den < aj.den) then Result := true
	end;
	
	// a zavola sa to cca nejako takto
	var s: TStat; a: TPole;
	//...
	minsort(a, @vzostupne, @vymen, s);
	write('pocet prvkov: ',s.N,' vymen: ',s.vymeny,' porovnani: ',s.porovnania);

(Všeobecný) backtrack

• Naprogramujte všeobecnú backtrackovú schému pomocou procedurálnych typov a demonštrujte pomocou nej riešenie aspoň 2 rôznych problémov pomocou backtracku. T.j. budem mať všeobecnú funckiu napr. function backtrack(vypisRiesenie: TSpracujRiesenie; moze: TPovolVetvu;...): TRiesenie, ktorá implementuje všeobecnú schému backtrackového algoritmu (niekoľko ich je v prednáške). Ako parametre dostáva procedúru a funkcie a prípadne doplnkové parametre, ktoré implementujú kľúčové body schémy pre riešenie konkrétneho problému.
• Naprogramujete dva rôzne konkrétne backtracky (napríklad generovanie permutácií a problém obchodného cestujúceho, alebo hociaké iné), buď pomocou všeobecnej schémy, alebo bez nej.

Staré domáce úlohy

Generovanie haldy

Naprogramujte generovanie haldy s daným počtom vrcholov. Halda (angl. heap) je binárny strom, ktorý ma minimálnu možnú hĺbku a všetky listy na najhlbšej úrovni sú "natlačené" vľavo. Na obsahu listov mi nezáleží, ale ideálne by bolo, keby boli po vypísaní inorderom usporiadané. Možno sa oplatí využiť vlastnosť, že plný binárny strom hĺbky H má 2^H+1-1 vrcholov. Teda naopak, strom s N vrcholmi má hĺbku minimálne ceil(log₂(N+1)-1) kde ceil vráti hornú celú časť, teda zaokrúhlenie nahor. Ľahšie sa to možno predstaví ako log₂(najbližšia_väčšia_alebo_rovná_mocnina_dvojky(N+1))-1.

Aritmetický binárny strom

Aritmetický binárny strom má v listoch celé čísla a vo vnútorných uzloch má operáciu, kde ľavý a pravý podstrom predstavujú operandy, ktoré treba operáciou skombinovať (sčítať, odčítať, vynásobiť, vydeliť) Ak je operadom operácia, znamenaá to, že je akoby v zátvorke. Náčrt deklarácií pre triedy je nižšie. Takýto strom môžeme zapísať v troch tvaroch, podľa toho, či je operácia pred operandami, medzi operandami, alebo za operandami:

• inorder ((1 + 2) * 3) - operátor je medzi, prirodzený zápis, ale nejednoznačný, nutné používať zátvorky
• preorder (* + 1 2 3) - operátor je pred, ak by sme chápali operaátory ako pascalovské funkcie, vyzeralo by to podobne (až na zátovrky a čiarky): krát(plus(1, 2), 3)
• postorder (1 2 + 3 *) - operátor je po operanoch, tzv. poľský zápis, podľa starých poľských kalkulačiek, dobre sa spracúva

TBinarnyStrom = class
protected
	lavy,pravy: TBinarnyStrom;
public
	function pravyPodstrom: TBinarnyStrom;
	function lavyPodstrom: TBinarnyStrom;
	function vyhodnot: integer; virtual; abstract;
end

TZnamienko = class (TBinarnyStrom)
protected
	znamienko: char;
public
	constructor Create(zn: char);
	function vyhodnot: integer; override;
end

TCislo = class (TBinarnyStrom)
protected
	hodnota: integer;
public
	constructor Create(hod: integer);
	function vyhodnot: integer; override;
end

function parsujPreorder(input: string): TBinarnyStrom;       // + * 1 2 3  pochopi ako  (1 * 2) + 3    0.5 boda
var
  start, space: integer;

	function parsuj: TBinarnyStrom;
	begin
		// preskoc medzery
		while (space <= length(input)) and (_____________________) do
			inc(space);
			
		start := space; // tuto sa bude zacinat slovo
		
		// najdi dalsiu medzeru
		while (space <= length(input)) and (_____________________) do
			inc(space);
		
		// (space-start) je teraz vlastne dlzka slova

		if (space-start=1) and (_____________ in ['+','-','*','/']) then begin
			Result := _____________________;
			Result.lavy := parsuj; // rekurzivne sparsujeme zvysok stringu - prvy operand
			Result.pravy := parsuj; // a potom este dalsi zvysok - druhy operand
		end
		else
			Result := TCislo.Create(_____________________);
	end;

begin
	start := 1;
	space := 1;
	Result := parsuj;
end;

function parsujPostorder(input: string): TBinarnyStrom;       // 1 2 * 3 +  pochopi ako  (1 * 2) + 3    1.5 boda
// v zasade v mnohom podobne ako preorder, ale namiesto rekurzie bude mat zasobnik uzlov
// ked je nove nacitane slovo hodnota, prida novy uzol do zasobnika
// ked je nove slovo operator, vyberie a pouzije posledne dva prvky v zasobniku ako operandy operacie a do zasobnika prida takyto zlozeny uzol
    	

Spájaný zoznam

Vymen(i,j: integer)

Doprogramujte (alebo úplne preprogramujte) metódu spájaného zoznamu, ktorá vymení dva vrcholy určené indexami, aby fungovala správne vo všetkých prípadoch. (za 1 bod)

Otoc

Naprogramujte metódu spájaného zoznamu, ktorá otočí zoznam namieste, t.j. nevytvorí žiadny nový zoznam, pole ani inú množinu hodnôt, resp. vrcholov (ktorej by sa veľkosť menila podľa veľkosti pôvodného zoznamu). Môžete, ale nemusíte pri tom použiť metódu vymeň - ide to aj bez nej celkom ľahko. (za 1 bod)