Feladatok

Egyszerű feladatok:

1. Tetszőleges egész szám abszolútértéke:

A=|A|

 

DEKLARÁCIÓK
A: Egész
ALGORITMUS KEZD
  BE: A
  HA A<0 AKKOR
    KI:=-A
  KÜLÖNBEN
  KI: A
ALGORITMUS VÉGE.

2. Tetszőleges egyismeretlenes egyenlet megoldása:

AX+B=0

 

DEKLARÁCIÓK
A,B,X: Valós
KEZD
  BE: A,B
  HA A=0 AKKOR
    KI: ’Hibás bemenő A’
  KÜLÖNBEN
    KI: ’X=’,-B/A
VÉGE.

3. Két elem cseréje:

DEKLARÁCIÓK:
A,B,C: Típus
KEZD
  BE: A,B
  C:=A
  A:=B
  B:=C
VÉGE.

4. Két szám legnagyobb közös osztója:

A nagyobbik számot csökkenteni kell a kisebbikkel, és a kapott értékre át kell írni. Ezt addig kell folytatni, amíg egyenlő számot nem kapunk. Ez az érték a két szám legnagyobb közös osztója.

Pl.
27/21
27        21
6          21
6          15
6          9
6          3
3          3
DEKLARÁCIÓK
  A,B: Egész
KEZD
  BE: A,B
  HA (A<=0) OR (B<=0) AKKOR
    KI: ’Hibás bemenő adatok!’
  KÜLÖNBEN
    CIKLUS amíg A<>B
      HA A>B AKKOR
        A:=A-B
      KÜLÖNBEN
        B:=B-A
    CVÉGE
    KI: ’A közös nevezőjük:’, A
  HAVÉGE
VÉGE.

Alapvető algoritmusok:

1. Egydimenziós tömb elemeinek feltöltése:

Tomb[1..N]

CILUS I:=1-től N-ig
  BE: Tomb[I]
CVÉGE

2. Egydimenziós tömb kiírása:

Tomb[1..N]

CILUS I:=1-től N-ig
  KI: Tomb[I]
CVÉGE

3. Kétdimenziós tömb feltöltése:

Tomb[1..N, 1..M]

CILUS I:=1-től N-ig
  CILUS I:=1-től M-ig
    BE: Tomb[I,J]
  CVÉGE
CVÉGE

 

4. Kétdimenziós tömb kiírása:

Tomb[1..N, 1..M]

CILUS I:=1-től N-ig
  CILUS I:=1-től M-ig
    KI: Tomb[I,J]
  CVÉGE
CVÉGE

Egy sorozathoz egy elem hozzárendelése:

1. Összegképzés tétele:

Tomb[1..N, 1..M]

S:=0
CILUS I:=1-től N-ig
  CILUS I:=1-től M-ig
    S:=S+Tomb[I,J]
  CVÉGE
CVÉGE

2. Szorzatképzés tétele:

Tomb[1..N, 1..M]

S:=1
CILUS I:=1-től N-ig
  CILUS I:=1-től M-ig
    S:=S*Tomb[I,J]
  CVÉGE
CVÉGE

3. Eldöntés tétele:

Szerepel-e a tömb elemei között valamilyen tulajdonságú elem. Ha igen, melyik az?
Az első előfordulást figyeli.
Ha az utolsót akarjuk, akkor vagy visszafelé haladjunk, vagy a ciklusfeltételnek ne adjuk meg a NOT Jóelem-et!

 

 

 

I:=0
CILUS amíg (I<=N) AND NOT Jóelem(Tomb[I])
  I:=I+1
CVÉGE
HA Jóelem(Tomb[I]) AKKOR
  KI: ’Van ilyen elem!’
  KI :I,’ az elem sorszáma.’
KÜLÖNBEN
  KI: ’Nincs ilyen elem!’
  KI: Az I,’:=N+1’

4. Kiválasztás tétele:

Biztosan tartalmazza az elemet, de nem tudjuk, hogy melyik az.

I:=1
CIKLUS amíg NOT Jóelem(Tomb[I])
  I:=I+1
CVÉGE
KI: ’Az elem sorszáma:’,I,’.’

5. Maximum kiválasztás tétele:

A legnagyobb elem kiválasztása.

MAX:=1
CIKLUS I:=2-től N-ig
  HA T[I]>T[MAX] AKKOR MAX:=I
CVÉGE
KI: T[MAX]

6. Minimum kiválasztás tétele:

A legkisebb elem kiválasztása.

MIN:=1
CIKLUS I:=2-től N-ig
  HA T[I]<T[MIN] AKKOR MIN:=I
CVÉGE
KI: T[MIN]

