Cykly v Pascalu

while - do

Cyklus má tvar

while <podmínka> do <příkaz>;

Probíhá následovně: provede se <podmínka>, a pokud platí, provede se <příkaz> a vše se znovu opakuje. Pokud podmínka neplatí, cyklus je ukončen (pokračuje se dalším příkazem). Z výše uvedeného je zřejmé, že pokud podmínka neplatí ani na začátku, neprovede se příkaz ani jednou.

Pokud má v cyklu probíhat více příkazů, samozřejmě si můžeme pomoci pomocí programových závorek begin a end (kdekoli lze napsat příkaz, je možné napsat klíčové slovo begin, řadu příkazů, a klíčové slovo end).

repeat - until

Cyklus má tvar

repeat
 <příkaz>;
  <příkaz>;
  ...
  <příkaz>;
until podmínka;

V programu se pokračuje i za slovem repeat. Když se dojde k podmínce, otestuje se, a není-li ještě splněna, vrací se běh programu ke klíčovému slovu repeat. Je tedy zřejmé, že tento cyklus vždy proběhne alespoň jednou (i kdyby podmínka byla splněna již předtím). Za zmínku také stojí, že mezi klíčovými slovy repeat a until může být více příkazů (nemusíme psát begin a end).

Ve cvičení AII uvádím samé kratší příklady. Použití výše uvedených cyklů v takto krátkých příkladech zpravidla není tou nejjednodužší variantou, jak problém řešit. Ilustruje to i následující příklad:

Příklad: spočtěte, kolik je ve větě mezer (písmen "e" a podobně).

Řešení: Větu napíšeme do Edit1. Připravíme si tlačítko, jehož stisknutím se mezery spočítají. Použijeme cyklus while-do; pro počet mezer si připravíme celočíselnou proměnnou, pro zjednodušení manipulace s řetězcem pak ještě proměnnou typu string.

procedure Button1Click(Sender:TObject);
  var
    i : integer;
    s : string;
  begin
    i:=0;
    s:=Edit1.Text;
    while pos(' ',s)>0 do 
      begin
        i:=i+1;
        delete(s,pos(' ',s),1);
      end;
    Button1.Caption:=IntToStr(i);
  end;

Především si všimněte, že každému begin odpovídá jeden end; (se středníkem; ten s tečkou značí konec programu a je to úplně jiný end). Častá chyba je některý end do programu nenapsat. Ve výše uvedené ukázce je jejich spojitost názorná díky tomu, že automaticky generované části jsou psány šedivě.

Pro odstranění mezery (aby nebyla započtena znovu) je použita procedura delete. Poslední parametr označuje délku mazané části (jeden znak). V tomto případě by bylo opět jednodušší (a pro počítač rychlejší) použít cyklus for-do. Procedura by vypadala následovně:

procedure Button1Click(Sender:TObject);
  var
    i,j : integer;
    s : string;
  begin
    i:=0;
    s:=Edit1.Text;
    for j:=1 to length(s) do
      if s[j]=' ' then i:=i+1;
    Button1.Caption:=IntToStr(i);
  end;

Jiná situace by byla, kdyby se měl počítat počet výskytů nějakého krátkého řetězce, uvedeného například v Edit2, v dlouhém řetězci v Edit1. Například mějme v Edit1 zapsán text "sešel jsem se se sestrou" a v Edit2 text "se". Obsluha tlačítka by pak vypadala následovně:

procedure Button1Click(Sender:TObject);
  var
    i : integer;
    s,a : string;
  begin
    i:=0;
    s:=Edit1.Text;
    a:=Edit2.Text;
    while pos(a,s)>0 do 
      begin
        i:=i+1;
        delete(s,pos(a,s),length(a));
      end;
    Button1.Caption:=IntToStr(i);
  end;

Zde již je použití cyklu while-do oprávněné (přeložený program s cyklem for-do by nebyl o mnoho rychlejší, zato o mnoho komplikovanější).

//cyklus pro všechna čísla od 0 do 11 s krokem 0,375:

x:=0;
while x<=11 do
  begin {nějaké příkazy}
    x:=x+0.375;
  end;

příklad: výrazem x_i+1 = (x_i*7+1) mod 11 a prvním prvkem 1 je definována řada. Kolik členů této řady je třeba sečíst, aby součet byl větší než sto?

Řešení v Delphi asi bude nejlepší vytvořit jako obsluhu nějakého prvku, buď tlačítka, nebo třeba nápisu (Label). Můžeme někam umístit například nápis "Kolik sečíst?" (jako Label1) a pro událost (Event) "OnClick" vytvořit obslužný program:

procedure TForm1.Label1Click(Sender: TObject);
  var
    x,n,soucet: integer;
begin
  x := 1;
  soucet := 0;
  n := 0;
  while soucet<100 do
    begin
      soucet := soucet + x;
      n := n+1;
      x := (x*7+1) mod 11;
    end;
  Label1.Caption:='Je třeba sečíst '
    + IntToStr(n)
     + ' prvků';
