[itk] Számítástechnika kezdőknek

C++ programozás kezdőknek - programozási tételek

[2022. április 08.] [ christo161 ]

A programozási tételek olyan algoritmusminták, amiket tipikus alapvető, gyakran előforduló feladatok megoldásához használunk.

Tartalom

  • megszámlálás
  • összegzés
  • sorozatszámítás
  • maximumkiválasztás
  • eldöntés
  • kiválasztás
  • lineáris keresés
  • logaritmikus keresés
  • másolás
  • kiválogatás
  • szétválogatás
  • összefésülés
  • összefuttatás
  • metszet
  • unió
  • maximumkeresés kiválogatással
  • összetett kiválogatás

Alapvető tudnivalók

Pontosan miket sorolunk a programozási tételek közé?

Erről jókat lehetne vitatkozni, szerintem erről nincs egyértelmű közös megegyezés.

Jellemzően: megszámlálás (count), összegzés (sum), maximumkiválasztás (max) vagy minimumkiválasztás (min), esetleg szokták őket együttesen szélsőértékkiválasztásnak is nevezni, eldöntés (contains), kiválasztás (find), lineáris keresés (linear search), logaritmikus keresés (logarithmic search) vagy más néven bináris keresés.
Esetleg ezek között szokott még szerepelni sorozatszámítás egyes tananyagokban. Például:

Egyes tananyagok csak az eddigieket sorolják a programozási tételek közé, míg más tananyagok a következőket is: kiválogatás (filter), szétválogatás (split), összefésülés, összefuttatás (merge).
Talán ezek között találkozhatunk olyannal is, hogy másolás.

Esetleg ilyesmikkel is találkozhatunk: metszet, unió (nem rendezett adatszerkezetek esetén).
Továbbá egyes tananyagokban rendezésekkel is találkozhatunk a programozási tételek között (például itt).

Van-e arról közös megegyezés, hogy pontosan hogyan valósítsuk meg (a kódban) a programozási tételeket?

Nincs. Sok tananyagban folyamatábrákkal vagy struktogramokkal, esetleg mondatszerű leírásokkal adják meg a programozási tételeket, ahol nincs tisztázva a konkrét megvalósítás a kódban.

  • Például nincs pontosan megadva, hogy a bemenet, input honnan származik. Pl. fájlból, adatbázisból, a program egy függvényéből (pl. random generált számok), vagy a felhasználótól kérdezzük be.
    Ebben a tananyagban a legtöbb esetben a legegyszerűbb módszert választjuk, literálként előre megadunk egy tömbszerű adatszerkezetben néhány példaértéket, így az eredmény talán valamivel könnyebben ellenőrízhető, mint random generált adatok esetén.
  • Például nincs pontosan megadva, hogy egy adatszerkezet (pl. egy tömbszerű adatszerkezet esetén) hogyan megyünk végig az elemeken (for ciklus, ranged for ciklus, foreach függvény és iterátorok).
  • Például lineáris keresés vagy maximumkiválasztás esetén nincs pontosan megadva, hogy csak az adott elem értékére van-e szükségünk, vagy a helyére (indexére), esetleg azonosítójára (id-jára) osztály/objektum esetén. Illetve hogy jelezni kell-e azt, ha több azonos érték van, esetleg kigyűjteni az azonos értékek indexét, id-ját.
  • Például kiválogatás esetén mondjuk legyen az a feladat, hogy egy egész számokat tartalmazó tömbből válogassuk ki a páros számokat, vagy egy stringeket tartalmazó tömbből válogassuk ki az 5 karakternél több karaktert tartalmazó stringeket.
    Ezt többféleképp megtehetjük. Például létrehozunk egy másik tömböt a kiválogatott elemeknek, vagy például az eredeti tömbből eltávolítjuk a feltételnek nem megfelelő elemeket, vagy például kiíratjuk a kiválogatott elemeket. Erre mondjuk egy ELTE-s tananyagban vannak különböző változatok.
  • Érdemes szót ejteni arról is, hogy sok programozási tételt érdemes lehet típusparaméterezéssel template függvényként megvalósítani, így nem kell megírni az egyes típusokra vonatkozó változatokat külön-külön.
  • C++ adottság, hogy többféle tömbszerű adatszerkezet van, hagyományos tömb, dinamikusan allokált tömb, std::array és std::vector. Természetesen a programozási tételek azt sem szabják meg, hogy ezek közül melyiket használjuk. Illetve ha függvényekben írjuk meg a programozási tételeket akkor írhatunk akár több függvényt, hogy pl. hagyományos tömböket és std::vectorokat is fel tudjunk dolgozni.

