Alap & Összetett Programozási Tételek
A Neumann János Egyetem mérnökinformatikus és programozói vizsgakövetelményeinek algoritmusai tiszta C++ forráskódokkal és működési animációkkal szemléltetve.
Tételek áttekintése:
I. Alap Programozási Tételek
Egyetlen bemeneti sorozaton végeznek vizsgálatot, és egyetlen kimenetet (összeg, darabszám, logikai igaz/hamis, sorszám/index, vagy szélsőérték) szolgáltatnak.
Összegzés Tétele
Kiszámítja a sorozat elemeinek összegét.
Egy gyűjtőváltozót (szum) 0-ra állítunk, majd a sorozat minden elemét hozzáadjuk a számláló ciklus futása során. Átlagszámítás esetén ezt az összeget osztjuk az elemek számával.
#include <iostream>
using namespace std;
int osszegzes(int tomb[], int meret) {
int szum = 0;
for (int i = 0; i < meret; i++) {
szum += tomb[i];
}
return szum;
}
int main() {
int szamok[] = {4, 7, 2, 9, 1};
int n = sizeof(szamok) / sizeof(szamok[0]);
cout << "Osszeg: " << osszegzes(szamok, n) << endl; // 23
return 0;
}Megszámolás Tétele
Megmondja, hány olyan elem van a sorozatban, amely egy adott tulajdonságnak megfelel.
Egy számláló változót (db) 0-ra inicializálunk. A ciklusban minden elemet megvizsgálunk a feltétellel (pl. páros-e), és ha a feltétel teljesül, megnöveljük a számlálót eggyel.
#include <iostream>
using namespace std;
int megszamlalas_paros(int tomb[], int meret) {
int db = 0;
for (int i = 0; i < meret; i++) {
if (tomb[i] % 2 == 0) {
db++;
}
}
return db;
}
int main() {
int szamok[] = {4, 7, 2, 9, 1, 8};
int n = sizeof(szamok) / sizeof(szamok[0]);
cout << "Paros elemek szama: " << megszamlalas_paros(szamok, n) << endl; // 3
return 0;
}% 2 == 0) elemeknél ugrik a számláló: 1, 2, 3. Eldöntés Tétele
Megvizsgálja, hogy van-e a sorozatban adott tulajdonságú elem (az eredmény igaz vagy hamis).
Ciklussal lépkedünk végig a sorozaton. Amint találunk egy olyan elemet, amely kielégíti a feltételt (pl. negatív szám), azonnal megszakítjuk a ciklust és igaz (true) értékkel térünk vissza. Ha a sorozat végére érünk anélkül, hogy találnánk ilyet, az eredmény hamis (false).
#include <iostream>
using namespace std;
bool van_e_negativ(int tomb[], int meret) {
for (int i = 0; i < meret; i++) {
if (tomb[i] < 0) {
return true; // Megtaláltuk, az eredmény azonnal IGAZ
}
}
return false; // Végigértünk, az eredmény HAMIS
}
int main() {
int szamok[] = {5, 12, -3, 8, 20};
int n = sizeof(szamok) / sizeof(szamok[0]);
cout << (van_e_negativ(szamok, n) ? "Van benne negativ szam (true)" : "Nincs benne (false)") << endl;
return 0;
}Kiválasztás Tétele
Megadja egy adott tulajdonságú elem sorszámát (indexét), amikor BIZTOSAN tudjuk, hogy az elem szerepel a sorozatban.
Mivel előfeltételünk, hogy a keresett elem garantáltan megtalálható a sorozatban (pl. strázsa módszer vagy garantált azonosító), nem szükséges vizsgálni a tömbhatár túllépését; egy while ciklussal addig lépegetünk, amíg el nem érjük az elemet.
#include <iostream>
#include <string>
using namespace std;
// Előfeltétel: A keresett elem BIZTOSAN benne van a tömbben!
int kivalasztas(string tomb[], string keresett) {
int i = 0;
while (tomb[i] != keresett) {
i++; // Addig lépkedünk, amíg meg nem találjuk
}
return i; // Visszaadjuk a biztosan megtalált elem sorszámát (indexét)
}
int main() {
string hallgatok[] = {"Kovacs", "Nagy", "Toth", "Molnar", "Szabo"};
// Biztosan tudjuk, hogy "Molnar" a listában van:
int sorszam = kivalasztas(hallgatok, "Molnar");
cout << "A 'Molnar' nevu hallgato indexe: " << sorszam << endl; // 3
return 0;
}i indexet, míg rá nem találunk. Keresés (Lineáris Keresés) Tétele
Megmondja, hogy szerepel-e a keresett elem, és ha igen, hol (megadja a sorszámát). Ha nincs benne, azt is jelzi.
Összekapcsolja az eldöntést és a kiválasztást: végigvizsgálja a tömböt a mérethatárig. Ha megtalálja, azonnal visszaadja az elem indexét (>= 0). Ha végigért és az elem nem szerepelt a sorozatban, egy speciális hibajelzéssel (tipikusan -1) jelzi a hiányát.
#include <iostream>
#include <string>
using namespace std;
int linearis_kereses(string tomb[], int meret, string keresett) {
for (int i = 0; i < meret; i++) {
if (tomb[i] == keresett) {
return i; // SZEREPEL a sorozatban: visszaadjuk a sorszámát (indexét)
}
}
return -1; // NEM SZEREPEL a sorozatban: -1-gyel jelezzük
}
int main() {
string nevek[] = {"Gabor", "Peter", "Anna", "Dora"};
int n = sizeof(nevek) / sizeof(nevek[0]);
int idx1 = linearis_kereses(nevek, n, "Anna");
if (idx1 != -1) cout << "Anna szerepel a tombben, indexe: " << idx1 << endl;
else cout << "Anna nincs a tombben!" << endl;
int idx2 = linearis_kereses(nevek, n, "Bence");
if (idx2 != -1) cout << "Bence indexe: " << idx2 << endl;
else cout << "Bence nincs a sorozatban (eredmeny: " << idx2 << ")!" << endl;
return 0;
}Maximum- és Minimumkeresés Tétele
Megkeresi egy sorozat legnagyobb vagy legkisebb értékét és annak sorszámát (indexét).
A szélsőérték kezdőértékének a sorozat legelső elemét (tomb[0]) választjuk, a kezdő index pedig 0. Ezután a 2. elemtől (index 1) kezdve végigiterálunk a tömbön: ha a vizsgált elem nagyobb a jelenlegi maximumnál (vagy kisebb a minimumnál), frissítjük az értéket és feljegyezzük az új indexet.
#include <iostream>
using namespace std;
void min_max_kereses(int tomb[], int meret, int &maxErtek, int &maxIdx, int &minErtek, int &minIdx) {
maxErtek = tomb[0];
maxIdx = 0;
minErtek = tomb[0];
minIdx = 0;
for (int i = 1; i < meret; i++) {
if (tomb[i] > maxErtek) {
maxErtek = tomb[i];
maxIdx = i;
}
if (tomb[i] < minErtek) {
minErtek = tomb[i];
minIdx = i;
}
}
}
int main() {
int szamok[] = {12, 45, 8, 92, 17, 3, 76};
int n = sizeof(szamok) / sizeof(szamok[0]);
int maxVal, maxIdx, minVal, minIdx;
min_max_kereses(szamok, n, maxVal, maxIdx, minVal, minIdx);
cout << "Maximum ertek: " << maxVal << " (index: " << maxIdx << ")" << endl;
cout << "Minimum ertek: " << minVal << " (index: " << minIdx << ")" << endl;
return 0;
}II. Összetett Programozási Tételek
Fő jellemzőjük: Ezek a tételek több adatsorozatot hoznak létre vagy alakítanak át (új tömb vagy vektor létrehozása másolással/transzformációval, szűréssel, halmazműveletekkel, vagy a sorozat elemeinek átrendezésével).
Másolás (Transzformáció) Tétele
Egy sorozat elemeit átmásolja egy másik sorozatba úgy, hogy közben mindegyiken elvégez egy műveletet (pl. mindegyiket megszorozza kettővel).
Egy forrástömb elemeit egy céltömbbe (vagy vektorba) visszük át úgy, hogy a másolási lépés közben egy tetszőleges transzformációt (szorzás, formázás, matematikai függvény) hajtunk végre az elemen.
#include <iostream>
#include <vector>
using namespace std;
// Transzformáció: minden elem megduplázása
vector<int> masolas_duplazas(int tomb[], int meret) {
vector<int> cel(meret);
for (int i = 0; i < meret; i++) {
cel[i] = tomb[i] * 2; // Művelet elvégzése másolás közben
}
return cel;
}
int main() {
int eredeti[] = {1, 3, 5, 8, 10};
int n = sizeof(eredeti) / sizeof(eredeti[0]);
vector<int> masolt = masolas_duplazas(eredeti, n);
cout << "Atmasolt, megduplazott ertekek: ";
for (int elem : masolt) {
cout << elem << " ";
}
cout << endl; // 2 6 10 16 20
return 0;
}Kiválogatás (Filterezés) Tétele
Egy sorozatból egy másik sorozatba gyűjti azokat az elemeket, amelyek megfelelnek egy feltételnek.
Végigiterálunk a forrássorozaton, megvizsgáljuk a feltételt (pl. páros-e vagy pozitív-e), és csak azokat az elemeket szúrjuk be az új tömbbe vagy vektorba, amelyekre a feltétel igaznak bizonyul.
#include <iostream>
#include <vector>
using namespace std;
// Filterezés: Csak a páros számok összegyűjtése
vector<int> kivalogatas_parosak(int tomb[], int meret) {
vector<int> kivalogatott;
for (int i = 0; i < meret; i++) {
if (tomb[i] % 2 == 0) {
kivalogatott.push_back(tomb[i]); // Csak a megfelelőt mentjük
}
}
return kivalogatott;
}
int main() {
int szamok[] = {11, 24, 7, 8, 15, 42, 3};
int n = sizeof(szamok) / sizeof(szamok[0]);
vector<int> parosak = kivalogatas_parosak(szamok, n);
cout << "Kivalogatott paros szamok: ";
for (int szam : parosak) {
cout << szam << " ";
}
cout << endl; // 24 8 42
return 0;
}Metszet Tétele
Két sorozat közös elemeit gyűjti össze egy új sorozatba.
Az első sorozat minden elemére elvégzünk egy eldöntést a második sorozaton. Ha benne van a másodikban is (és az új gyűjtőben még nem szerepel), akkor hozzáadjuk a metszethez.
#include <iostream>
#include <vector>
using namespace std;
// Segédfüggvény: Benne van-e már a vektorban? (Eldöntés tétel)
bool benne_van(const vector<int>& v, int ertek) {
for (int elem : v) {
if (elem == ertek) return true;
}
return false;
}
vector<int> metszet(int A[], int nA, int B[], int nB) {
vector<int> kozos;
for (int i = 0; i < nA; i++) {
// Megnézzük, hogy A[i] szerepel-e B tömbben:
bool benne_van_B_ben = false;
for (int j = 0; j < nB; j++) {
if (A[i] == B[j]) {
benne_van_B_ben = true;
break;
}
}
// Ha mindkettőben benne van és még nem mentettük:
if (benne_van_B_ben && !benne_van(kozos, A[i])) {
kozos.push_back(A[i]);
}
}
return kozos;
}
int main() {
int A[] = {1, 2, 4, 7, 9, 12};
int B[] = {2, 5, 7, 12, 15};
int nA = sizeof(A) / sizeof(A[0]);
int nB = sizeof(B) / sizeof(B[0]);
vector<int> res = metszet(A, nA, B, nB);
cout << "A es B metszete (kozos elemek): ";
for (int x : res) cout << x << " ";
cout << endl; // 2 7 12
return 0;
}Unió Tétele
Két sorozat összes elemét egyesíti úgy, hogy a duplikációkat kiszűri.
Első lépésként az első tömb összes elemét átmásoljuk az unióba (duplikátumok nélkül). Második lépésként a második tömb elemeit csak akkor fűzzük hozzá, ha az unió gyűjtemény még nem tartalmazza őket.
#include <iostream>
#include <vector>
using namespace std;
bool benne_van(const vector<int>& v, int ertek) {
for (int elem : v) {
if (elem == ertek) return true;
}
return false;
}
vector<int> unio(int A[], int nA, int B[], int nB) {
vector<int> egyesitett;
// 1. A tömb elemeinek hozzáadása
for (int i = 0; i < nA; i++) {
if (!benne_van(egyesitett, A[i])) {
egyesitett.push_back(A[i]);
}
}
// 2. B tömb elemeinek hozzáadása (ha még nem szerepelnek)
for (int j = 0; j < nB; j++) {
if (!benne_van(egyesitett, B[j])) {
egyesitett.push_back(B[j]);
}
}
return egyesitett;
}
int main() {
int A[] = {1, 3, 5, 7};
int B[] = {3, 4, 7, 8, 9};
int nA = sizeof(A) / sizeof(A[0]);
int nB = sizeof(B) / sizeof(B[0]);
vector<int> res = unio(A, nA, B, nB);
cout << "A es B unioja: ";
for (int x : res) cout << x << " ";
cout << endl; // 1 3 5 7 4 8 9
return 0;
}Rendezés Tétele
Növekvő vagy csökkenő sorrendbe rendezi a sorozat elemeit (pl. buborékos rendezés, cserés rendezés).
Az elemek páronkénti összehasonlításával és cseréjével (swap) mozgatja a nagyobb elemeket a sorozat végére. A programozásban a leggyakoribb klasszikus algoritmus az egyszerű cserés és a buborékos rendezés (Bubble Sort).
#include <iostream>
using namespace std;
// Buborékos rendezés (Bubble Sort)
void buborekos_rendezes(int tomb[], int meret) {
for (int i = 0; i < meret - 1; i++) {
for (int j = 0; j < meret - i - 1; j++) {
// Ha a bal oldali nagyobb mint a jobb oldali, megcseréljük:
if (tomb[j] > tomb[j + 1]) {
int ideiglenes = tomb[j];
tomb[j] = tomb[j + 1];
tomb[j + 1] = ideiglenes;
}
}
}
}
int main() {
int szamok[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(szamok) / sizeof(szamok[0]);
buborekos_rendezes(szamok, n);
cout << "Rendezett tomb (novekvo): ";
for (int i = 0; i < n; i++) {
cout << szamok[i] << " ";
}
cout << endl; // 11 12 22 25 34 64 90
return 0;
}tomb[j] > tomb[j+1], megcseréljük őket, így a nagy értékek a sor végére "lebegnek fel".