end;

Po spuštění programu pak na nápis klikneme a dozvíme se, že je třeba sečíst 19 prvků. Kdybychom těch 19 prvků chtěli vidět, můžeme si přidat někam komponentu Memo1 a mezivýsledky zapisovat do ní:

procedure TForm1.Label1Click(Sender: TObject);
  var
    x,n,soucet: integer;
begin
  x := 1;
  soucet := 0;
  n := 0;
  Memo1.Lines.Clear;
  while soucet<100 do
    begin
      soucet := soucet + x;
      n := n+1;
      Memo1.Lines.Add(
        IntToStr(n)
         +'. = '
          +IntToStr(x));
      x := (x*7) mod 11;
    end;
  Label1.Caption:='Je třeba sečíst '
    + IntToStr(n)
     + ' prvků';
  Memo1.Lines.Add('Součet je '+IntToStr(soucet)+'.');
end;

Je třeba správně zvolit řádek, kam dát vypisování - o řádek níže by již byla vypisována jiná hodnota x, o řádek výše by bylo špatné pořadové číslo (počítání od nuly bylo zvoleno proto, aby na konci v n byla správná hodnota). Řádky, které není třeba psát, protože pocházejí z minulého příkazu, nebo jsou vygenerované, jsou opět šedou barvou.
Poslední poznámka - nezapomeňte u mema na svislý posuvník, nebo alespoň udělejte dost velké okno.

příklad: načtěte textový soubor. Spočítejte, kolik je v něm písmen "a" (malá/velká).

Třídění: bubble - sort

Nejsnazší metoda třídění - procházíme od začátku a pokud najdeme dvojici, která ještě není seřazena, zaměníme je. Pamatujeme si, že je třeba ještě jednou projít, dojde-li k prohození.

Jiné řešení vychází z toho, že teoreticky může být třeba projít pole o n prvcích nejvýše (n-1)krát; druhý poznatek je, že hned při prvním průchodu se na poslední pozici dostane největší prvek, takže ten již není třeba kontrolovat (při každém průchodu lze cyklus zkrátit o další prvek). Teoretický nejvyšší možný počet průchodů je tedy n-1, pokud zvolíme pevný počet průchodů, bude třeba (n-1)*(n-1)/2 porovnání. Při probírání dynamických datových struktur si vysvětléme, že operace porovnání může být mnohem obtížnější, než operace prohození (například u českých příjmení řádově 100x časově náročnější).

První (oblíbenější) řešení si předvedeme na setřídění 10 náhodných čísel v poli a. Nadeklarujeme si pole:
var a : array[1..10] of integer;
Ještě budeme potřebovat proměnnou prohození typu Boolean (ano-ne) a nějakou proměnnou pro cyklus (i). Protože Pascal nemá operaci prohození, musíme použít výměnu přes pomocnou proměnnou, řekněme x.

Pole náhodných čísel vygenerujeme pomocí funkce random, pomocí cyklu for-do:
for i:=1 to 10 do a[i]:= random(100)/10; ,
čímž se pole naplní čísly od nuly do 9,9 s krokem 0,1.
V našem případě ale ponechám čísla celočíselná - zkuste si FloatToStr a uvidíte proč.

Je dobré si na jedno tlačítko připravit naplnění pole a jeho vypsání, například do mema, a na další teprve jeho setřídění. Budeme tedy potřebovat formulář se dvěma tlačítky a s komponentou Memo. Třídit ale zatím budeme pole, a ne řádky v memo1. Aby bylo možné tyto akce takto rozdělit, je nutné pole a deklarovat jako globální proměnnou, mimo definice procedur. Ostatní proměnné zachováme jako lokální, definované až uvnitř procedury. Deklarace pole pak bude vypadat následovně:

var
  Form1: TForm1;
  a : array[1..10] of integer;

První tlačítko bude mít následující obsluhu:

procedure TForm1.Button1Click(Sender: TObject);
  var
    i : integer;
begin
  Memo1.Lines.Clear;
  for i:=1 to 10 do begin
      a[i]:= random(100);
      Memo1.Lines.Add(IntToStr(a[i]));
    end;
end;

Druhé tlačítko pak provede samotné třídění. Na začátku každého průchodu se nastaví pomocná proměnná "prohozeni" na False a v případě, že se najde něco nepřehozeného, tak se nejprve přehodí, a pak se nastaví tato proměnná na True. Bude tedy vnější cyklus (vždy alespoň jeden průchod => testovací podmínka cyklu až na konci => repeat-until cyklus) a vnitřní cyklus (pro začátek na pevno, 9 porovnání, v případě potřeby s prohozeními):

procedure TForm1.Button2Click(Sender: TObject);
  var
    prohozeni : Boolean;
    i, x : integer;
