====== 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.


===== Sorozathoz érték rendelése =====

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

==== Eldöntés tétel ====

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.

=== Állapot tér===
<m>N in bbN, A = bbR^{N}, T: bbR right delim{lbrace}{igaz, hamis}{rbrace}</m>

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.

=== Előfeltétel ===
nincs

=== Utófeltétel ===
<m>Ki: (exists i in bbN, 1<=i<=N: T(A(i)))</m>

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ú.

=== Algoritmus ===

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

**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).

=== Feladatok ===

  * 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!



==== Kiválasztás tétel ====

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!

=== Állapot tér===
<m>N in bbN, A = bbR^{N}, T: bbR right delim{lbrace}{igaz, hamis}{rbrace}</m>

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.

=== Előfeltétel ===

<m>exists i in bbN, 1<=i<=N: T(A(i))</m>

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

=== Utófeltétel ===

<m>Ki: i, A(i) (i in bbN, 1<=i<=N: T(A(i)))</m>

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

=== Algoritmus ===

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

=== Feladatok ===

  * 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!

==== Keresés tétel ====

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!

=== Állapot tér===
<m>N in bbN, A = bbR^{N}, T: bbR right delim{lbrace}{igaz, hamis}{rbrace}</m>

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.

=== Előfeltétel ===
nincs

=== Utófeltétel ===
<m>Ki: (exists i in bbN, 1<=i<=N: T(A(i)))</m> esetén <m>delim{lbrace}{i; A(i)}{rbrace}</m>, különben <m>hamis</m>

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.

=== Algoritmus ===

<code>
  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
</code>

**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.

=== Feladatok ===


==== Megszámolás tétel ====

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.

=== Állapot tér===
<m>N in bbN, A = bbR^{N}, T: bbR right delim{lbrace}{igaz, hamis}{rbrace}, Db in bbN</m>

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.

=== Előfeltétel ===
nincs

=== Utófeltétel ===
<m>Db = |delim{lbrace}{i in bbN | T(A(i))}{rbrace}|</m>

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

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

==== Összegzés (sorozatszámítás) tétel ====

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

=== Állapottér ===

<m>N in bbN, A = bbR^{N}</m>

=== Előfeltétel ===

nincs

=== Utófeltétel ===

<m>S = sum{i=1}{N}{A(i)}</m>

=== Algoritmus ===

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

**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):

<m>f(a_1,a_2,...,a_n) = f(a_1,a_2,...a_{n-1}) circ a_n</m>

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.

=== Feladatok ===

  * 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!




==== Maximumkiválasztás ====

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

=== Algoritmus ===

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


==== Logaritmikus keresés ====

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

=== Algoritmus ===

<code>
  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
</code>

===== Sorozathoz sorozat rendelése =====

==== Rendezés ====


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

=== Minimumkiválasztásos rendezés ===

<code>
  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
</code>

==== Kiválogatás ====

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.

=== Algoritmus ===

<code>
  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
</code>

==== Szétválogatás - két tömbbe ====

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.

=== Algoritmus ===

<code>
  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
</code>

===== Példák =====
  * [[informatika:programozas:pascal:tetelek|Pascal megvalósítás]]
  * [[informatika:programozas:dotnet:c-sharp:tetelek|C# megvalósítás]]