Honnan származik a programozási tételek elnevezés?

Az elnevezés (programozási tétel) innen származik:
Dijksta, E.W.: A discipline of programming, Prentice Hall, Englewood Cliffs, New Jersey, 1976.

/Zsakó László/

A programozási tételek fogalmát az ELTE-n Fóti Ákos vezette be a 80-as elején. Ezt a fogalmat vettük át (Zsakó László és én) és némileg kibővítettük, ill. kissé más formalizmust rendeltünk hozzá. Ekként publikáltuk, ill. oktattuk a 80-as évek második felétől. A szakmai irodalom érdekes módon nem nagyon alkalmazza a fogalmat. A tételhez viszont tartozik egy feladatspecifikáció is és a kettejük összetartozásának bizonyítása. Vagyis a "programozási tétel" fogalom teljesebb, absztraktabb fogalom, mint az "alapalgoritmusok" fogalom.

/Szlávi Péter/

Akit mélyebben érdekel a téma ezeket a pdf-eket ajánlom számára (talán nyomtatott formában is meg lehet szerezni őket):

Esetleg meg lehet próbálni beszerezni ezt a könyvet (pl. az antikvarszakkonyv.hu honlapon):

  • Mikrológia 19, Módszeres programozás, programozási tételek (Szlávi Péter, Zsakó László)

Ha pedig van, akit a programozási tételek matematikai háttere érdekel, annak ezt tudom ajánlani:

Hogy van angolul a programozási tételek?

Alaposan utánakerestem, utánakérdeztem, de nincs pontos angol kifejezés, amire rákeresve konkrétan a fentebb felsorolt algoritmusokat kapnánk meg (a legtöbb keresési találat esetén).

programozasi_tetelek_angolul.png

Felmerülő válaszok:

  • basic algorithms, essential algorithms, top 5 algorithms, top 10 algorithms:
    Ezekre rákeresve olyanokat is megkapunk, mint például a Dijkstra's Algorithm, Huffman Coding Compression Algorithm, Euclid’s Algorithm.
    Ezeket egyetlen magyar tananyagban sem találtam a programozási tételek között felsorolva. Ezek inkább az algoritmusok és adatszerkezetek tantárgy témái.
  • programming principles:
    Erre rákeresve inkább design pattern, coding standard, best practice, coding style guide, core guideline, clean code témájába illő találatokat kapunk. Pl. DRY, SOLID elvek
    Ezekről ebben a tananyagban itt volt szó: kódolási minták, konvenciók
  • programming theses:
    Teljesen más keresési találatokat kapunk erre rákeresve. Jellemzően mély emlélet, esetleg szakdolgozatok, phd munkák.
  • programming theorems:
    Jellemzően ELTE-s körökben így fordították le, így lehet vele találkozni általuk írt angol cikkekben.
    Például: [1] [2] [3] (pdf)
    Viszont egyrészt ez a kifejezés így használva az angol szakirodalomban nincs elterjedve (ha nemzetközi csoportokban, fórumokon (pl. stackoverflow-n) használnánk ezt a kifejezést, jó eséllyel nem értenék, mire gondolunk), másrészt a kifejezésre rákeresve teljesen más találatokat is kapunk: wikipedia - structured program theorem

előző tananyagrész: STL

Megszámlálás

2 eset van:

  • megszámoljuk az összes elemet
  • megszámoljuk a bizonyos feltételnek megfelelő elemeket

Mivel általában tömböket, tömbszerű adatszerkezeteket használunk, így annak nincs sok értelme, hogy megszámoljuk az összes elemet, hiszen az a tömb elemszámát jelentené, a tömb elemszámát pedig vagy tároljuk egy változóban, vagy pl. std::vector esetén a size() tagfüggvénnyel könnyen megkaphatjuk.

Így tehát jó eséllyel ezt a programozási tételt a bizonyos feltételnek megfelelő elemek megszámolására használjuk.

Milyen értékeket számolhatunk meg jellemzően?

  • Például számok esetén: páros számok, páratlan számok, negatív számok, nullák, prímszámok
  • Például szövegek esetén: valahány karakternél (pl 5 karakternél hosszabb) szövegek, bizonyos karaktereket/szavakat tartalmazó szövegek

