2015. május 9., szombat

Algoritmus leírása


Folyamatábra

Struktogram
Programozási feladattípusok (programozási tételek), a feladatmegoldás speciális kérdései. 
 A vizsgálni kívánt sorozatot megadhatjuk elemei felsorolásával vagy elemei kiszámítási módjával.
 
Feladattípusok

összegzés (a sorozat  elemeinek  összege,   szorzata, uniója stb.),
maximum-kiválasztás (a sorozat maximális, vagy   minimális értékű elemének kiválasztása),
megszámolás (adott tulajdonságú elemek száma a  sorozatban),
kiválogatás (sorozat  adott  tulajdonságú   elemeinek megadása),
Feladattípusok
kiválasztás (a vizsgált sorozat egy adott   tulajdonságú elemének megadása, ilyen elem  biztosan   szerepel a sorozatban),
eldöntés (van-e a vizsgált sorozatban  adott   tulajdonságú elem),
keresés (a vizsgált sorozat  egy adott   tulajdonságú elemének megadása, ilyen elem lehet, hogy nincs a sorozatban),
Feladattípusok
unió (két sorozatként ábrázolt halmaz egyesítése),
metszet (két sorozatként  ábrázolt halmaz közös  elemei),
összefuttatás (két rendezett sorozat egyesítése),
szétválogatás (egy sorozat kétféle tulajdonságú  elemeinek különválasztása),
Feladattípusok
rendezés (rendezetlen sorozat  elemeinek  átrendezése növekvő vagy csökkenő sorrendbe),
visszalépéses keresés (sorozatokból egy-egy elem meghatározása).


Összegzés: Ez a feladattípus egy sorozathoz egy értéket rendel.
A sorozat elemeinek összegét, szorzatát, unióját stb. kell előállítani.
A feladatok egy részénél az így kiszámított  értékkel esetleg még egyszerű műveletet kell végezni (pl.  osztani  az átlagszámításnál).
Az összegzés általános algoritmusa
Eljárás:
      S:=kezdőérték
      Ciklus I=1-től N-ig
         S:=S művelet A(I)
      Ciklus vége
   Eljárás vége.
Példa (egy 100 elemű tömb elemeinek összege)
Procedure osszegzes;
begin
  osszeg:=0;
      for i:=1 to 100 do
         osszeg:=osszeg+a[i];
end;
Maximum-kiválasztás
Ebben a feladatkörben adott egy N elemű sorozat.
A feladat ezen sorozat legnagyobb elemének meghatározása  (néha  csupán az értékére van szükség).
Hasonló feladat - csupán a < relációt kell >-ra cserélni - a minimum-kiválasztás.
A maximum-kiválasztás általános algoritmusa (1.)
Eljárás:
  MAXIMUM := A(1)
  SORSZAM := 1
Ciklus I=2-től N-ig
    Ha MAXIMUM < A(I) akkor   MAXIMUM := A(I)
   SORSZAM := I 
Ciklus vége
Eljárás vége.
Példa (Egy 100 elemű tömb legnagyobb elemének kiválasztása)
Procedure maximum;
begin
  max:=a[1];
  sorsz:=1;
  for i:=2 to 100 do
  begin
      if max < a[i] then
     begin
     max := a[i];
      sorsz:=i;
     end;
   end;
end;
A maximum-kiválasztás általános algoritmusa (2)
Eljárás:
   SORSZAM := 1
   Ciklus I=2-től N-ig
      Ha A(SORSZAM) < A(I) akkor SORSZAM := I
    Ciklus vége
    MAXIMUM  := A(SORSZAM)
