12.Prednaska

Z Pascal
Revízia z 00:58, 27. október 2012; Andrej (Diskusia | príspevky)

(rozdiel) ← Staršia verzia | Aktuálna úprava (rozdiel) | Novšia verzia → (rozdiel)
Prejsť na: navigácia, hľadanie
12. Prednáška

úlohy | cvičenie


Nekonečná rekurzia

Rekurzia v programovaní znamená, že podprogram najčastejšie zavolá sám seba, t.j. že podprogram je definovaný pomocou samého seba. Na prvej ukážke vidíme rekurzívnu procedúru, ktorá nerobí nič iné, len volá samú seba:

procedure TForm1.Button1Click(Sender: TObject);
 
  procedure XY;
  begin
    XY;
  end;
 
begin
  XY;
end;

chybová hláška

Takýto program veľmi rýchlo skončí chybovou správou.

To, že program naozaj volal sám seba, môžeme vidieť, keď popri rekurzívnom volaní urobíme nejakú akciu, napr. vypisovanie nejakého počítadla:

procedure TForm1.Button1Click(Sender: TObject);
var
  P: Integer;
 
  procedure XY;
  begin
    Inc(P);
    Caption := IntToStr(P);
    XY;
  end;
 
begin
  P := 0;
  XY;
end;

V tomto prípade program opäť spadne, hoci môžeme vidieť, ako sa sa zvyšovalo počítadlo v titulku aplikácie (Caption tu znamená Form1.Caption a teda titulný riadok aplikácie). Treba si uvedomiť, že každé zvýšenie počítadla zamená rekurzívne volanie a teda vidíme, že ich bolo vyše 250 tisíc krát. My už vieme, že každé volanie podprogramu (bez ohľadu na to, či je rekurzívne alebo nie) spôsobí, že program si niekde zapamätá návratovú adresu, aby po skončení podprogramu vedel, kam sa má vrátiť. Ak by si zapamätával len 4-bajtovú adresu, zaberalo by to v pamäti vyše 1MG. Naozaj si systém pre každý pascalovský program vyhradí len niekoľko MG nielen na návratové adresy, ale aj na všetky lokálne premenné spolu.

My sa budeme v našich programoch snažiť vyvarovať takejto nekonečnej rekurzii. Hoci ešte si ju ukážeme aj pri práci s robotom:

procedure TForm1.Button1Click(Sender: TObject);
var
  Robot: TRobot;
 
  procedure XY(S: Real);
  begin
    Robot.Fd(S);
    Robot.Lt(60);
    Wait(1);
    XY(S + 1);
  end;
 
begin
  Robot := TRobot.Create;
  XY(10);
  Robot.Free;
end;

nekonečná rekurzia

Aj tento program, ak by sme ho nechali dostatočne dlho bežať, spadne.

Trasujeme tento program (použijeme známy mechanizmus volania podprogramov):

  • z hlavného programu je volanie procedúry XY => vytvorí sa lokálna premenná S, ktorej hodnota je 10,
  • nakreslí sa čiara dĺžky S a robot sa otočí doľava o 60 stupňov,
  • znovu sa volá procedúra XY s parametrom S zmeneným na S+1, t.j. vytvorí sa nová lokálna premenná S s hodnotou 11 (táto premenná sa vytvára na zásobníku),
  • toto sa robí donekonečna. Už vieme, že časom sa pamäť počítača (určená na mechanizmus volania podprogramov) zaplní. Hovoríme, že pretečie zásobník, t.j. niekedy sa môže objaviť správa Stack overflow.

Zásobník (stack) je údajová štruktúra, ktorá má tieto vlastnosti:

  • nové prvky pridávame na vrch (napr. kopa tanierov, resp. na koniec radu čakajúcich)
  • keď potrebujeme zo zásobníka nejaký prvok, vždy ho odoberáme z vrchu (posledne položený tanier, resp. posledný v rade čakajúcich)

V ukážke si ešte všimnite volanie Robot.Free na konci programu: na tento príkaz sa výpočet nikdy nedostane a teda je tu zbytočný.



