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.