Eljárás vége.
Példa (egy 100 elemű tömb legnagyobb elemének kiválasztása
Procedure maximum2;
begin
   sorsz:=1;
   for i:=2 to 100 do
      if a[sorsz] < a[i] then sorsz:=i;
    max:=a[sorsz];
end;

Megszámolás
A következő feladatok megoldása során egy  sorozathoz  egy számot rendelünk hozzá.
Rendelkezésünkre áll egy N elemű  sorozat és egy, a sorozat elemein értelmezett T tulajdonság.
Az a feladatunk, hogy a  T  tulajdonsággal  rendelkező  elemeket számoljuk meg.
Ügyeljünk arra, hogy az összegzés céljára szolgáló változó értékét kezdetben 0-ra kell állítani!
A megszámolás általános algoritmusa
Eljárás:
   DB:=0
   Ciklus I=1-től N-ig
      Ha A(I) T tulajdonságú akkor DB:=DB+1
   Ciklus vége
Eljárás vége.
Példa (Egy 100 elemű tömb elemei közül hány pozitív van)
Procedure pozitiv;
begin
   darab:=0;
   for i:=1 to 100 do
      if a[i] > 0 then darab:=darab+1;
end;

Kiválogatás
Ennél a feladattípusnál egy N elemű A sorozat összes T tulajdonsággal rendelkező elemét kell meghatározni.
Az eredmény egy B(M) sorozat lesz, ahol 0<=M<=N. 
M=0,  ha az A(N) sorozat egy eleme sem, M=N, ha az A(N) sorozat minden eleme T tulajdonságú.
A kiválogatás általános algoritmusa
Eljárás:
   M:=0
   Ciklus I=1-től N-ig
      Ha A(I) T tulajdonságú akkor M:=M+1 : B(M):=A(I)
   Ciklus vége
Eljárás vége.
Példa (egy száz elemű tömb pozitív elemeit gyűjtsük egy másik tömbbe)
Procedure pozitivtomb;
begin
   darab:=0;
   for i:=1 to 100 do
      if a[i] > 0 then
      begin
         darab:=darab+1;
         b[darab]:=a[i];
      end;
end;

Kiegészítés
A megoldásban gyakran - ha további  feldolgozásukra  nincs szükség - nem gyűjtjük ki az elemeket, hanem azonnal kiírjuk:
Eljárás:
  Ciklus I=1-től N-ig
     Ha A(I) T tulajdonságú akkor Ki: I,A(I)
   Ciklus vége
Eljárás vége.
Példa (egy 100 elemű tömb pozitív elemeinek kiíratása)
Procedure pozitivki;
begin
  for i:=1 to 100 do
     if a[i] > 0 then writeln(i,’ ., ‘,a[i]);
end;

Kiválasztás
Adott egy N elemű sorozat és egy, a sorozat elemein értelmezett T tulajdonság. Azt is tudjuk, hogy a  sorozatban  van legalább egy T tulajdonságú elem.
A feladat az első ilyen elem sorszámának meghatározása.
A kiválasztás algoritmusa
Eljárás:
   I:=1
   Ciklus amíg A(I) nem T tulajdonságú
      I:=I+1
   Ciklus vége
   SORSZAM:= I
Eljárás vége.
Példa (egy tömbben biztosan található első pozitív elem meghatározása)
Procedure elsopoz;
begin
   i:=1;
   while a[i] <= 0 do
   begin     
      i:=i+1;
   end;
   sorsz:=i;
end;
Eldöntés
Ez a feladattípus egy sorozathoz logikai értéket rendel.
A logikai érték "igaz"-at vesz fel,  ha  a  sorozatban  létezik adott (T) tulajdonságú elem, és "hamis"-at vesz fel, ha ilyen tulajdonságú elem nincs a sorozatban.
Az eldöntés általános algoritmusa
Eljárás:
   I:=1
   Ciklus amíg I<=N és A(I) nem T tulajdonságú
      I:=I+1
   Ciklus vége
   VAN:=(I<=N)
Eljárás vége.
Példa (egy 100 elemű tömbben van-e pozitív)
Procedure vanepoz;
begin
   i:=1;
   while (i <= 100) and (a[i] <= 0) do
   begin
      i:=i+1;
   end;
   van:=(i <= 100);
end;
Keresés
A keresés feladattípus egy sorozathoz egy elemet rendel.
A feladat lényege, hogy a sorozatban egy adott tulajdonságú (T) elemet kell meghatároznunk (magát az elemet vagy a sorozatbeli sorszámát szokás kérni).
Nem biztos, hogy a sorozatban van ilyen elem.
Keresés
A keresés hatékonyságát lényegesen  befolyásolhatja,  hogy rendezett vagy rendezetlen sorozatban keresünk: logaritmikus, illletve lineáris keresést használunk.
Amelyik feladatban lehet, használjuk ki a sorozat rendezettségét!

A lineáris keresés általános algoritmusa
Eljárás: lineáris keresés
   I:=1
   Ciklus amíg I<=N és A(I) nem T tulajdonságú
      I:=I+1
   Ciklus vége
   VAN:=(I<=N)
   Ha VAN akkor SORSZÁM:=I
Eljárás vége.
Példa (egy 100 elemű tömbben hányadik az első pozitív, ha van)
Procedure linearisker;
begin
   i:=1;
   while (i <= 100) and (a[i] <= 0) do
   begin
      i:=i+1;
   end;
   van:=(i<=100);
   if van then sorsz:=i;
end;

A logaritmikus keresés általános algoritmusa
Eljárás: logaritmikus keresés
      Be: X
      AlsoH = 1   FelsoH = n
      Ciklus vége
         K = (AH+FH)/2 egész része
         Ha X<A(K) akkor FH=K-1
         Ha X>A(K) akkor AH=K+1
      Ciklus amíg A(K)=X vagy AH>FH
      VAN:=(A(K)=X)
      Ha VAN akkor SORSZÁM:=K
   Eljárás vége.
Példa (egy 100 elemű rendezett tömbben keressük meg  egy tetszőleges elem sorszámát)
Procedure logaritmker;
begin
      readln(x);
      AlsoHatar:=1;
      FelsoHatar:=100;
      repeat
         Kozep:= (AlsoHatar+FelsoHatar) div 2;
         if x<a[Kozep] then FelsoHatar:=Kozep-1;
         if x>a[Kozep] then AlsoHatar:=Kozep+1;
      until (a[Kozep]=x) or AlsoHatar>FelsoHatar;
      van:=(a[Kozep]=x);
      if van then sorszam:=Kozep;
   end;

Alkalmazás
Gyakrabban találkozhatunk azonban olyan feladatokkal  a  gyakorlatban, ahol több programozási tétel együttes használatára van szükség.
Szerepel több olyan feladatsor, amelyben az adatok  azonosak, s velük kapcsolatban különböző kérdésekre  kell  választ adni.
Ezek jól használhatók önálló feladatmegoldásra.
Alkalmazás
A következő feladat megoldásánál a már  megismert  feladattípusok (összegzés, eldöntés, kiválasztás,  keresés,  megszámolás, maximumkiválasztás és kiválogatás) közül kell kiválasztani azokat, amelyekkel a kívánt eredmény elérhető.
Példa
Adott egy N elemű sorozat, valamint egy a sorozat  elemein értelmezett T tulajdonság.
Adjuk meg a sorozat minimális  értékű T tulajdonságú elemeit!
Adott N személyi számból álló sorozat [A(N)]. Adjuk meg az 1968-ban született legfiatalabb ember sorszámát  és  személyi számát!
Adjuk meg az összes ezen a napon született ember adatait is!
Alkalmazott tételek
Kiválogatás tétele: 1968-ban született emberek.
   B(I)= A(I) 2. és 3. számjegye.
Minimum-kiválasztás tétele: legkésőbbi  hónapban  és  napon született ember.
   C(I)= B(I) 4-7. számjegye.
Kiválogatás tétele: ugyanezen a napon született emberek.
Megoldás
Procedure szemelyiszam;
begin
      min:=1231;
      minsor:=0;
      for i=1-től n do
         if b[i]=68 then
                if c[i]<=min then
                begin
                    min:=c[i];
                    minsor:=i;
                end;
      if minsor>0 then
                for i=1 to n do
                if b[i]=68 and c[i]=min then writeln(a[i],’, ‘,i);
end;
Unió
Eddig olyan feladattípusokkal foglalkoztunk, ahol egy  sorozathoz egy értéket, vagy egy  sorozatot  rendeltünk  hozzá.
Ebben a részben viszont több sorozat adott, amelyből egy  sorozatot kell valamilyen szempont szerint előállítani.
A matematikából ismerjük két halmaz egyesítésének  (uniójának)  fogalmát.
Unió
A két halmaz egyesítéséből származó halmazba azok az  elemek tartoznak, amelyek legalább az egyikben szerepelnek.
Ebben, és a következő alfejezetben a  halmazt  speciálisan ábrázoljuk: az elemeit felsoroljuk egy sorozatban.
Ezt a sorrendet felhasználjuk a halmaz elemeinek bejárására.
Unió
Például, ha
      az "A" sorozat elemei: e, b, a, f, d, c és
      a  "B" sorozat elemei: j, f, b, h, d,
      akkor a két sorozat uniójába ("C") az  e, b, a, f, d, c, j, h
      elemek tartoznak.
Az unió általános algoritmusa
Eljárás:
      Ciklus I=1-től N-ig
         C(I):=A(I)
      Ciklus vége
      K:=N
      Ciklus J=1-től M-ig
         I:=1
         Ciklus, amíg I<=N és B(J)<>A(I)
            I:=I+1
         Ciklus vége
         Ha I>N akkor K:=K+1 : C(K):=B(J)
      Ciklus vége
   Eljárás vége.
Példa (egy 100 és egy 30 elemű sorozat uniója)
procedure unio;
begin     
   for i:=1 to 100 do c[i]:=a[i];
   k:=100;
   for j:=1 to 30 do
   begin
      i:=1;
      while (i<=100) and (b[j]<>a[i]) do i:=i+1;
      if i>n then
      begin
          k:=k+1;
         c[k]:=b[j];
       end;
    end;
end;
Metszet
A metszetképzés fogalmával találkoztunk már  a  matematika órán a halmazműveletek tanulása során.
Két halmaz metszetébe azok az  elemek  tartoznak,  amelyek mindkettőben szerepelnek.
   Például, ha
      az "A" halmaz elemei: e, b, a, f, d, c és
      a  "B" halmaz elemei: a, j, f, b, h, d,
      akkor a két halmaz metszetébe ("C") a  b, f, d  elemek tartoznak.
A metszet általános algoritmusa
Eljárás:
      K:=0
      Ciklus I=1-től N-ig
         J:=1
         Ciklus amíg J<=M és A(I)<>B(J)
            J:=J+1
         Ciklus vége
         Ha J<=M akkor K:=K+1 : C(K):=A(I)
      Ciklus vége
   Eljárás vége.
Példa (egy 100 és egy 30 elemű halmaz közös elemei)
Procedure metszet;
begin    
k:=0;
      for i:=1 to 100 do
      begin
         j:=1;
         while (j<=30) and (a[i]<>b[j]) do j:=j+1;
         if j<=30 then
         begin 
            k:=k+1;  c[k]:=a[i];
         end;
      end;
   end;
Összefuttatás
Az alapelve megegyezik az unióképzéssel, de feltételezzük, hogy a két sorozat rendezett,  és  azt  szeretnénk,  hogy  az egyesítés során keletkezett sorozat is rendezett legyen.
   Például, ha
      az A sorozat elemei: A, B, C, D, E, F és
      a B sorozat elemei:  B, D, F, H, J,
      akkor a két sorozat összefuttatásával keletkezett sorozatba az A, B, C, D, E, F, H, J elemek tartoznak.
Az összefuttatás általános algoritmusa
Eljárás:
      I:=1 : J:=1 : K:=0
      Ciklus amíg I<=N és J<=M
         K:=K+1
         Elágazás
            A(I)<B(J) esetén C(K):=A(I) : I:=I+1
            A(I)=B(J) esetén C(K):=A(I) : I:=I+1 : J:=J+1
            A(I)>B(J) esetén C(K):=B(J) : J:=J+1
         Elágazás vége
      Ciklus vége
   Eljárás vége.
Példa (egy 100 és egy 30 elemű rendezett sorozat összefuttatása)
Procedure osszefuttatas;
begin
      i:=1;j:=1;k:=0;
      while (i<=100) and (j<=m) do
      begin
         k:=k+1;
         if a[i]<b[j] then begin c[k]:=a[i]; i:=i+1; end else
         if a[i]=b[j] then begin c[k]:=a[i]; i:=i+1;j:=j+1; end
         else begin c[k]:=b[j];j:=j+1 end;
      end;
end;

Szétválogatás
Ebben a részben egy sorozat elemeit választjuk külön  vagy egy sorozaton belül két részre, vagy két különböző  sorozatba aszerint, hogy egy adott T tulajdonsággal  rendelkeznek-e  az elemek, vagy nem.
Például, ha az A sorozat elemei 1, 2, 3, 4, 5, 6, 7, 8, 9, és a T tulajdonság:  a  számok  párossága,  akkor  a  sorozat elemeinek szétválogatásával a 2, 4, 6, 8, és az 1, 3, 5, 7, 9 sorozatok keletkeznek.
A szétválogatás általános algoritmusa
Eljárás:
      J:=0 : K:=0
      Ciklus I=1-től N-ig
         Ha A(I) T tulajdonságú akkor  J:=J+1 : B(J):=A(I)  különben K:=K+1 : C(K):=A(I)
      Ciklus vége
   Eljárás vége.
Példa (100 szám szétválogatása paritás alapján)
Procedure szetvalogatas;
begin
      j:=0;k:=0;
      for i:=1 to 100 do
         if a[i] mod 2=0 then begin j:=j+1;b[j]:=a[i]; end
         else begin k:=k+1; c[k]:=a[i]; end;
      end;
end;

Rendezések
Közvetlen beszúrással
Közvetlen kiválasztással
Buborék-rendezés (közvetlen csere)
Keverő rendezés
megjegyzés: Ennél sokkal több rendezési algoritmus létezik!
Közvetlen beszúrás
Minden lépésben a második elemtől egyesével kiemeljük a csökkenő sorozat szerinti első elemet, és beszúrjuk a megfelelő helyre
Ábra
Algoritmus
Procedure kozvetlenbeszuras;
begin
   for i:=2 to n do
   begin
       elem:=a[i];
       j:=i-1;
       while (j>0) and (elem<a[j]) do
       begin
          a[j+1]:=a[j];
          j:=j-1;
       end;
       a[j+1]:=elem;
    end;
end;
Közvetlen kiválasztás
A sorozat soron következő legkisebb elemének kiválasztása, majd beszúrása a megfelelő helyre.
Ábra
Algoritmus
Procedure kozvetlenkivalasztas;
begin
   for i:=1 to n-1 do
   begin
      k:=i; elem:=a[i];
      for j:=i+1 to n do
          if a[j]<elem then
          begin
             k:=j; elem:=a[j];
          end;
      a[k]:=a[i]; a[i]:=elem;
   end;
end;
Közvetlen csere (buborék)
Az alkalmas elempárok összehasonlítása és felcserélése során jutunk az összes elem rendezéséhez.
Ábra
Algoritmus
Procedure buborek;
begin
   for i:=2 to n do
   begin
      for j:=n downto i do
         if a[j-1]>a[j] then
         begin
            elem:=a[j-1];
            a[j-1]:=a[j];
            a[j]:=elem;
         end;
   end;
end;
Keverő rendezés
Az előző módszer elég rossz hatásfokú, ha kevés rossz helyen tartózkodó elem van, mert akkor is elvégzi az összes összehasonlítást.
A keverő rendezés ezen úgy javít, hogy váltogatja az összehasonlító menetek irányát.
Ábra
Algoritmus / 1
Procedure kevero;
begin
   l:=2; r:=n; k:=n;
   repeat
      for j:=r downto l do
         if a[j-1]>a[j] then
         begin
             elem:=a[j-1];
             a[j-1]:=a[j];
             a[j]:=elem;
             k:=j;
         end;
      l:=k+1;
Algoritmus / 2
for j:=1 to r do
         if a[j-1]>a[j] then
         begin
             elem:=a[j-1];
             a[j-1]:=a[j];
             a[j]:=elem;
             k:=j;
         end;
       r:=k-1;
   until l>r ;
end;

Visszalépéses keresés (backtrack)
A visszalépéses keresés ( backtrack )  a  problémamegoldás igen széles területén alkalmazható algoritmus,  amelynek  lényege a feladat megoldásának megközelítése rendszeres próbálgatással.
Néha ez a legjobb megoldás!
Visszalépéses keresés (backtrack)
Adott N sorozat, amelyek rendre M(1),  M(2),...M(N)  elemszámúak.
Ki kell választani mindegyikből egy-egy elemet  úgy, hogy az egyes  sorozatokból  való  választások másokat  befolyásolnak.
Ez egy bonyolult keresési  feladat,  amelyben  egy adott tulajdonsággal rendelkező szám N-est kell megadni  úgy, hogy ne kelljen az összes lehetőséget végignézni.
Visszalépéses keresés (backtrack)
Először megpróbálunk az első sorozatból  kiválasztani  egy elemet, ezután a következőből, s ezt  addig  csináljuk,  amíg választás lehetséges.
X(I) jelölje az I. sorozatból kiválasztott elem sorszámát!
Ha még nem  választottuk, akkor értéke 0 lesz.
Ha nincs jó választás, akkor visszalépünk az előző  sorozathoz, s megpróbálunk abból egy másik  elemet  választani.
Visszalépéses keresés (backtrack)
Visszalépésnél természetesen törölni kell a választást  abból a sorozatból, amelyikből visszalépünk.
Az  eljárás  akkor  ér véget, ha minden sorozatból sikerült választani, vagy pedig a visszalépések sokasága után már az első sorozatból sem  lehet újabb elemet választani (ekkor a feladatnak nincs megoldása).
A backtrack általános algoritmusa
Eljárás:
      I:=1 : X(I):=0
      Ciklus amíg I>=1 és I<=N
         Ha VAN JO ESET(I) akkor  I:=I+1
                         különben X(I):=0 : I:=I-1
      Ciklus vége
      VAN:=(I>N)
   Eljárás vége.

  
A backtrack általános algoritmusa
VAN JO ESET(I):
      Ciklus
         X(I):=X(I)+1
      amíg X(I)<=M(I) és ROSSZ ESET( I,X(I) )
      Ciklus vége
      VAN JÓ ESET:=(X(I)<=M(I))
   Eljárás vége.
A backtrack általános algoritmusa
ROSSZ ESET( I,X(I) ):
      J:=1
      Ciklus amíg J<I és (J,X(J)) nem zárja ki (I,X(I))-t
         J:=J+1
      Ciklus vége
      ROSSZ ESET:=(J<I)
   Eljárás vége.








1 megjegyzés: