Programozási tételek

A programozási tételek egyszerű alap algoritmusok, azaz típusfeladatok minta megoldásai, melyek bizonyítottan jók és hatékonyak, így a „tétel” elnevezés jogos rájuk nézve.

Az alábbi tételekben minden esetben egy A tömb elemeiből indulunk ki, eredményül pedig egy értéket kapunk.

Adott egy N elemű A tömb. valamint egy T() tulajdonság (logikai függvény). Döntsük el, hogy van-e az A tömbnek T tulajdonságú eleme.

azaz N természetes szám az A tömb elemszáma, a tömb tehát N darab valós számot tartalmaz, a T tulajdonság pedig a valós számokhoz rendel igaz, vagy hamis értéket.

nincs

azaz a visszatérési érték akkor lesz igaz, ha találtunk az A tömbben T tulajdonságú elemet, pontosabban akkor, ha van olyan érvényes (1 és N közé eső) i index, melyre igaz, hogy az A tömb i-edik eleme T tulajdonságú.

  i := 1
  Ciklus amig (i <= N) és nem T(A(i))
    i := i + 1
  Ciklus vége
  Ki: (i <= N)

Magyarázat:

Az elemek vizsgálatát az első elemtől kezdjük (i := 1), és lépegetünk sorba az elemeken (i := i + 1), amíg el nem érjük a tömb végét (i ⇐ N), vagy nem találunk T tulajdonságú elemet (nem T(A(i))). A visszatérési érték akkor lesz igaz, ha nem értük el tömb végét (i ⇐ N).

• Ismerjük egy hét napjainak napi átlaghőmérsékleteit. Igaz-e, hogy folyamatosan emelkedett a hőmérséklet?
• Állapítsuk meg egy szövegről, hogy eszperente szöveg-e (eszperente szöveg az, amelyben csak e és é magánhangzók szerepelnek)
• Adott szövegről döntsük el, hogy több mondatból áll-e! (Mondathatár: mondatvégi írásjel, szóköz, majd nagybetű)
• Egy repülőgéprő Európából Amerikába repülve rendszeres időközönként mérték a tengerszint feletti magasságot (0 tengert, pozitív érték szárazföldet jelöl). Döntsük el, hogy az út során haladt-e el sziget felett a repülőgép!

Adott egy N elemű A tömb. valamint egy T() tulajdonság (logikai függvény). Tudjuk, hogy a tömbnek van T() tulajdonságú eleme. Adjunk meg egy T() tulajdonságú elemet, vagy annak indexét!

azaz N természetes szám az A tömb elemszáma, a tömb tehát N darab elemet tartalmaz, a T tulajdonság pedig az elemekhez rendel igaz, vagy hamis értéket.

Az A tömbnek van T() tulajdonságú eleme.

azaz a visszatérési érték az i index, vagy a tömb i-edik eleme, melyre A(i) T() tulajdonságú.

  i := 1
  Ciklus amig nem T(A(i))
    i := i + 1
  Ciklus vége
  Ki: i, A(i)

• Adjuk meg egy beolvasott 1-nél nagyobb pozitív egyész szám legkisebb 1-től különböző pozitív osztóját!
• Adjuk meg egy beolvasott 1-nél nagyobb pozitív egyész szám legnagyobb önmagától különböző pozitív osztóját!
• Határozzuk meg két szám legnagyobb közös osztóját!
• Határozzuk meg az N természetes számhoz legközelebbi négyzetszámot (N>1)!
• Határozzuk meg hány nap múlva lesz a legközelebbi vasárnap!

Adott egy N elemű A tömb. valamint egy T() tulajdonság (logikai függvény). Döntsük el, hogy van-e az A tömbnek T tulajdonságú eleme, ha van adjuk meg az elemet, vagy az elem tömbbeli indexét!

azaz N természetes szám az A tömb elemszáma, a tömb tehát N darab valós számot tartalmaz, a T tulajdonság pedig a valós számokhoz rendel igaz, vagy hamis értéket.

nincs

esetén , különben

azaz a visszatérési érték akkor lesz hamis, ha nem találtunk az A tömbben T tulajdonságú elemet, egyéb esetben a T tulajdonságú elem indexég és az elemet magát adjuk vissza.

  i := 1
  Ciklus amig (i <= N) és nem T(A(i))
    i := i + 1
  Ciklus vége
  Ha (i <= N) akkor
    Ki: i, A(i)
  különben
    Ki: hamis
  Elágazás vége

Magyarázat:

Az elemek vizsgálatát az első elemtől kezdjük (i := 1), és lépegetünk sorba az elemeken (i := i + 1), amíg el nem érjük a tömb végét (i ⇐ N), vagy nem találunk T tulajdonságú elemet (nem T(A(i))). Ha nem értük el tömb végét (i ⇐ N), akkor találtunk T tulajdonságú elemet, így ezt, illetve ennek indexét adjuk vissza, egyéb esetben hamis logikai értékkel tér vissza.

Adott egy N elemű A tömb. valamint egy T() tulajdonság (logikai függvény). Számoljuk meg, hogy hány T tulajdonságú eleme van az A tömbnek.

azaz N természetes szám az A tömb elemszáma, a tömb tehát N darab valós számot tartalmaz, a T tulajdonság pedig a valós számokhoz rendel igaz, vagy hamis értéket.

nincs

azaz a Db változó az A tömb T tulajdonságú elemeinek számával egyenlő

  Db := 0
  Ciklus i := 1-től N-ig
    Ha T(A(i)) akkor Db := Db + 1
  Ciklus vége
  Ki: Db

Adott egy N elemű, számokat tartalmazó A tömb. Határozzuk meg az A tömb elemeinek összegét!

nincs

  S := 0
  Ciklus i := 1-től N-ig
    S := S + A(i)
  Ciklus vége
  Ki: S

Magyarázat: S-ben tároljuk az eddig sorra vett elemek összegét, i mutatja, hogy hányadik elemnél tartunk a feldolgozás közben.

Első lépésként - mivel még egy elemet sem vizsgáltunk meg - az S kezdőértékét 0-ra állítjuk. Ezután végig megyünk az összes elemen (ezért számlálásos ciklust használunk) és S értékét minden lépésben az A tömb soron következő elemével növeljük.

Az algoritmus gondolatmenete minden olyan esetben alkalmazható, ahol a sorozathoz rendelt érték megadható az eggyel rövidebb sorozat és az utolsó tag segítségével (rekurzív módon):

Ilyen a szumma függvény az összeadás művelettel párban, a produktum függvény a szorzás művelettel, de ilyen a számok átlaga, mértani közepe, szövegek egymásután fűzése és még sok egyéb függvény is.

• Olvassunk be egy n pozitív egész számot, majd számítsuk ki az n! értéket!
• Egy napon minden órában megmértük a hőmérsékletet. Számítsuk ki ezen adatok alapján a napi átlaghőmérsékletet!
• Adott szavakat fűzzünk össze közéjük szóközöket helyezve!

Adott egy N elemű A tömb. Válasszuk ki a tömb legnagyobb elemét.

  MaxIndex := 1
  Ciklus i := 2-től N-ig
    Ha A(i) > A(MaxIndex) akkor MaxIndex := i
  Ciklus vége
  Ki: MaxIndex, A(MaxIndex)

Adott egy N elemű, rendezett A sorozat. Keressük meg benne az X értéket!

  E := 1
  V := N
  Ciklus
    K := int((E+V) / 2)
    Ha A(K) > X akkor V := K - 1
    Ha A(K) < X akkor E := K + 1
  Amíg A(K) <> X és E <= N
  Ha E > N akkor Ki: nincs
  különben Ki: K

Adott egy N elemű A tömb. Rendezzük a tömb elemeit emelkedő sorrendbe!

  Ciklus i := 1-től N-1-ig

    // minimumkiválasztás
    minIndex := i
    Ciklus j := i+1-től N-ig
      Ha A(minIndex) > A(j) akkor
        minIndex := j;
      Elágazás vége
    Ciklus vége

    // csere
    Segéd := A(i)
    A(i) := A(minIndex)
    A(minIndex) := Segéd
    
  Ciklus vége

Adott egy N elemű A tömb és egy T tulajdonság. Válogassuk ki egy B tömbbe az A vektor T tulajdonságú elemeit.

  Db := 0
  Ciklus i := 1-től N-ig
    Ha T(A(i) akkor
      Db := Db + 1
      B(Db) := A(i)
    Elágazás vége
  Ciklus vége

Adott egy N elemű A tömb és egy T tulajdonság. Válogassuk ki az A vektor T tulajdonságú elemeit egy B, nem T tulajdonságú elemeit egy C tömbbe.

  Db := 0
  Ciklus i := 1-től N-ig
    Ha T(A(i) akkor
      Db := Db + 1
      B(Db) := A(i)
    különben
      C(i-Db) := A(i)
    Elágazás vége
  Ciklus vége

• Pascal megvalósítás
• C# megvalósítás