7. Megszámlálás tétele:

Adott tulajdonságú elemek kiírása.

 

S:=0
CIKLUS amíg I<=N
  HA Jóelem(Tomb[I]) AKKOR S:=S+1
CVÉGE
KI: S,’ db jó elem van!’

Egy sorozathoz egy sorozat hozzárendelése:

1. Maximum kiválasztásos rendezés:

A tömb rendezése a legnagyobb elem segítségével.
Az utolsó elem a legnagyobb, a legnagyobb elem helyére kerül az utolsó elem. Az utolsó előtti elem lesz a 2. legnagyobb, a 2. legnagyobb helyére kerül az utolsó előtti elem stb.

CIKLUS I:=N-től 2-ig (-1-esével)
  MAX:=I
  CIKLUS J:=I-1-től 1-ig (-1-esével)
    HA A[J]>A[MAX] AKKOR
    MAX:=J
  CVÉGE
  C:=A[I]
  A[I]:=A[MAX]
  A[MAX]:=C
CVÉGE

2. Buborékrendezés I.:

Mindig szomszédos elemeket vizsgál.
Lassú, mert ahol már rendezve van, ott is ellenőrzi.

CIKLUS I:=N-től 1-ig (-1-esével)
  CIKLUS J:=1-től I-ig
    Ha A[J]>A[J+1] AKKOR
      C:=A[J]
      A[J]:=A[J+1]
      A[J+1]:=C
    HAVÉGE
  CVÉGE
CVÉGE

3. Buborékrendezés II.:

Mindig szomszédos elemeket vizsgál.
Ha az adott belső ciklusban nem volt csere, akkor a főciklust, azaz az algoritmust befejezi.

 

I:=N-1
VEGE:=Hamis
CIKLUS amíg I>=1 (vagyis I>0) AND NOT VEGE
  VEGE:=Igaz
  CIKLUS J:=1-től I-ig
    HA A[J]>A[J+1] AKKOR
      C:=A[J]
      A[J]:= A[J+1]
      A[J+1]:=C
      VEGE:=Hamis
    HAVÉGE
  CVÉGE
  I:=I-1
CVÉGE

4. Buborékrendezés III.:

Mindig szomszédos elemeket vizsgál.
Az utolsó cseréig vizsgál, ahol már nem volt csere, ott nem vizsgál.

I:=N-1
CIKLUS amíg I>0 (vagyis az UTOLSOCSERE>0)
  UTOLSOCSERE:=0
  CIKLUS J:=1-től I-ig
    HA A[J]>A[J+1] AKKOR
      C:=A[J]
      A[J]:=A[J+1]
      A[J+1]:=C
      UTOLSOCSERE:=J
    HAVÉGE
  CVÉGE
  I:=UTOLSOCSERE
CVÉGE

5. Póker rendezés:

A számokat közvetlenül egymás mellé helyezi – ahogyan az ember a kártyáit rendezi.

CIKLUS I:=2-től N-ig
  J:=I-1
  X:=A[I]
  CIKLUS amíg (J>=1) AND (X<A[J])
    A[J+1]:=A[J]
    J:=J-1
  CVÉGE
  A[J+1]:=X
CVÉGE

6. Listás-beillesztéses rendezés:

Feltétele, hogy MU tömb 0-kat tartalmazzon. Csökkenő sorrendben rendez (lehet fordítva is).
MU 0-tól N-ig tartalmaz számokat, a Tomb tömb indexeit (elemeinek sorszámát). A Tomb tömb rendezettsége nem változik, a MU-ban változik a Tomb tömb indexeinek sorrendje. Az ME az aktuálisat, az MK a következő tömbelemet mutatja. Az új elem mindig az ME és az MK közé szúródik be. Keresi, hogy hol van az első új elem, amelyik a kettő között áll.
Előnye: A tömbnek csak az indexeit rendezi, így nagyobb adatbázisoknál nem kell a rekordokat cserélni, ami nagyon lassítja a folyamatot.

Tomb[1..N] – a rendezettsége nem változik
MU[0..N] – segédtömb, a Tomb tömb indexeit tartalmazza

MU[0]:=1
CIKLUS I:=2-től N-ig
  MK:=MU[0]
  ME:=0
  A:=Tomb[I]
  CIKLUS amíg (MK>0) AND (A<Tomb[MK])
    ME:=MK
    MK:=MU[ME]
  CVÉGE
  MU[ME]:=I
  MU[I]:=MK
CVÉGE
CIKLUS I:=1-től N-ig
  KI: Tomb[MU[I-1]]
CVÉGE

Több sorozathoz egy sorozat hozzárendelése:

1. Metszetképzés:

A és B halmaz (tömb) közös része.
Az A és a B tömbben nem lehet ismétlődő elem. Ha már volt a B-ben az elem, akkor ne keressen. Ha 2 vagy több azonos elem van az A-ban és a B-ben, akkor a C-ben is 2 vagy több azonos elem van.

A[1..N]
                                   C[1..min(N,M)](maximum)
B[1..M]

 

 

 

CDB:=0
CIKLUS I:=1-től N-ig
  CIKLUS J:=1-től M-ig
    HA A[I]=B[J] AKKOR
      CDB:=CDB+1
      C[CDB]:=A[I]
    HAVÉGE
  CVÉGE
CVÉGE

2. Unióképzés:

A és B halmaz (tömb) összege.
Azonos elemek csak egyszer kerülnek be a C halmazba.

A[1..N]
                                   C[1..N+M](maximum)
B[1..M]

CIKLUS I:=1-től N-ig
  C[I]:=A[I]
CVÉGE
CDB:=N
--- Innentől különbségképzés:
CIKLUS J:=1-től M-ig
  TALALAT:=Hamis
  CIKLUS I:=1-től N-ig
    HA B[J]=A[I] AKKOR
      TALALAT:=Igaz
    HAVÉGE
  CVÉGE
  HA NOT TALALAT AKKOR
    CDB:=CDB+1
    C[CDB]:=B[J]
  HAVÉGE
CVÉGE

3. Különbségképzés:

A-B halmaz (tömb).

A[1..N]
                                   C[1..N](maximum) – mivel A-B
B[1..M]

 

 

CDB:=0
CIKLUS I:=1-től N-ig
  TALALAT:=Hamis
  CIKLUS J:=1-től M-ig
    HA A[I]=B[J] AKKOR
      TALALAT:=Igaz
    HAVÉGE
  CVÉGE
--- Eddig eldöntés tétele.
  HA NOT TALALAT AKKOR
    CDB:=CDB+1
    C[CDB]:= A[I]
  HAVÉGE
CVÉGE

4. Összefuttatás tétele I.:

Minden elemet át kell tenni növekvő sorrendben (feltétel: az A és a B tömb rendezett legyen).

A[1..N]
                                   C[1..N+M](mindig)
B[1..M]

CDB:=0
I:=1
J:=1
CIKLUS amíg (I<=N) AND (J<=M)
  CDB:=CDB+1
  ELÁGAZÁS
    HA A[I]<B[J] AKKOR
      C[CDB]:=A[I]
      I:=I+1
    HA A[I]>B[J] AKKOR
      C[CDB]:=B[J]
      J:=J+1
    KÜLÖNBEN (vagyis A[I]=B[J])
      C[CDB]:=A[I]
      I:=I+1
      CDB:=CDB+1
      C[CDB]:=B[J]
      J:=J+1
    ELÁGAZÁS VÉGE
CVÉGE
CIKLUS amíg I<=N (Ha az A tömbben vannak még elemek)
  CDB:=CDB+1
  C[CDB]:=A[I]
  I:=I+1
CVÉGE
CIKLUS amíg J<=M (Ha a B tömbben vannak még elemek)
  CDB:=CDB+1
  C[CDB]:=B[I]
  J:=J+1
CVÉGE

5. Összefuttatás tétele II.:

Minden elemet át kell tenni növekvő sorrendben (feltétel, hogy az A és a B tömb rendezett legyen). Beírja a +”végtelent” (mert a +végtelen nem lehet kisebb a másik tömb egyik eleménél sem – a ciklus azon a ponton marad), így nem kell a maradékokat bemásolnia. De az N+1-dik elem legyen „végtelen”.

A[1..N+1]
                                   C[1..N+M+1](mindig)
B[1..M+1]

A[N+1]:=65535 (Mivel a számítástechnikában nincs végtelen, minél nagyobb számot válasszunk)
B[M+1]:=65535
CDB:=0
I:=1
J:=1
CIKLUS amíg (I<=N+1) VAGY (J<=M+1)
  HA A[I]<=B[J] AKKOR
    CDB:=CDB+1
    C[CDB]:=A[I]
    I:=I+1
  HAVÉGE
  HA A[I]>=B[J] AKKOR
    CDB:=CDB+1
    C[CDB]:=B[J]
    J:=J+1
  HAVÉGE
CVÉGE

Adatszerkezetek:

1. Egyszerű:
- egy változó egy érték (szám, logikai, szöveg).

2. Összetett:
- tömb,
- halmaz,
- verem,
- sor,
- láncolt lista.

1. Verem (stack):

N elem tárolására képes.
Last In First Out adatszerkezet (amit utolsónak be, azt elsőnek ki)