Ebben a példában a vec_example nevű std::vectorban lévő páros számokat számoljuk meg.

A count nevű változóban fogjuk tárolni a megszámlálás eredményét. Ennek a változónak a kezdőértéke értelemszerűen 0, hiszen ha esetleg egyetlen elem sem felel meg a feltételnek, akkor az azt jelenti, hogy 0 elem felelt meg a feltételnek.

A for ciklusban végig kell mennünk a tömbszerű adatszerkezet utolsó eleméig (hiszen nem tudhatjuk, hogy az utolsó elem megfelel-e a feltételnek).

Ha már végig kell mennünk a teljes adatszerkezeten, használhatnánk akár ranged for ciklust is, vagy foreach függvényt iterátorokkal, melyek így néznének ki:

ranged for ciklus:

for (const int& element : vec_example) { if (element % 2 == 0) {++count;} }

foreach függvény iterátorokkal (ne felejtsük el, hogy ennek használatához includeolnunk kell az algorithm header fájlt):

#include <algorithm>

[...]

std::for_each(vec_example.begin(), vec_example.end(), [&](const int& element) { if (element % 2 == 0 ) {++count; } });

A példaprogram (hagyományos for ciklussal):

//count even elements of "vec_example" std::vector
#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};
  int count = 0;

  for (int i = 0; i < vec_example.size(); ++i) {
    if (vec_example[i] % 2 == 0) {
      ++count;
    }
  }

  std::cout << "Number of even numbers: " << count << '\n';
}

A példaprogram függvénnyel (count_even):

//count even elements of "vec_example" std::vector
#include <iostream>
#include <vector>

//define count function
int count_even(const std::vector<int>& numbers) {
  int count = 0;
  for (const int& element : numbers) { if (element % 2 == 0) {++count;} }
  return count;
}

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};

  std::cout << "Number of even numbers: " << count_even(vec_example) << '\n';
}

Esetleg olyat is szoktak, hogy a feltétel ellenőrzését külön függvénybe szervezik (is_even). Annak ellenére, hogy ez több karakterből áll, mintha ezt kihagynánk, tulajdonképpen átláthatóbbá teszi a kódot.

//count even elements of "vec_example" std::vector
#include <iostream>
#include <vector>

//define is_even function
bool is_even(const int& p_number) { return p_number % 2 == 0; }

//define count function
int count_even(const std::vector<int>& numbers) {
  int count = 0;
  for (const int& element : numbers) { if (is_even(element)) {++count;} }
  return count;
}

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};

  std::cout << "Number of even numbers: " << count_even(vec_example) << '\n';
}

Hasonló célre használható az STL std::count és std::count_if függvénye.

Összegzés

Hasonló mint a megszámlálás azzal a különbséggel, hogy egy 0 kezdőértékű változóhoz nem 1-et adunk hozzá egy elem esetén, hanem az elem értékét adjuk hozzá.

2 eset van:

  • összeadjuk az összes elemet
  • csak bizonyos feltételnek megfelelő elemeket adunk össze

A megszámlálással ellentétben az összegzés esetén van értelme az összes elem összegzésének is, hiszen azonos elemszám esetén az összeg eltérő lehet.

Ezt a tételt nem fogjuk olyan részletesen kielemezni, mint a megszámlálást, hiszen az egész tulajdonképpen csak egy műveleti jelben tér el a megszámlálástól.

A példaprogramban összeadjuk a vec_example nevű std::vectorban lévő páros számokat. Az összeadás eredményét a sum nevű változó tárolja.

//sum even elements of "vec_example" std::vector
#include <iostream>
#include <vector>

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};
  int sum = 0;

  for (int i = 0; i < vec_example.size(); ++i) {
    if (vec_example[i] % 2 == 0) {
      sum += example[i];
    }
  }

  std::cout << "Sum of even numbers: " << sum << '\n';
}

Függvénnyel:

//sum even elements of "vec_example" std::vector
#include <iostream>
#include <vector>

bool is_even(const int& p_number) { return p_number % 2 == 0; }

int sum_even(const std::vector<int>& numbers) {
  int sum = 0;

  for (const int& element : numbers) {
    if(is_even(element)) { sum += element; }
  }

  return sum;
}

int main() {
  std::vector<int> vec_example = {2,2,3,5,10,7,8,9,11,0};

  std::cout << "Sum of even numbers: " << sum_even(vec_example) << '\n';
}