Chvostová rekurzia (nepravá rekurzia)



Aby sme nevytvárali nikdy nekončiace programy, t.j. nekonečnú rekurziu, niekde do tela rekurzívnej procedúry musíme vložiť test, ktorý zabezpečí, že v niektorých prípadoch rekurzia predsa len skončí. Najčastejšie to budeme riešiť tzv. triviálnym prípadom: na začiatok podprogramu umiestnime podmienený príkaz if, ktorý otestuje triviálny prípad, t.j. prípad, keď už nebudeme procedúru rekurzívne volať, ale vykonáme len nejaké "nerekurzívne" príkazy. Môžeme si to predstaviť aj takto: rekurzívna procedúra rieši nejaký komplexný problém a pri jeho riešení volá samu seba (rekurzívne volanie) väčšinou s nejakými pozmenenými údajmi. V niektorých prípadoch ale rekurziu na riešenie problému nepotrebujeme, ale vieme to vyriešiť "triviálne" aj bez nej (riešenie takejto úlohy je už "triviálne"). V takto riešených úlohách vidíme, že procedúra sa skladá z dvoch častí:

  • pri splnení nejakej podmienky, sa vykonajú príkazy bez rekurzívneho volania (triviálny prípad),
  • inak sa vykonajú príkazy, ktoré v sebe obsahujú rekurzívne volanie.

Zrejme, toto má šancu fungovať len vtedy, keď po nejakom čase naozaj nastane podmienka triviálneho prípadu, t.j. keď sa tak menia parametre rekuzívneho volania, že sa k triviálnemu prípadu nejako blížime. V nasledujúcej ukážke môžete vidieť, že rekurzívna špirála sa kreslí tak, že sa najprv nakreslí úsečka dĺžky S, robot sa otočí o 60 stupňov vľavo a dokreslí sa špirála väčšej veľkosti. Toto celé skončí, keď už budeme chcieť nakresliť špirálu väčšiu ako 100 - takáto špirála sa nenakreslí. Triviálnym prípadom je tu nič, t.j. žiadna akcia pre príliš veľké špirály.

procedure TForm1.Button1Click(Sender: TObject);
var
  Robot: TRobot;
 
  procedure Spir(S: Real);
  begin
    if S > 100 then
      // nič nerob len skonči
    else
    begin
      Robot.Fd(S);
      Robot.Lt(60);
      Wait(1);
      Spir(S + 3);
    end;
  end;
 
begin
  Robot := TRobot.Create;
  Spir(10);
  Robot.Free;
end;

špirála

Trasujme volanie so simuláciou na zásobníku s počiatočnou hodnotou parametra S, napr. 92:

  • na zásobníku vznikne nová lokálna premenná S s hodnotou 92 ... robot nakreslí čiaru, otočí sa a volá Spir s parametrom 95,
  • na zásobníku vznikne nová lokálna premenná S s hodnotou 95 ... robot nakreslí čiaru, otočí sa a volá Spir s parametrom 98,
  • na zásobníku vznikne nová lokálna premenná S s hodnotou 98 ... robot nakreslí čiaru, otočí sa a volá Spir s parametrom 101,
  • na zásobníku vznikne nová lokálna premenná S s hodnotou 101 ... robot už nič nekreslí ani sa nič nevolá ... procedúra Spir končí, t.j.
    • zabudnú sa všetky lokálne premenné na tejto úrovni, t.j. premenná S s hodnotou 101 a riadenie sa vráti za posledné volanie procedúry Spir - tá ale končí, t.j.
    • zabudnú sa všetky lokálne premenné na tejto úrovni, t.j. premenná S s hodnotou 98 a riadenie sa vráti za posledné volanie procedúry Spir - tá ale končí, t.j.
  • zabudnú sa všetky lokálne premenné na tejto úrovni, t.j. premenná S s hodnotou 95 a riadenie sa vráti za posledné volanie procedúry Spir - tá ale končí, t.j.
  • zabudnú sa všetky lokálne premenné na tejto úrovni, t.j. premenná S s hodnotou 92 a riadenie sa vráti za posledné volanie procedúry Spir - teda do hlavného programu - na príkaz Robot.Free.

Nakoľko rekurzívne volanie procedúry je iba na jednom mieste, za ktorým už nenasledujú ďalšie príkazy procedúry, toto rekurzívne volanie sa dá ľahko prepísať cyklom while. Rekurzii, v ktorej za rekurzívnym volaním nie sú ďalšie príkazy, hovoríme chvostová rekurzia (jediné rekurzívne volanie je posledným príkazom procedúry). Predchádzajúcu ukážku môžeme prepísať napr. takto:

  while S <= 100 do
  begin
    Robot.Fd(S);
    Robot.Lt(60);
    Wait(1);
    S := S + 3;
  end;

Rekurziu môžeme používať nielen pri kreslení pomocou robota, ale napr. aj pri výpise do textovej plochy. V nasledujúcom príklade vypisujeme pod seba čísla N, N-1, N-2, ..., 2, 1:

  procedure Vypis(N: Integer);
  begin
    if N < 1 then
      // nič nerob len skonči
    else
    begin
      WriteLn(N);
      Vypis(N - 1);
    end;
  end;
 
begin
  WriteLn('start');
  Vypis(30);
  ReadLn;
end.

Zrejme je veľmi jednoduché prepísať to bez použitia rekurzie, napr. pomocou while-cyklu. Poexperimentujme, a vymeňme dva riadky: vypisovanie do textovej plochy (WriteLn) s rekurzívnym volaním (Vypis). Po spustení vidíte, že aj táto nová rekurzívna procedúra sa dá prepísať len pomocou while-cyklu (resp. for-cyklu), ale jej činnosť už nemusí byť pre každého na prvý pohľad až tak jasná - odtrasujte túto zmenenú verziu:

procedure Vypis(N: Integer);
begin
  if N < 1 then
    // skonči
  else
  begin
    Vypis(N-1);
    WriteLn(N);
  end;        // už to nie je chvostová rekurzia
end;


Pravá rekurzia

Rekuzie, ktoré už nie sú obyčajné chvostové, sú na pochopenie trochu zložitejšie. Pozrime takéto kreslenie špirály:

procedure Spir(S: Real);
begin
  if S > 100 then
    Robot.PC := clRed     // a skonči
  else
  begin
    Robot.Fd(S);
    Robot.Lt(60);
    Wait(1);
    Spir(S + 3);
    Robot.Fd(S);
    Robot.Lt(60);
    Wait(1);
  end;
end;

rekurzia

Nejaké príkazy sú pred aj za rekurzívnym volaním. Aby sme to lepšie rozlíšili, triviálny prípad nastaví inú farbu pera. Teraz trasujte jej volanie, napr. pre Spir(189)...

Aj takéto rekurzívne volanie sa dá prepísať pomocou dvoch cyklov:

  Pocet := 0;
  while S <= 100 do           // čo sa deje pred rekurzívnym volaním
  begin
    Robot.Fd(S);
    Robot.Lt(60);
    S := S + 3;
    Inc(Pocet);
    Wait(1);
  end;
  Robot.PC := clRed;          // triviálny prípad
  while Pocet > 0 do          // čo sa deje po vynáraní z rekurzie
  begin
    S := S - 3;
    Robot.Fd(S);
    Robot.Lt(60);
    Dec(Pocet);
    Wait(1);
  end;

Aj v ďalších príkladoch môžete vidieť pravú rekurziu. Napr. vylepšená procedúra Vypis vypisuje postupnosť čísel:

procedure Vypis(N: Integer);
begin
  if N < 1 then
    // skonči
  else
  begin
    WriteLn(N);
    Vypis(N - 1);
    WriteLn(N));
  end;
end;

Keď ako triviálny prípad pridáme riadok s hviezdičkami, tento sa vypíše niekde medzi postupnosť čísel. Viete, kde sa vypíšu tieto hviezdičky?

procedure Vypis(N: Integer);
begin
  if N < 1 then
    WriteLn('***')
  else
  begin
    WriteLn(N);
    Vypis(N - 1);
    WriteLn(N);
  end;