Üres: Empty

Tele: Full
Inicializálás: Init
Berak: Push
Kiszed: Pop

VM: egész – veremmutató (az elemek számát mutatja)

1. Verem üres, ha VM=0

2. Verem teli, ha VM=N

3. Verem üresre állítása (inicializálása): VM:=0

4. Elem elhelyezése a verembe:
HA VM<>N AKKOR (vagyis VM<N)
  VM:=VM+1
  Tomb[VM]:=Elem
KÜLÖNBEN
  HIBA! (Fel kell dolgozni!)

5. Elem kiszedése a veremből:
HA VM<>0 AKKOR (vagyis VM>0)
  Elem:=Tomb[VM]
  VM:=VM-1
KÜLÖNBEN
  HIBA! (Fel kell dolgozni!)

A verem létrehozása után üresre kell állítani (inicializálni kell) a vermet! A verem egy butított tömb.

Pl. Egy numerikus kifejezésnél ellenőrizni kell, hogy jól van-e zárójelezve. (12*(14-(-12)+8)-4)
(Elég egy változó értékét növelni és csökkenteni, nem kell verem.)
Menet közben betelhet a verem. Az elején meg kell adni, hogy hány nyitó (vagy záró) zárójelet tartalmazhat.

CIKLUS a végéig
  HA ’(’ AKKOR
    Elem elhelyezése a verembe
  HAVÉGE
  HA ’)’ AKKOR
    Elem kiszedése a veremből – Hiba esetén több záró zárójel van, mint nyitó!
  HAVÉGE
CVÉGE
HA VM=0 AKKOR
  Jó!
KÜLÖNBEN
  Több nyitó zárójel van, mint záró zárójel!

Eljárás- és függvényhívások esetén a proci használ verem adatszerkezetet.

2. Sor (queue):

N elem tárolására képes.
First In First Out adatszerkezet (amit elsőnek be, azt elsőnek ki)

1. Egyszerű sorok:
a) Egyszer használatos sor,
b) léptetős (többször használatos) sor.
2. Ciklikus sorok.

1/a. Egyszer használatos sor:

Ha végig beraktuk, azután kiszedtük, akkor már nem tudjuk használni.
Két változó van: első és utolsó.

Init:
ELSO:=1
UTOLSO:=0

Üres:
ELSO>UTOLSO

Tele:
UTOLSO=N

Betesz:
HA UTOLSO<>N AKKOR
  UTOLSO:=UTOLSO+1
  Sor[UTOLSO]:=Elem
KÜLÖNBEN
  HIBA!

Kivesz:
HA ELSO<=UTOLSO AKKOR
  Elem:=Sor[ELSO]
  ELSO:=ELSO+1
KÜLÖNBEN
  HIBA!

 

1/b. Léptetős sor:

A sor elemeit visszahúzza (balra lépteti). Hasonlít az egyszer használatoshoz, csak a kiszedés módosul.

Kivesz:
HA ELSO<=UTOLSO AKKOR
  Elem:=Sor[ELSO]
  CIKLUS I:=2-től UTOLSO-ig
      Sor[I-1]:=SOR[I]
    CVÉGE
KÜLÖNBEN
  HIBA!

2. Ciklikus sor:

Felhasználja a már kiolvasott elemek helyeit, ha már feltöltődött a sor. Amikor összeér a 2 változó, akkor inicializál.

Init:
ELSO:=1
UTOLSO:=0

Üres:
UTOLSO=0

Teli:
ELSO=1 AND UTOLSO=N
(Mert mindig úgy teszünk bele elemet, hogy az utolsót növeljük először.)
VAGY
UTOLSO>0 AND UTOLSO= ELSO-1

Betesz:
HA NOT ((ELSO=1 AND UTOLSO=N) OR (UTOLSO>0 AND UTOLSO= ELSO-1)) AKKOR
  HA UTOLSO<N AKKOR
  UTOLSO:=UTOLSO+1
  KÜLÖNBEN (vagyis UTOLSO=N)
    UTOLSO:=1 (Átfordul a sor első indexére)
  HAVÉGE
  Sor[UTOLSO]:=Elem
KÜLÖNBEN
  HIBA!

 Kivesz:
HA UTOLSO<>0 AKKOR
  Elem:=Sor[Elem]
  HA ELSO=UTOLSO AKKOR
    Init
  KÜLÖNBEN
    HA ELSO<N AKKOR
      ELSO:=ELSO+1
    KÜLÖNBEN (vagyis ELSO=N)
      ELSO:=1
    HAVÉGE
  HAVÉGE
KÜLÖNBEN
  HIBA!
HAVÉGE