Hasonlóan működik az STL std::accumulate függvénye.

Sorozatszámítás

//

Maximumkiválasztás

Két eset van:

  • az összes elemet vizsgáljuk
  • csak bizonyos feltételnek megfelelő elemeket vizsgálunk

Ha az összes elemet vizsgáljuk, akkor megtehetjük azt, hogy a legnagyobb érték tárolására használt változónak először értékül adjuk az első elemet, majd ha ennél nagyobbat találunk, akkor lecseréljük arra az értékre.
Ebben az esetben a ciklust elég a második elemtől indítani, mivel ha az első elemtől indítanánk, akkor az eddigi legnagyobb értéket (vagyis az első elemet) önmagával hasonlítanánk össze.

//max
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {13,8,7,21,5,32,-2,17,11,10};
  int max = example[0];

  for (int i = 1; i < example.size(); ++i) {
    if (max < example[i]) {
      max = example[i];
    }
  }

std::cout << "The biggest number: " << max << '\n';
}

Feltételes maximumkeresés

Ha bizonyos feltételnek megfelelő elemek között keressük a legnagyobb értéket, akkor viszont ügyelnünk kell arra is, hogy előfordulhat, hogy nincs is a feltételnek megfelelő érték az értékek között. Ezt általában egy logikai változóval jelezzük. Ezt a logikai változót általában össze szokták valahogy kötni a maximum értéket tárolni kívánt változóval, pl egy std::pair segítségével, illetve erre szokták az optional adatszerkezetet használni, amit C++-ban csak a C++17-es szabványtól érhetünk el std::optional néven.

A logikai változó értékét false-ra állítjuk. Ha ez false marad a ciklus végéig, akkor az azt jelenti, hogy nem találtunk a feltételnek megfelelő (páros) elemet.

Ha megtaláljuk az első feltételnek megfelelő (páros) elemet, akkor a logikai változó értékét true-ra kell állítanunk, ezzel jelezve, hogy van a feltételnek megfelelő elem. Innentől kezdve az algoritmus ugyanúgy működik mint a hagyományos maximum keresés. A további páros elemekből ha van olyan, ami nagyobb, mint amit eddig találtunk, akkor azt fogjuk eltárolni.

//max of even numbers
#include <iostream>
#include <vector>
#include <tuple>

bool is_even(const int& p_number) { return p_number % 2 == 0; }

std::pair<int, bool> max_of_even(const std::vector<int>& numbers) {
  std::pair<int, bool> max;
  max.second = false;

  for (const int& element: numbers) {
    if (is_even(element)) {
      if (!max.second) {
        max.first = element;
        max.second = true;
      } else if (max.second && element > max.first) {
        max.first = element;
      }
    }
  }
  return max;
}

int main() {
  std::vector<int> vec_example = {13,8,7,21,5,31,-2,17,11,10};

  std::pair<int, bool> max = max_of_even(vec_example);

  if (!max.second) {
    std::cout << "There is no even number in the std::vector\n";
  } else {
    std::cout << "The max even number in the std::vector: " << max.first << '\n';
  }
}

Megjegyzés: ebben a feladatban a maximum indexét nem tároltuk.

Eldöntés

Két dolgot vizsgálhatunk:

  • van-e az elemek között a feltételnek megfelelő
  • az összes elem a feltételnek megfelelő

Ebben a tételben nem vizsgáljuk a következőket:

  • a feltételnek megfelelő elem, elemek értéke, indexe
  • hány darab feltételnek megfelelő elem van

Egy logikai változóban tároljuk, hogy találtunk-e a feltételnek megfelelő elemet. A logikai változó kezdőértéke hamis, és ha nincs az elemek között a feltételnek megfelelő, akkor a ciklus végén is hamis marad a logikai változó értéke.
Ha találunk a feltételnek megfelelő elemet, akkor a logikai változó értékét igazra állítjuk.

Van viszont valami, ami az eddigi tételekben nem fordult elő. Ha csak az a lényeg, hogy eldöntsük, hogy az elemek között van-e a feltételnek megfelelő, akkor ha megtaláltuk az első ilyen elemet, nem kell tovább folytatnunk a ciklust, kiléphetünk a ciklusból.

Általában megvetendőnek tartják, ha a ciklusból való kilépést a break utasítással érjük el. Ezzel kapcsolatban 3 dolgot érdemes tudni:

  • ciklusok esetén a break használata kiváltható azzal, ha módosítjuk a ciklus feltételét
  • ranged for ciklusból elfogadottnak tartják a break utasítással való kilépést
  • ha függvényeket használunk, akkor a return utasítás kiváltja a break utasítást

Ebben a példában azt vizsgáljuk, hogy van-e az elemek között negatív szám.

//contains negative
#include <iostream>
#include <vector>

int main() {
  std::vector<int> example = {13,8,7,21,5,32,-2,17,11,10};
  bool contains_negative = false;

  for (int i = 0; i < example.size() && !contains_negative; ++i) {
    if (example[i] < 0) {
      contains_negative = true;
    }
  }

  if (contains_negative) {
    std::cout << "There is an even number in the numbers.\n";
  } else {
    std::cout << "There isn't any even number in the numbers.\n";
  }
}

Függvénnyel:

//contains negative
#include <iostream>
#include <vector>

bool is_negative(const int& p_number) { return p_number < 0;}

bool contains_negative(std::vector<int>& numbers) {
  for (const int& element : numbers) {
    if(is_negative(element)) {
      return true;
    }
  }
  return false;
}

int main() {
  std::vector<int> vec_example1 = {13,8,7,21,5,32,-2,17,11,10};
  std::vector<int> vec_example2 = {13,8,7,21,5,32, 2,17,11,10};

  if (contains_negative(vec_example1)) {
    std::cout << "There is a negative number in vec_example1.\n";
  } else {
    std::cout << "There isn't any negative number in vec_example1.\n";
  }

  if (contains_negative(vec_example2)) {
    std::cout << "There is a negative number in vec_example2.\n";
  } else {
    std::cout << "There isn't any negative number in vec_example2.\n";
  }
}

Hasonlóan működik az std::find vagy std::find_if algoritmus.

Kiválasztás

Ezt a programozási tételt akkor alkalmazzuk, amikor biztosra vesszük, hogy az adott elemek között van a feltételnek megfelelő, amit keresünk, és ezek közül az elsőt adjuk vissza.

Random generálással létrehozunk 7 dobókockával dobott értéket. Ezek között biztos lesz 2 egyező érték. Az első egyező érték helyét (index+1) adjuk vissza.

//first duplicate
#include <iostream>
#include <random>
#include <vector>

int select_first_duplicate(std::vector<int>& numbers) {
  for (int i = 0; i < numbers.size(); ++i) {
    for (int j = i+1; j < numbers.size(); ++j) {
      if (numbers[i] == numbers[j]) {
        return i+1;
      }
    }
  }
}

int main() {
  //initialize random
  std::random_device rnd_device;
  std::mt19937 rnd_generator(rnd_device());
  std::uniform_int_distribution<int> int_dist(1,6);

  std::vector<int> vec_example;
  //random generate numbers between 1 and 6, 7 times
  for (int i = 1; i <= 7; ++i) {
    vec_example.push_back(int_dist(rnd_generator));
  }

  std::cout << "The elements:\n";
  for (const int& element : vec_example) {
    std::cout << element << ' ';
  }
  std::cout.put('\n');

  std::cout << "The place of the first duplicate value: " << select_first_duplicate(vec_example) << '\n';
}

Lineáris keresés

Ez a tétel akár lehetne az eldöntés és a kiválasztás hibridje. Ha nincs a feltételnek megfelelő elem, azt egy logikai változóban tároljuk, ha van, akkor pedig az első találatnak az helyét (index+1) adjuk vissza. Ez utóbbi esetben kiléphetünk a ciklusból.

//linear search (even number)
#include <iostream>
#include <vector>
#include <tuple> int main() { std::vector<int> vec_example = {13,8,7,21,5,32,-2,17,11,10}; std::pair<int, bool> found; found.second = false; for (int i = 0; i < vec_example.size() && !found.second; ++i) { if (vec_example[i] % 2 == 0) { found.second = true; found.first = i+1; } } if (found.second) { std::cout << "There is an even number in the numbers.\n"; std::cout << "Its place is: " << found.first << '\n'; } else { std::cout << "There isn't any even number in the numbers.\n"; } }

Függvénnyel:

//linear search (even number)
#include <iostream>
#include <vector>
#include <tuple>

bool is_even(const int& p_number) { return p_number % 2 == 0; }

std::pair<int, bool> find_even(std::vector<int>& numbers) {
  std::pair<int, bool> found;
  found.second = false;

  for (int i = 0; i < numbers.size(); ++i) {
    if (is_even(numbers[i])) {
      found.second = true;
      found.first = i+1;
      return found;
    }
  }
  return found;
}

int main() {
  std::vector<int> vec_example = {13,8,7,21,5,32,-2,17,11,10};

  std::pair<int, bool> found = find_even(vec_example);

  if (found.second) {
    std::cout << "There is an even number in the numbers.\n";
    std::cout << "Its place is: " << found.first << '\n';
  } else {
    std::cout << "There isn't any even number in the numbers.\n";
  }
}

Hasonlóan működik az STL std::find_if függvénye.

Logaritmikus, vagy más néven bináris keresés

Csak rendezett tömbökre működik.

Megfelezzük a tömböt. Megnézzük, hogy az elem a tömb első vagy a második felében van. Ha például az első felében, akkor azt tovább felezzük, és így tovább, amíg meg nem találjuk az elemet.

Ebben a példában egy 1 és 12 közti random generált számot keresünk meg egy 1 és 10 közötti számokat tartalmazó tömbben.

//binary search
#include <iostream>
#include <random>
#include <vector>
#include <algorithm>

int generate_rnd_number(const int& intval_begin, const int& intval_end) {
  static std::mt19937 rnd_generator( std::random_device{}());
  std::uniform_int_distribution<int> int_dist(intval_begin,intval_end);
  return int_dist(rnd_generator);
}

int main () {
  std::vector<int> example = {1,2,3,4,5,6,7,8,9,10};
  int find = generate_rnd_number(1,12);
  bool contains = false;
  int index = -1;

  int low = 0;
  int high = example.size()-1;

  while (low <= high && !contains) {
    int mid = (low + high) / 2;
    if (find == example[mid]) {
      contains = true;
      index = mid;
    } else if (find < example[mid]) {
      high = mid-1;
    } else if (find > example[mid]) {
    low = mid+1;
  }
}

  std::cout << "Find: " << find << '\n';
  if (contains) {
    std::cout << "Found at index: " << index << '\n';
  } else {
    std::cout << "Not found\n";
  }
}

Kiválogatás

Egy tömbből bizonyos feltételnek megfelelő elemeket átmásoljuk egy másik tömbbe. Pl. kiválogatjuk a páros számokat.

//select
#include <iostream>
#include <vector>

int main() {
  std::vector<int> input = {1,2,3,4,5,6,7,8,9,10};
  std::vector<int> output;

  for (int i = 0; i < input.size(); ++i) {
    if (input[i] % 2 == 0) {
      output.push_back(input[i]);
    }
  }

  for (const int& element : output) {
    std::cout << element << " ";
  }
  std::cout.put('\n');
}

Szétválogatás

Egy tömbből bizonyos feltételnek megfelelő elemeket átmásoljuk egy másik tömbbe, a feltételnek nem megfelelő elemeket pedig egy harmadik tömbbe.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> input = {1,2,3,4,5,6,7,8,9,10};
  std::vector<int> even;
  std::vector<int> odd;

  for (int i = 0; i < input.size(); ++i) {
    if (input[i] % 2 == 0) {
      even.push_back(input[i]);
    } else {
      odd.push_back(input[i]);
    }
  }

  std::cout << "Even numbers:\n";
  for (const int& element : even) {
    std::cout << element << " ";
  }
  std::cout.put('\n');

  std::cout << "Odd numbers:\n";
  for (const int& element : odd) {
    std::cout << element << " ";
  }
  std::cout.put('\n');
}

Szétválogatás egy tömbön belül (rendezés nélkül)

Ebben a példában páros és páratlan számokat válogatunk szét. A párosak kerülnek a tömb elejére, a páratlanok a tömb végére.

Az első elem mindenképp át lesz helyezve, mégpedig középre, így tehát mindegy, hogy páros vagy páratlan. A többi áthelyezésnél pedig mindig az előző áthelyezésnél felszabadult helyre helyezünk át.

#include <iostream>
#include <random>
#include <vector>

void generate_rnd_number(std::vector<int>& vec, const int& howmany, const int& intval_begin, const int& intval_end) {
  static std::mt19937 rnd_generator( std::random_device{}());
  std::uniform_int_distribution<int> int_dist(intval_begin, intval_end);

  for (int i = 0; i < howmany; ++i) {
    vec.push_back(int_dist(rnd_generator));
  }
}

void print_vector(const std::vector<int>& vec) {
  for (const int& element : vec) { std::cout << element << ' '; }
  std::cout.put('\n');
}

bool is_even(const int& p_element) {
  return p_element % 2 == 0;
}

void even_odd_sort(std::vector<int>& vec){
  int low = 0;
  int high = vec.size()-1;
  int mid = vec[0];

  while (low < high){
    while (low < high && !is_even(vec[high])) {
      --high;
    }

    if (low < high) {
      vec[low] = vec[high];
      ++low;
    }

    while (low < high && is_even(vec[low])){
      ++low;
    }

    if (low < high){
      vec[high] = vec[low];
      --high;
    }
  }
  vec[low] = mid;
}

int main() {
  std::vector<int> stdvec_example1;

  const int howmany = 10;
  generate_rnd_number(stdvec_example1, howmany, 1, 100);

  std::cout << "Elements before sorting:\n";
  print_vector(stdvec_example1);

  even_odd_sort(stdvec_example1);

  std::cout << "Elements after sorting:\n";
  print_vector(stdvec_example1);
}

Összefésülés, összefuttatás

Két rendezett tömb elemeit átmásoljuk egy harmadik tömbbe, a rendezettséget megőrízve.

Először két tömbön haladunk egy ciklussal addig amíg az egyik tömb végére nem érünk. Eközben amelyik tömbben van éppen kisebb elem, azt másoljuk át a harmadik tömbbe, és növeljük az annak megfelelő ciklusváltozót. Ha esetleg az elemek egyenlőek (ebben a példában ilyen eset nem fordul elő), akkor mindkét ciklusváltozót növeljük.

Ezt követően ha az egyik tömb feldolgozása még nem ért véget, akkor a fennmaradó elemeket átmásoljuk a harmadik tömbbe.

#include <iostream>
#include <vector>

int main() {
  std::vector<int> even = {2,4,6,8,10,12,14,16};
  std::vector<int> odd = {1,3,5,7,9,11,13};
  std::vector<int> output;

  int i = 0, j = 0;
  for (; i < even.size() && j < odd.size();) {
    if (even[i] < odd[j]) {
      output.push_back(even[i]);
      ++i;
    } else if (odd[j] < even[i]) {
      output.push_back(odd[j]);
      ++j;
    } else if (even[i] == odd[j]) {
      output.push_back(even[i]);
      ++i; ++j;
    }
  }

  for (; i < even.size(); ++i) {
    output.push_back(even[i]);
  }

  for (; j < odd.size(); ++j) {
    output.push_back(odd[j]);
  }

  for (const int& element : output) {
    std::cout << element << " ";
  }std::cout.put('\n');
}

Maximumkeresés indexek kiválogatásával

Miután az elemek közül megkerestük a legnagyobbat, kigyűjthetjük annak összes előfordulását is.

Érdemesebb először egy külön ciklusban megkeresni a legnagyobb elemet, mintsem ahogy a legnagyobb elemet keressük, rögtön gyűjtögetni hozzá az előfordulások indexeit (amit mindig üríteni kéne, ha találunk egy nagyobb elemet).

Az indices az index többesszáma angolul.

//max with all indices
#include <iostream>
#include <vector>

//find max
int find_max(std::vector<int>& numbers) {
  int max = numbers[0];
  for (int i = 1; i < numbers.size(); ++i) {
    if (numbers[i] > max) {
      max = numbers[i];
    }
  }
  return max;
}

//find all indices of max
std::vector<int> find_all_indices(std::vector<int>& numbers, const int& max) {
  std::vector<int> indices;
  for (int i = 0; i < numbers.size(); ++i) {
    if (numbers[i] == max) {
      indices.push_back(i);
    }
  }
  return indices;
}

int main() {
  std::vector<int> vec_example = {2,4,-1,11,2,11,6,7,11};

  int max = find_max(vec_example);

  std::cout << "The max value in vec_example: " << max << '\n';

  std::vector<int> indices = find_all_indices(vec_example, max);

  std::cout << "All indices of " << max << ":\n";
  for (const int& index : indices) {
    std:: cout << index << ' ';
  }
}

Kiválogatás indexek kiválogatásával