end;

V ďalších príkladoch s robotom využívame veľmi užitočnú procedúru Poly:

procedure Poly(N: Integer; S, U: Real);
begin
  while N > 0 do
  begin
    Robot.Fd(S);
    Robot.Lt(U);
    Dec(N);
  end;
end;

Ktorú môžeme cvične prerobiť na rekurzívnu:

procedure Poly(N: Integer; S, U: Real);
begin
  if N > 0 then
  begin
    Robot.Fd(S);
    Robot.Lt(U);
    Poly(N - 1, S, U);
  end;
end;

Zistite, čo kreslia procedúry Stvorec a Stvorec1.

procedure Stvorec(A: Integer);
begin
  if A > 100 then
     // nič nerob len skonči
  else
  begin
    Poly(4, A, 90);
    Stvorec(A + 5);
  end;
end;
 
procedure Stvorec1(A: Integer);
begin
  if A > 100 then
    Robot.Lt(180)    // a skonči
  else
  begin
    Poly(4, A, 90);
    Stvorec1(A + 5);
    Poly(4, A, 90);
  end;
end;

Všetky tieto príklady s pravou rekurziou by ste mali vedieť jednoducho prepísať bez rekurzie pomocou niekoľkých cyklov.

V nasledujúcom príklade počítame Faktoriál prirodzeného čísla N, pričom vieme, že

  • 0! = 1 ... triviálny prípad
  • n! = (n-1)!*n ... rekurzívne volanie
function Faktorial(N: Integer): Integer;
begin
  if N = 0 then
    Result := 1
  else
    Result := Faktorial(N - 1) * N;
end;

Triviálnym prípadom je tu úloha, ako vyriešiť 0!. Toto vieme aj bez rekurzie, lebo je to 1. Ostatné prípady sú už rekurzívne: na to, aby sme vyriešili zložitejší problém (N faktoriál), najprv vypočítame jednoduchší (N-1 faktoriál) - zrejme pomocou rekurzie - a z neho skombinujeme (násobením) požadovaný výsledok. Hoci toto riešenie nie je chvostová rekurzia (po rekurzívnom volaní Faktorial sa musí ešte násobiť), vieme ho jednoducho prepísať pomocou cyklu.


Binárne stromy

Medzi informatikmi sú veľmi populárne binárne stromy. Najlepšie sa kreslia pomocou robota. Hovoríme, že binárne stromy majú nejakú svoju úroveň N a sú definované takto:

  • ak je úroveň stromu N = 0, nakreslí sa len čiara nejakej dĺžky;
  • pre N >= 1, sa najprv nakreslí čiara, potom sa na jej konci nakreslí najprv vľavo binárny strom (N-1). úrovne a potom vpravo opäť binárny strom (N-1). úrovne (hovoríme im podstromy) - po nakreslení týchto podstromov sa ešte vráti späť po prvej nakreslenej čiare;
  • po skončení kreslenia stromu ľubovoľnej úrovne sa robot nachádza na mieste, kde začal kresliť;
  • ľavé aj pravé podstromy môžu mať buď rovnako veľké konáre ako kmeň stromu, alebo sa môžu v nižších úrovniach zmenšovať.

Najprv ukážeme binárny strom, ktorý má vo všetkých úrovniach rovnako veľké podstromy:

procedure Strom(N: Integer);
begin
  if N = 0 then
  begin              // triviálny prípad
    Robot.Fd(30);
    Robot.Fd(-30);
  end
  else
    with Robot do
    begin
      Fd(30);
      Lt(45);         // natoč sa na kreslenie ľavého podstromu
      Strom(N - 1);   // nakresli ľavý podstrom (n-1). úrovne
      Rt(90);         // natoč sa na kreslenie pravého podstromu
      Strom(N - 1);   // nakresli pravý podstrom (n-1). úrovne
      Lt(45);         // natoč sa do pôvodného smeru
      Fd(-30);        // vráť sa na pôvodné miesto
    end;
  Wait(1);
end;

binárny strom

