29.Prednaska/Cvicenie: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
(Vytvorená stránka „{{Nadpis| 29. Cvičenie}} < 29.Prednáška | riešené úlohy === Cvičenie === * BVS (binárny vyvážený strom) type ...“)
 
 
Riadok 56: Riadok 56:
 
{{Podnadpis|Ďalšie námety}}
 
{{Podnadpis|Ďalšie námety}}
  
:* vzorová úloha na teste: počet listov, hĺbka lexikografického stromu pre
+
* vzorová úloha na teste: počet listov, hĺbka lexikografického stromu pre
 
  mama
 
  mama
 
  ma
 
  ma

Aktuálna revízia z 16:26, 3. apríl 2013

29. Cvičenie


< 29.Prednáška | riešené úlohy



Cvičenie

  • BVS (binárny vyvážený strom)
type
  TBVS = class
    Koren: TVrchol;
  end;
  • ručne vytvoriť, ak postupne pridávame:
6, 2, 4, 7, 3, 9, 5, 8, 1
  • pridať
6.5, 1.5, 5.5
  • vytvoriť uvedený strom v aplikácii z prednášky
  • funkcia TBVS.Min: TVrchol, ktorá nájde minimálny vrchol stromu
  • všimnite si, že počet krokov while cyklu bude maximálne hĺbka stromu
  • na vykreslenie minima treba mať v aplikácii z prednášky (TForm1.Kresli) podporu
  • verzia Vloz s dynamickým poľom ako parametrom
function TVBStrom.Vloz(Hodnota: array of Integer);
  • nakresliť dostatočne košatý strom a ručne vyhadzovať vrchol zo stromu
  • ak má dvoch synov, minimum pravého podstromu sa presťahuje do vrcholu + potrebné upratovanie


  • aritmetické stromy
  • nakresliť strom aritmetického výrazu
5+7/(4-2*5)
  • preorder aritmetického výrazu
(4*5)+(7-9)

výsledok

'+ * 4 5 - 7 9'
a('+', a('*', b(4), b(5)), a('-', b(7), b(9)))
  • programujeme v prefixe, myslíme v infixe
  • postfix najrozumnejší z pohľadu vyhodnocovania


  • lexikografické stromy
  • písmená samozrejme nepíšeme do vrcholov, ale na hrany
  • nakresliť strom obsahujúci
aab
cbb
cab
bba
bbb



Ďalšie námety


  • vzorová úloha na teste: počet listov, hĺbka lexikografického stromu pre
mama
ma
emu
a
ema
ma
mamu



Domáca úloha

  • konštruktor, ktorý ako parameter dostáva string so zápisom aritmetického stromu v prefixe oddelený medzerami a vytvorí BVS
'+ * 4 5000 - 712 94'
zrejme budeme musieť použiť rekurziu
čísla môžu byť aj viacciferné
AStrom := v('+', v('*', c(4), c(5)), v('-', c(7), c(9)));
//Astrom := Vytvor('+ * 4 5 - 7 9');
Memo1.Lines.Add('Prefix = ' + AStrom.Prefix);
Memo1.Lines.Add('Infix = ' + AStrom.Infix);
Memo1.Lines.Add('Hodnota = ' + AStrom.Hodnota);