Míg a maximumkeresésnél csak egyetlen érték lehetett a maximum, itt az összes különböző értékű elemnél ki kell gyűjteni a hozzá tartozó indexeket. Arra is ügyelni kell, hogy azok az elemek, amikhez az indexeket kigyűjtjük, csak egyszer szerepeljenek, mivel ha többször szerepelnek, akkor többször ki kell gyűjteni hozzájuk az indexeket, ami felesleges.

Először a filter_unique nevű függvénnyel kiválogatjuk egy halmaz (std::set) adatszerkezetbe a páros számokat. A halmaz adatszerkezetben egy elem csak egyszer szerepelhet, még akkor is, ha megpróbáljuk többször is hozzáadni az insert tagfüggvénnyel.

A filter_indices függvény lehet, hogy elsőre nem átlátható. Az indices az index többesszáma angolul vagyis indexek. 

Egy ilyen típusú adatszerkezetbe gyűjtjük ki az elemeket:

std::vector<std::pair<int, std::vector<int>>>

Ez azt jelenti, hogy több olyan párt tárolunk, ahol a pár első eleme egy szám (az előző feladatban kigyűjtütt páros számok egyike), a pair második eleme pedig egy std::vector, ami majd az adott szám előfordulásait, vagyis indexeit fogja tartalmazni.

Ennek a függvénynek átadtuk a kiválogatott elemeket (a halmaz adatszerkezetet), illetve az std::vectort, amiben az eredeti elemek vannak. Ez utóbbiból tudjuk kiválogatni az elemek előfordulásait, indexeit.

Egy for ciklusban először egy std::pair adatszerkezet első elemének értékül adjuk a világogatott elemek (filtered_numbers) soron következő elemét. Az előfordulásokhoz egy belső for ciklus kell, amivel az std::vectoron megyünk végig, ami az eredeti elemeket tartalmazta.

//filter unique even numbers with incides
#include <iostream>
#include <set>
#include <vector>
#include <tuple>

bool is_even(const int& p_number) { return p_number % 2 == 0; }

//filter unique even numbers
std::set<int> filter_unique(std::vector<int>& numbers) {
  std::set<int> filtered;

  for (const int& element : numbers) {
    if (is_even(element)) {
      filtered.insert(element);
    }
  }
  return filtered;
}

//filter indices for each even number
std::vector<std::pair<int, std::vector<int>>> filter_indices(const std::set<int>& filtered_numbers, const std::vector<int>& numbers) {
  std::vector<std::pair<int, std::vector<int>>> indices;

  for (const int& element : filtered_numbers) {
    std::pair<int, std::vector<int>> a_pair;
    a_pair.first = element;

    for (int i = 0; i < numbers.size(); ++i) {
      if (a_pair.first == numbers[i]) {
        a_pair.second.push_back(i);
      }
    }
    indices.push_back(a_pair);
  }
  return indices;
}

int main() {
  std::vector<int> vec_example = {2,4,-1,11,2,11,6,4,11};

  std::set<int> filtered = filter_unique(vec_example);

  std::cout << "Filtered elements of vec example:\n";

  for (const int& element : filtered) {
    std::cout << element << ' ';
  }
  std::cout.put('\n');

  std::vector<std::pair<int, std::vector<int>>> indices = filter_indices(filtered, vec_example);

  std::cout << "Indices:\n";
  for (const std::pair<int, std::vector<int>>& element : indices) {
    std::cout << element.first << ":\n";
    for (const int& index : element.second) {
      std::cout << index << ' ';
    }
    std::cout.put('\n');
  }
}

Buborékrendezés

//bubble sort
#include <iostream>
#include <random>
#include <vector>

int main() {
  std::vector<int> stdvec_example = {9,6,11,3,1,7,8,-2};

  for (int i = stdvec_example.size()-1; i >= 0; --i) {
    for (int j = 0; j < i; ++j) {
      if (stdvec_example[j] > stdvec_example[j+1]) {
        int temp = stdvec_example[j];
        stdvec_example[j] = stdvec_example[j+1];
        stdvec_example[j+1] = temp;
      }
    }
  }

  for (const int& element : stdvec_example) {
    std::cout << element << ' ';
  }
  std::cout.put('\n');
}

Egyéb tananyagok

előző tananyagrész: STL

A bejegyzés trackback címe:

https://itkezdoknek.blog.hu/api/trackback/id/tr617798349

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.

Nincsenek hozzászólások.
süti beállítások módosítása