Binárne stromy môžeme rôzne vylepšovať, napr. vetvy stromu sa vo vyšších úrovniach môžu rôzne skracovať, uhol o ktorý je natočený ľavý a pravý podsrom môže byť tiež rôzny. V tomto riešení si všimnite, kde je triviálny prípad:

procedure Strom(N: Integer; V: Real);
begin
  with Robot do
  begin
    Fd(V);
    if N > 0 then
    begin
      Lt(40);
      Strom(N - 1, V * 0.7);
      Rt(75);
      Strom(N - 1, V * 0.6);
      Lt(35);
    end;
    Fd(-V);
  end;
end;

Strom(5, 80)

Ak využijeme náhodný generátor, môžme vytvárať úplne rôzne stromy:

var
  Robot: TRobot;
 
  procedure Strom(N: Integer; V: Real);
  var
    Uhol1, Uhol2, V1, V2: Real;
  begin
    with Robot do
    begin
      PW := 2 * N + 1;
      Fd(V);
      if N = 0 then
      begin
        PC := clGreen;
        Point(10);
        PC := clMaroon;
      end
      else
      begin
        Uhol1 := 20 + Random(40);
        Uhol2 := 20 + Random(40);
        V1 := V * (0.4 + Random(30) / 100);
        V2 := V * (0.4 + Random(30) / 100);
        Lt(Uhol1);
        Strom(N - 1, V1);
        Rt(Uhol1 + Uhol2);
        Strom(N - 1, V2);
        Lt(Uhol2);
      end;
      Fd(-V);
    end;
  end;
 
begin
  CS;
  Robot := TRobot.Create(Image1.Width div 2, Image1.Height - 20);
  Robot.PC := clMaroon;
  Strom(4 + Random(4), 50 + Random(50));
  Robot.Free;
end;

binárny strom
binárny strom
binárny strom

V tomto riešení si všimnite, kde sme zmenili hrúbku pera, aby sa strom kreslil rôzne hrubý v rôznych úrovniach. Tiež sa tu na posledných "konároch" nakreslili zelené listy - pridali sme ich v triviálnom prípade.

V nasledujúcom riešení vzniká zaujímavý efekt tým, že v triviálnom prípade urobí robot malý úkrok vpravo a teda sa ďalej nepokračuje v tom bode ako sa začalo, ale je tam malá chyba. Táto chyba sa stále zväčšuje a zväčšuje, až pri nakreslení kmeňa stromu je už dosť veľká:

procedure Strom(N: Integer; V: Real);
begin
  with Robot do
    if N = 0 then    // s hrubšími vetvami
    begin
      Fd(V);
      Rt(90);
      Fd(1);
      Lt(90);
      Fd(-V);
    end
    else
    begin
      Fd(V);
      Lt(45);
      Strom(N - 1, V / 2);
      Rt(90);
      Strom(N - 1, V / 2);
      Lt(45);
      Fd(-V);
    end;
  Wait(1);
end;

binárny strom

Nakreslime strom, ktorý sa rozvetvuje nie na dve ale na tri časti - nazýva sa ternárny strom:

procedure Strom3(N: Integer; A: Real);
var
  I: Integer;
begin
  if N = 1 then
    Poly(2, A, 180)
  else
    with Robot do
    begin
      Fd(A);
      Lt(45);
      for I := 1 to 3 do
      begin
        Strom3(N - 1, A / 2);
        Rt(45);
      end;
      Lt(90);
      Fd(-A);
    end;
  Wait(1);
end;

ternárny strom

Ak vložíme do formulára posúvač (napr. TrackBar1 s Min = 0 a Max = 10, Orientation = trVertical), môžeme sledovať postupný rast stromu, napr. takto

procedure TForm1.TrackBar1Change(Sender: TObject);
var
  Robot: TRobot;
 
  procedure Strom(N: Integer; V: Real);
  begin
    with Robot do
    begin
      Fd(V);
      if N = 0 then
      begin
        PC := clGreen;
        Point(8);
        PC := clMaroon;
      end
      else
      begin
        Lt(40);
        Strom(N - 1, V * 0.6);
        Rt(75);
        Strom(N - 1, V * 0.7);
        Lt(35);
      end;
      Fd(-V);
    end;
  end;
 
