6 - Elemi programozási tételek

Sorozatszámítás

Minden olyan művelet szerepelhet ebben a feladattípusban, amelyre a matematika valamilyen „egységes” jelölést használ: összeg, szorzat, unió, metszet, logikai műveletek, konkatenáció stb.

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

Végigolvassuk az összes számot és összeadjuk őket egy Szum nevű változóba. Vigyázni kell, hogy az összegzés megkezdése előtt az Szum-nak az értéke 0 legyen, hiszen nem tudhatjuk, hogy később adunk-e hozzá valamit.

Algoritmus

Összegzés (N, A, Szum):
  Szum := 0
  Ciklus i := 1-től N-ig
    Szum := Szum + A[i]
  Ciklus vége
Eljárás vége.

Struktogram

C# megoldás

// Létezik egy N elemű A tömb

int szum = 0;
for (int i = 0; i < A.Length; i++) {
  szum += A[i];
}

Eldöntés

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!

Vesszük sorban az elemeket (ezért nő i mindig eggyel), és ezt addig csináljuk, amíg nem találunk megfelelő tulajdonságú elemet vagy már nincs több elem (éppen ez van leírva a ciklusfeltételben)

Algoritmus

Eldöntés (N, A, Van):
  i := 1
  Ciklus amíg (i <= N) és nem T(A(i))
    i := i + 1
  Ciklus vége
  Van := (i <= N)
Eljárás vége.

Struktogram

C# megoldás

// Létezik egy N elemű A tömb

int i = 0;
while (i < A.Length && !T(A[i])) { // !T(A[i]) lehet például !(A[i] == 4), vagy bármi
  i++;
}
bool van = i < A.Length;

Megszámlálás

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!

Végigolvassuk az összes elemet. Amikor találunk olyat, ami megfelel a feltételünknek, akkor növeljük eggyel a db számlálónkat.

Algoritmus

Megszámolás (N, A, Db):
    Db := 0
  Ciklus i = 1-től N-ig
    Ha T(X[i])
      akkor Db := Db + 1
  Ciklus vége
Eljárás vége.

Struktogram

C# megoldás

// Létezik egy N elemű A tömb

int db = 0;
for (int i = 0; i < A.Length; i++) {
  if (T(X[i])) { // T(A[i]) lehet például (A[i] == 4), vagy bármi
    db++;
  }
}

Kiválasztás

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!

Mivel biztosan van legalább egy T() tulajdonságú elem, ezért nincs szükség arra, hogy megvizsgáljuk van-e még elem. Ha megtaláltuk a T() tulajdonságú elemet, akkor a ciklus megáll, és már csak az index értékét kell lekérdeznünk.

Algoritmus

Kiválasztás(N,A,Sorsz):
  i := 1
  Ciklus amíg nem T(A[i])
    i := i+1
  Ciklus vége
  Sorsz := i
Eljárás vége.

Struktogram

C# megoldás

// Létezik egy N elemű A tömb

int i = 0;
while (T(A[i])) { // T(A[i]) lehet például (A[i] == 4), vagy bármi
  i++;
}
int sorsz = i;

Keresés

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!

Az elemek vizsgálatát az első elemtől kezdjük, és lépegetünk sorban az elemeken, amíg el nem érjük a tömb végét, vagy nem találunk T() tulajdonságú elemet. Ha nem értük el tömb végét , 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.

Algoritmus

Keresés(N,A,Van,Sorsz):
  i := 1
  Ciklus amíg i<=N és nem T(A[I])
    i := i + 1
  Ciklus vége
  Van := (i <= N)
  Ha Van
    akkor Sorsz := i
Eljárás vége.

Struktogram

C# megoldás

int i = 0;
while (i < A.Length && !T(A[i])) { // !T(A[i]) lehet például !(A[i] == 4), vagy bármi
  i++;
}
bool van = i <= A.Length;
int sorsz;
if (van) {
  sorsz = i;
}

Szélsőérték-kiválasztás

Maximum és minimum érték kiválasztási művelet szerepelhet benne.

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

Vesszük a sorozat első elemét. Ezek után ehhez az elemhez hasonlítjuk a többi elemet. Ha azonban találunk ettől az elemtől nagyobb számot, akkor innentől kezdve már a megtalált nagyobb számhoz hasonlítjuk a többi elemet. Vagyis amikor találtunk az eddig megvizsgáltak közül kiválasztott legnagyobbtól nagyobbat, akkor ennek az indexét azonnal berakjuk a Max-ba, és innentől kezdve ez a legnagyobb.

Minimum esetén annyi a változás, hogy az előző algoritmusban az elágazás feltételében a relációjel megfordul, hiszen most a legkisebb elemet keressük.

Maximum esetén mindig a lehető legkisebb értéket adjuk meg a kezdő értéknek, minimumnál pedig a lehető legnagyobbat

Algoritmus

Maximumkiválasztás(N,A,Max):
  Max := 1
  Ciklus i=2-től N-ig
    Ha A[Max] < A[i]
      akkor Max := i
  Ciklus vége
Eljárás vége.

Struktogram

C# megoldás

int maxIndex = 0; // A lehető legkisebb érték
for (int i = 0; i < A.Length) {
  if (A[maxIndex] < A[i]) [
    maxIndex = i;
  ]
}