Programozási tételek megvalósítása

[Calyd]

Egy másik témában már írtam a programozási tételekről nyelvfüggetlenül. Úgy gondoltam, hogy hasznos lenne ezekről kicsit konkrétabban is írni. Mivel főleg a Pascal-alapú nyelvekben vagyok otthon, így ide írok. Az algoritmusok szövegesek lesznek. Ennek több oka van. Egyrészt általánosabb, mint a kód, másrészt elég "kódközeli" lesz ahhoz, hogy könnyen meg lehessen valósítani. Itt nem írom le a specifikációt sem, azt megtettem az említett témában. Megemlíteném, hogy az algoritmusok fentről lefelé tervezettek. Ez nagyjából azt jelenti, hogy bizonyos esetekben a felhasznált függvényeket, eljárásokat később fejtem ki, mert logikusan így következik. Programírás során során azonban, ugye pont fordítva kell. Szintén fontos, hogy bizonyos esetkben az algoritmikusan függvény használatát diktálja a logikám, de ez nem minden fordítóval valósítható meg (pl. Turbo Pascal nem tud összetett típust értékül adni függvénynek). Ilyen esetekben eljárásként kell megvalósítani a leírtakat. Még egy megjegyzés: a fórum "kód" lehetősőgét fogom használni, mert így megmaradnak az átláthatóságért felelős "felesleges" szóközök. Sajnos emiatt azonban nem tudom vastagítani a fontosabb kulcsszavakat.

 

1.: A másolás:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

   TFElem=...;
   TFElemek=Tömb(1..MaxN);

Eljárás Másolás (Konstans X:TElemek; N:Egész; Változó Y:TFElemek);
Változó i:Egész;
   Ciklus i:=1-től N-ig
      Y(i):=F(X(i));
   Ciklus vége;
Eljárás vége;

Függvény F (elem:TElem):TFElem;
   {feladatfüggő, hogy kell-e egyáltalán ilyet használni, így az is, hogy ez pontosan mit takar}
Függvény vége;

 

2.: Az eldöntés:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

Eljárás Eldöntés (Konstans X:TElemek; N:Egész; Változó VanE:Logikai);
   Változó i:Egész;

   i:=1;
   Ciklus amíg i<=N és nem T(X(i)) {feladatfüggő tulajdonságfüggvény}
      i:=i+1;
   Ciklus vége;
   VanE:=i<=N;
Eljárás vége;

Itt fontos megjegyezni, hogy a fordítók a ciklus feltételének kiértékelésében eltérőek lehetnek, és problémákhoz vezet. Például, ha az utolsó (N-ik) elemet megvizsgáltuk, és nem T-tulajdonásgú, akkor eggyel növeljük a ciklusváltozót. A következő feltételvizsgálatnál az "i<=N" feltétel már nyilván hamis, így a második részt már nem kéne kiértékelni. Azonban vannak fordítók, mely kiértékelik, azaz megnézik a T(X(N+1))-et is. Ez viszont túlindexelést eredményez, ha N=MaxN. Ez orvosolható például úgy, hogy a ciklus feltételében szigoró kisebbséget kérünk, és a tömb utolsó elemét külön megviszgáljuk.

 

 

3.: A kiválasztás:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

Eljárás Kiválasztás (Konstans X:TElemek; N:Egész; Változó Sorsz:Egész);
   Változó i:Egész;

   i:=1;
   Ciklus amíg nem T(X(i)) {feladatfüggő tulajdonságfüggvény}
      i:=i+1;
   Ciklus vége;
   Sorsz:=i;
Eljárás vége;

 

4.: A lineáris keresés:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

Eljárás LineárisKeresés (Konstans X:TElemek; N:Egész; Változó VanE:Logikai; Sorsz:Egész);
   Változó i:Egész;

   i:=1;
   Ciklus amíg i<=N és nem T(X(i)) {feladatfüggő tulajdonságfüggvény}
      i:=i+1;
   Ciklus vége;
   VanE:=i<=N;
   Ha VanE akkor Sorsz:=i;
Eljárás vége;

 

5.: A megszámolás:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

Eljárás Megszámolás (Konstans X:TElemek; N:Egész; Változó Darab:Egész);
   Változó i:Egész;

   Darab:=0;
   Ciklus i:=1-től N-ig
      Ha T(X(i)) {feladatfüggő tulajdonságfüggvény} akkor Darab:=Darab+1;
   Ciklus vége;
Eljárás vége;

 

6.: A maximum kiválasztás:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

Eljárás MaximumKiválasztás (Konstans X:TElemek; N:Egész; Változó max:Egész);
   Változó i:Egész;

   max:=1;
   Ciklus i:=2-től N-ig
      Ha X(i)>X(max) akkor max:=i;
   Ciklus vége;
Eljárás vége;

 

7.: A kiválogatás:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

   TIndexek=Tömb(1..MaxN:Egész);

Eljárás Kiválogatás (Konstans X:TElemek; N:Egész; Változó Darab:Egész; Y:TIndexek);
   Változó i:Egész;

   Darab:=0;
   Ciklus i:=1-től N-ig
      Ha T(X(i)) {feladatfüggő tulajdonságfüggvény} akkor
         Darab:=Darab+1;
         Y(Darab):=i;
      Elágazás vége;
   Ciklus vége;
Eljárás vége;

 

Mára ennyi. Remélhetőleg holnap lesz időm, és akkor leírok két rendezést is.

[Calyd]

Akkor íme a két rendezés. Már említettem egy másik témában, de itt is megteszem: ezek belsõ rendezések, azaz feltesszük, hogy a memória elegendõ lesz a rendezés során.

 

8.: Egyszerû cserés rendezés:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

Eljárás CserésRendezés (Konstans N:Egész; Változó X:TElemek); {az X bemeneti sorozat változó!}
   Változó i,j:Egész;

   Ciklus i:=1-tõl N-1-ig
      Ciklus j:=i+1-tõl N-ig
         Ha X(i)>X(j) akkor Csere(X(i),X(j));
      Ciklus vége;
   Ciklus vége;
Eljárás vége;

Eljárás Csere (Változó e,f:TElem);
   Változó s:TElem;

   s:=e;
   e:=f;
   f:=s;
Eljárás vége;

 

8.: Rendezés minimumkiválasztással:

 

Konstans MaxN:Egész;
Típus
   TElem=...;
   TElemek=Tömb(1..MaxN:TElem);

Eljárás MinKivRendezés (Konstans N:Egész; Változó X:TElemek); {az X bemeneti sorozat változó!}
   Változó i,min:Egész;

   Ciklus i:=1-tõl N-1-ig
      min:=i; {itt történik egy minimum kiválasztás}
      Ciklus j:=i+1-tõl N-ig
         Ha X(min)>X(j) akkor min:=j;
      Ciklus vége;
      Csere(X(i),X(min));
   Ciklus vége;
Eljárás vége;

Eljárás Csere (Változó e,f:TElem);
   Változó s:TElem;

   s:=e;
   e:=f;
   f:=s;
Eljárás vége;