begin
  CS;
  Robot := TRobot.Create(Image1.Width div 2, Image1.Height - 20);
  Robot.PW := 3;
  Robot.PC := clMaroon;
  Strom(TrackBar1.Position, 80);
  Robot.Free;
end;

binárny strom s posúvačom
binárny strom s posúvačom

Binárny strom sa dá nakresliť viacerými spôsobmi aj nerekurzívne. V jednom z nich využijeme pole robotov, pričom každý z nich nakreslí len jednu úsečku. Idea algoritmu je takáto:

  • prvý robot nakreslí koreň stromu - prvú úsečku dĺžky D
  • na jeho konci (na momentálnej pozícii tohto robota) sa vyrobia dva nové roboty, pričom jeden má natočenie o 40 vľavo a druhý o 50 vpravo
  • hodnota D sa zníži napr. na D * 0.6
  • všetky nové vytvorené roboty prejdú v svojom smere dĺžku D a opäť sa na ich pozíciách vytvoria nové roboty otočené o 40 a 50 stupňov, a D sa opäť zníži
  • toto sa opakuje N krát a takto sa nakreslí kompletný strom
var
  R: array [1..1023] of TRobot;
  Vsetky, Nove, Doteraz, I, J, Vyska: Integer;
  D: Real;
begin
  CS;
  Vyska := 3 + Random(8);
  Image1.Canvas.TextOut(0, 0, Format('výška = %d', [Vyska]));
  R[1] := TRobot.Create(Image1.Width div 2, Image1.Height - 20);
  Vsetky := 1;
  Nove := 1;
  D := 80;
  for I := 1 to Vyska do
  begin
    Doteraz := Vsetky;
    for J := Nove to Vsetky do
    begin
      R[J].Fd(D);
      if I = Vyska then
      begin
        R[J].PC := clGreen;
        R[J].Point(6);
      end
      else
      begin
        Inc(Vsetky);
        R[Vsetky] := TRobot.Create(R[J].X, R[J].Y, R[J].H - 40);
        Inc(Vsetky);
        R[Vsetky] := TRobot.Create(R[J].X, R[J].Y, R[J].H + 50);
      end;
    end;
    Nove := Doteraz + 1;
    D := D * 0.6;
    Wait(500);
  end;
  for I := 1 to Vsetky do
    R[I].Free;
  Image1.Canvas.Brush.Color := clWhite;
  Image1.Canvas.TextOut(0, Image1.Height - 20, Format('počet robotov = %d', [Vsetky]));
end;

binárny strom pomocou poľa robotov
binárny strom pomocou poľa robotov
binárny strom pomocou poľa robotov

Pre roboty na poslednej úrovni sa už ďalšie nevytvárajú, ale na ich koncoch sa nakreslí zelená bodka. Program na záver vypíše počet robotov, ktoré sa takto vyrobili.

Rekurzívne obrázky

Napíšeme procedúru, ktorá nakreslí obrázok Stvorce úrovne N, veľkosti A s týmito vlastnosťami:

  • pre N = 0 nerobí nič
  • pre N = 1 kreslí štvorec so stranou dĺžky A
  • pre N > 1 kreslí štvorec, v ktorom v každom jeho rohu (smerom dnu) je opäť obrázok Stvorce ale už zmenšený: úrovne N-1 a veľkosti A/3

Štvorce v každom rohu štvorca:

procedure Stvorce(N: Integer; A: Real);
var
  I: Integer;
begin
  if N = 0 then
     // nerob nič len skonči
  else
    for I := 1 to 4 do
    begin
      Robot.Fd(A);
      Robot.Lt(90);
      Wait(1);
      Stvorce(N - 1, A / 3);     // skúste: Stvorce(N - 1, A * 0.45);
    end;
end;

Uvedomte si, že to nie je chvostová rekurzia. Obrázok vyzerá takto (ďalšie sú malé modifikácie programu):