begin
  //setřídění v poli
  repeat
    prohozeni := False;
    for i:=1 to 9 do   //jediný příkaz - netřeba begin-end
      if a[i]>a[i+1] then begin
          x:=a[i];
          a[i]:=a[i+1];
          a[i+1]:=x;
          prohozeni:=True;
        end;
  until not prohozeni;      
  //vypsání do Mema
  Memo1.Lines.Clear;
  for i:=1 to 10 do Memo1.Lines.Add(IntToStr(a[i]));
end;

Třídění: čeština v MS Windows

Textové řetězce v Pascalu lze samozřejmě také porovnat operátory menší, větší, větší nebo rovno atd. (zde máme výhodu oproti nerozšířenému jazyku C++), ale tímto postupem seřadíme řetězce podle ordinální hodnoty jejich jednotlivých znaků (to je číslo, kterým je znak reprezentován v počítači). Na počítačích s ASCII by to fungovalo, ale jen pro všechna velká, nebo všechna malá písmena. Znaky národní sady (to jsou ty s háčkami, čárkami a jinými značkami) ovšem v základním ASCII nejsou a byly by tedy všechny zařazeny až na konec, v pořadí svých ordinálních hodnot.

Pro třídění v jazyce, do kterého jsou lokalizována Windows, musíme tedy volat funkce Windows. Právě způsob volání představuje rozhodující zdržení při provádění třídění. Rychlost je přitom hlavní důvod, proč opustit bubble-sort a přejít na quick-sort (zde bych se ale odvolal na přednášky - na cvičení jej sice vysvětluji, ale zde by to bylo zbytečné).

Funkce jsou v zásadě dvě.

AnsiCompareText porovnává dva řetězce bez ohledu na velikost písmen (to je ta správná).

AnsiCompareStr bere ohled na velikost písmen, za nižší a tedy blíže začátku jsou považována velká písmena. To je většinou špatně.

Funkce AnsiStrComp porovnává jiný typ řetězců, který je do Delphi přejat z C++ (v Pascalu je řetězec definován tak, že na nulté pozici (=jako úplně první znak) je jeho délka, kdežto v C byl řetězec definován tak, že končí znakem č. 0 - a nemůže tedy tento znak obsahovat). Tento typ označujeme jako Pchar:
.....function AnsiStrComp(S1, S2: PChar): Integer;
Práce s těmito řetězci je ale stejně složitá, jako s řetězci v C++, proto se jim snažíme vyhnout.

Všechny tři funkce jsou funkce, takže vrací hodnotu. Ale nikoli true - false, jak bychom u porovnání možná čekali. Vrátí číslo větší než nula, pokud je první porovnávaný řetězec větší, nebo menší než nula, pokud je menší, a v případě rovnosti (oba řetězce jsou stejné, u první funkce "až na velikost písmen") vrací nulu:

"Condition Return Value"
S1 > S2 , vrací číslo > 0
S1 < S2 , vrací číslo < 0
S1 = S2 , vrací číslo 0

Pokud si vytvoříme další tlačítko, celou obsluhu události "kliknutí na tlačítko" okopírujeme a použijeme v něm zmíněnou funkci, získáme následující úsek programu (poznámky: 1.: prohození probíhá přímo v komponentě memo, jejíž property "Lines" je ostatně také pole, 2.: převzaté řádky jsou opět označeny šedou barvou):

procedure TForm1.Button4Click(Sender: TObject);
  var
    prohozeni : Boolean;
    i : integer;
    s : string[250];
begin
  //setřídění přímo v komponentě Memo
  repeat
    prohozeni := False;
    for i:=0 to Memo1.Lines.Count - 2 do
      if AnsiCompareText(Memo1.Lines[i],
            Memo1.Lines[i+1]) >0 then begin
          s:=Memo1.Lines[i];
          Memo1.Lines[i]:=Memo1.Lines[i+1];
          Memo1.Lines[i+1]:=s;
          prohozeni:=True;
        end;
  until not prohozeni;
  //výsledek se zobrazí, jakmile se ukončí obsluha události "Click",
  // nebo průběžně - záleží na nastavení prostředí Windows programem

end;

Třídění urychlí, pokud vypneme průběžné zobrazování mezivýsledků. Často bývá naopak zvykem průběžně uvádět, kolik prohození proběhlo (číslo klesá s blízkostí konce třídění). Obvyklé řešení je, že proměnná "prohození" je celočíselná, místo na false se nastavuje na nulu a při každém prohození se o jednu zvětší. Před řádkem "until prohozeni=0" se přidá zobrazení, například "Label2.Caption:=IntToStr(prohozeni);".

Poznámka - výsledný program je vpravo:

(ke stažení zde)

příklad: načtěte textový soubor d:\autoexec.bat. Seřaďte řádky podle abecedy a zase jej uložte. Zkoušejte pouze v učebně 308 ve Windows 98.