29.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
 
(2 intermediate revisions by one other user not shown)
Riadok 30: Riadok 30:
 
* rozchodiť aplikáciu z prednášky a vytvoriť v nej uvedený strom
 
* rozchodiť aplikáciu z prednášky a vytvoriť v nej uvedený strom
 
* nájsť minimálny vrchol stromu
 
* nájsť minimálny vrchol stromu
  function TBVS.Min: Integer;
+
  function TBVS.Min: TVrchol;
 
  begin
 
  begin
 
   Result := koren;
 
   Result := koren;
if Result <> nil then
+
  if Result <> nil then
while Result.L <> Result do
+
    while Result.L <> nil do
Result :=  Result.L;
+
      Result :=  Result.L;
 
  end;
 
  end;
  
Riadok 41: Riadok 41:
 
: všimnite si, že počet krokov while cyklu bude maximálne hĺbka stromu
 
: všimnite si, že počet krokov while cyklu bude maximálne hĺbka stromu
 
  var
 
  var
M: TVrchol;
+
  M: TVrchol;
 
  begin
 
  begin
M := Strom.min;
+
  M := Strom.min;
if M <> nil then
+
  if M <> nil then
Image1.Canvas.TextOut(0, 0, 'min = ' + M.Text)
+
    Image1.Canvas.TextOut(0, 0, 'min = ' + M.Text);
 
  end;
 
  end;
  
 
* verzia Vloz s dynamickým poľom ako parametrom
 
* verzia Vloz s dynamickým poľom ako parametrom
  function TVBStrom.Vloz(Hodnota: array of Integer)
+
  function TVBStrom.Vloz(Hodnota: array of Integer);
 
  var
 
  var
h: Integer;
+
  h: Integer;
 
  begin
 
  begin
for h in Hodnota do
+
  for h in Hodnota do
Vloz(h);
+
    Vloz(h);
 
  end;
 
  end;
  
 
: otestujeme
 
: otestujeme
begin
+
  Strom.Vloz([6, 2, 4, 7, 3, 9, 5, 8, 1]);
  Strom.Vloz([6, 2, 4, 7, 3, 9, 5, 8, 1])
+
Vloz(h);
+
end;
+
  
 
* ručne vyhadzovať vrchol zo stromu
 
* ručne vyhadzovať vrchol zo stromu
Riadok 73: Riadok 70:
 
: ukázať najprv na tabuli napr. na 5, 7, 2, 4
 
: ukázať najprv na tabuli napr. na 5, 7, 2, 4
 
: vypísať inorder na spodok canvasu
 
: vypísať inorder na spodok canvasu
  Image1.Canvas.TextOut(0, Image1.Height - 20, Strom.Inorder)
+
  Image1.Canvas.TextOut(0, Image1.Height - 20, Strom.Inorder);
  
 
* nakresliť na tabuľu strom aritmetického výrazu 5+7/(4-2*5)
 
* nakresliť na tabuľu strom aritmetického výrazu 5+7/(4-2*5)
Riadok 81: Riadok 78:
 
: postfix najrozumnejší z pohľadu vyhodnocovania
 
: postfix najrozumnejší z pohľadu vyhodnocovania
  
: volanie vnorených je preorder
 
  
 
* lexikografické stromy
 
* lexikografické stromy
Riadok 91: Riadok 87:
 
  bba
 
  bba
 
  bbb
 
  bbb
 +
 +
{{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
Riadok 100: Riadok 98:
 
  ma
 
  ma
 
  mamu
 
  mamu
{{Podnadpis|ďalšie námety}}
+
 
  
  

Aktuálna revízia z 11:10, 19. marec 2013

29. Cvičenie


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


Rozcvička

1. binárny strom je definovaný

TStrom = class
  Info: Integer;
  L, P: TStrom;
  • napísať metódu TStrom.Urob, ktorá upraví hodnoty vo vrcholoch (Info) stromu takto:
  • vo všetkých listoch bude hodnota 1
  • vo vnútorných listoch bude hodnota, ktorá je maximálna z hodnôt jeho synov zvýšené o 1 (alebo súčtom synov)


Cvičenie

  • BVS
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
  • rozchodiť aplikáciu z prednášky a vytvoriť v nej uvedený strom
  • nájsť minimálny vrchol stromu
function TBVS.Min: TVrchol;
begin
 Result := koren;
  if Result <> nil then
    while Result.L <> nil do
      Result :=  Result.L;
end;
na vykreslenie minima treba mať v TForm1.Kresli podporu
všimnite si, že počet krokov while cyklu bude maximálne hĺbka stromu
var
  M: TVrchol;
begin
  M := Strom.min;
  if M <> nil then
    Image1.Canvas.TextOut(0, 0, 'min = ' + M.Text);
end;
  • verzia Vloz s dynamickým poľom ako parametrom
function TVBStrom.Vloz(Hodnota: array of Integer);
var
  h: Integer;
begin
  for h in Hodnota do
    Vloz(h);
end;
otestujeme
Strom.Vloz([6, 2, 4, 7, 3, 9, 5, 8, 1]);
  • ručne vyhadzovať vrchol zo stromu
ak má dvoch synov, minimum pravého podstromu sa presťahuje do vrcholu + potrebné upratovanie
lepšie robiť na košatejšom strome


  • aritmetické stromy
  • ako vyzerá Preorder a Inorder výpis
ukázať najprv na tabuli napr. na 5, 7, 2, 4
vypísať inorder na spodok canvasu
Image1.Canvas.TextOut(0, Image1.Height - 20, Strom.Inorder);
  • nakresliť na tabuľu strom aritmetického výrazu 5+7/(4-2*5)
  • '+ * 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
  • na tabuľu strom obsahujúci
písmená samozrejme nepíšeme do vrcholov, ale na hrany
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);