vnorené štvorce vnorené štvorce vnorené štvorce

Tesne pred rekurzívnym volaním otočíme robota o 30 stupňov a po návrate z rekurzie týchto 30 stupňov vrátime:

procedure Stvorce(N: Integer; A: Real);
var
  I: Integer;
begin
  if N > 0 then
    for I := 1 to 4 do
    begin
      Robot.Fd(A);
      Robot.Lt(90);
      Wait(1);
      Robot.Rt(30);
      Stvorce(N - 1, A / 3);
      Robot.Lt(30);
    end;
end;

vnorené štvorce

Rekurzívny obrázok na rovnakom princípe ale trojuholníkového tvaru navrhol poľský matematik Sierpiňský ešte v roku 1915:

procedure Trojuholniky(N: Integer; A: Real);
var
  I: Integer;
begin
  if N > 0 then
    for I := 1 to 3 do
    begin
      Robot.Fd(A);
      Robot.Lt(120);
      Wait(1);
      Trojuholniky(N - 1, A / 2);
    end;
end;

Sierpinského trojuholníky

Zaujímavé je to, že táto rekurzívna krivka sa dá nakresliť aj jedným ťahom (po každej čiare sa prejde len raz). Porozmýšľajte ako.

Ďalej ukážeme veľmi známu rekurzívnu krivku - snehovú vločku (známu tiež ako Kochova krivka):

var
  Robot: TRobot;
 
  procedure Vlocka(N: Integer; S: Real);
  begin
    if N = 0 then
    begin
      Robot.Fd(S);
      Wait(1);
    end
    else
    begin
      Vlocka(N - 1, S / 3);
      Robot.Rt(60);
      Vlocka(N - 1, S / 3);
      Robot.Lt(120);
      Vlocka(N - 1, S / 3);
      Robot.Rt(60);
      Vlocka(N - 1, S / 3);
    end;
  end;
 
var
  I: Integer;
begin
  Robot := TRobot.Create(Image1.Width div 2, Image1.Height - 50);
  for I := 1 to 3 do
  begin
    Vlocka(3, 150);
    Robot.Lt(120);
  end;
  Robot.Free;
end;

snehová vločka
snehová vločka
snehová vločka

Tretí obrázok vznikol tak, že sme v hlavnom cykle Robot.Lt(120) nahradili príkazom Robot.Rt(120).



Fraktály



Špeciálnou skupinou rekurzívnych kriviek sú fraktály (pozri aj na wikipédii). Ešte pred érou počítačov sa s nimi "hrali" aj významní matematici (niektoré krivky podľa nich dostali aj svoje meno, aj snehová vločka je fraktálom a vymyslel ju švédsky matematik Koch). Zjednodušene by sme mohli povedať, že fraktál je je taká krivka, ktorá sa skladá zo svojich zmenšených kópií. Keby sme sa na nejakú jej časť pozreli lupou, videli by sme opäť skoro tú istú krivku. Napr. aj binárne stromy a aj snehovú vločku by sme mohli považovať za fraktály.

Začneme veľmi jednoduchou, tzv. C-krivkou:

var
  Robot: TRobot;
 
  procedure Ckrivka(N: Integer; S: Real);
  begin
    if N = 0 then
      Robot.Fd(s)
    else
    begin
      Ckrivka(N - 1, S);
      Robot.Lt(90);
      Ckrivka(N - 1, S);
      Robot.Rt(90);
    end;
    Wait(1);
  end;
 
begin
  Robot := TRobot.Create(200, 100);
  Ckrivka(8, 4);         // skúste: Ckrivka(11, 2);
  Robot.Free;
end;

Ckrivka(8, 4)
Ckrivka(11, 2)

C-krivke sa veľmi podobá Dračia krivka, ktorá sa skladá z dvoch "zrkadlových" procedúr: LDrak a PDrak. Problémom u týchto dvoch rekurzívnych procedúr je to, že prvá rekurzívne volá samu seba ale aj druhú a druhá volá seba aj prvú. Tým problémom je poradie, v akom ich zadefinujeme: ak bude najprv prvá a až za ňou druhá, prvá nemôže volať druhú. Ak to bude naopak, tak máme ten istý problém. Jednou z možností je použitie direktívy forward:

var
  Robot: TRobot;
 
  procedure PDrak(N: Integer; S: Real); forward;
 
  procedure LDrak(N: Integer; S: Real);
  begin
    if N = 0 then
      Robot.Fd(s)
    else
    begin
      LDrak(N - 1, S);
      Robot.Lt(90);
      PDrak(N - 1, S);
    end;
    Wait(1);
  end;
 
  procedure PDrak(N: Integer; S: Real);
  begin
    if N = 0 then
      Robot.Fd(S)
    else
    begin
      LDrak(N - 1, S);
      Robot.Rt(90);
      PDrak(N - 1, S);
    end;
    Wait(1);
  end;
 
begin
  Robot := TRobot.Create(300, 200);
  LDrak(8, 6);
  Robot.Free;
end;

LDrak(8, 6)
LDrak(11, 3)
LDrak(13, 2)

Táto direktíva označuje, že uvedená procedúra bude definovaná až neskôr, ale kompilátor o tejto procedúre už vie a teda ju môžeme volať (ešte pred jej definíciou).

Iným riešením je vzájomné vnorenie procedúr:

var
  Robot: TRobot;
 
  procedure LDrak(N: Integer; S: Real);
 
    procedure PDrak(N: Integer; S: Real);
    begin
      if N = 0 then
        Robot.Fd(S)
      else
      begin
        LDrak(N - 1, S);
        Robot.Rt(90);
        PDrak(N - 1, S);
      end;
      Wait(1);
    end;
 
  begin         // LDrak
    if N = 0 then
      Robot.Fd(S)
    else
    begin
      LDrak(N - 1, S);
      Robot.Lt(90);
      PDrak(N - 1, S);
    end;
    Wait(1);
  end;
 
begin
  Robot := TRobot.Create(300, 200);
  LDrak(11, 5);
  Robot.Free;
end;

Obe riešenia sú rovnako správne. Všimnite si, že robot pri kreslení krivky, neprejde po žiadnej čiare viackrát.

Dračiu krivku môžeme nakresliť aj len jednou procedúrou - táto bude mať o jeden parameter viac a to, či je to ľavá alebo pravá verzia procedúry:

var
  Robot: TRobot;
 
  procedure Drak(N: Integer; S: Real; U: Integer);
  begin
    if N = 0 then
      Robot.Fd(S)
    else
    begin
      Drak(N - 1, S, 90);
      Robot.Lt(U);
      Drak(N - 1, S, -90);
    end;
    Wait(1);
  end;
 
begin
  Robot := TRobot.Create;
  Drak(14, 2, 90);
  Robot.Free;
end;

dračia krivka

V literatúre je veľmi známou Hilbertova krivka, ktorá sa tiež skladá z dvoch zrkadlových častí (ako dračia krivka) a preto ich definujeme jednou procedúrou a parametrom U (t.j. uhol pre ľavú a pravú verziu):

var
  Robot: TRobot;
 
  procedure Hilbert(N: Integer; S: Real; U: Integer);
  begin
    if N > 0 then
    begin
      Robot.Lt(U);
      Hilbert(N - 1, S, -U);
      Robot.Fd(S);
      Robot.Rt(U);
      Hilbert(N - 1, S, U);
      Robot.Fd(S);
      Hilbert(N - 1, S, U);
      Robot.Rt(U);
      Robot.Fd(S);
      Hilbert(N - 1, S, -U);
      Robot.Lt(U);
      Wait(1);
    end;
  end;
 
begin
  Robot := TRobot.Create(Image1.Width - 50, Image1.Height - 10);
  Hilbert(5, 7, 90);             // skúste: Hilbert(7, 2, 90);
  Robot.Free;
end;

Hilbert(5, 7, 90)
Hilbert(7, 2, 90)

Ďalšie inšpirácie na rekurzívne krivky môžete nájsť na wikipédii.


späť | ďalej