A programozás világában számtalan kihívással találkozunk, melyek néha egyszerűnek tűnnek, de mélyebb betekintést engednek az algoritmusok és adatstruktúrák csodálatos működésébe. Az egyik ilyen, elsőre talán triviálisnak tűnő, mégis sokat tanító feladat, egy számról eldönteni, hogy tükörszám-e, más néven palindróma szám. Ez azt jelenti, hogy ha visszafelé olvasva is ugyanazt az értéket kapjuk. Gondoljunk csak a 121-re, vagy a 7-re, esetleg az 5445-re. Ezek mind tükörszámok. De hogyan is vizsgálhatjuk meg ezt programozási szempontból, és miért érdemes ehhez a verem adatstruktúrát használni C++-ban?
Mi is az a Tükörszám? 🤔
Egy szám akkor tükörszám, ha fordított sorrendben olvasva is pontosan ugyanazt az értéket mutatja. A legszemléletesebb példa erre a már említett 121. Ha balról jobbra olvassuk, 121, ha jobbról balra, szintén 121. Ugyanez igaz az 5-re, 424-re, vagy 8778-ra. A negatív számok és a lebegőpontos értékek kezelése általában egyedi megállapodást igényel, de a klasszikus definíció szerint a pozitív egész számokra vonatkozik ez a jellemző. Ez a feladat nem csupán elméleti érdekesség, hanem kiválóan alkalmas arra, hogy bemutassa az adatstruktúrák, mint például a verem, gyakorlati alkalmazását.
Miért pont a Verem (Stack)? ⬆️⬇️
A verem egy alapvető, absztrakt adatstruktúra, mely a „utoljára be, elsőre ki” (LIFO – Last-In, First-Out) elv alapján működik. Gondoljunk egy tányérkupacra: mindig a legfelső tányért vesszük le (POP), és mindig a tetejére tesszük az újat (PUSH). Ez a tulajdonság teszi a vermet ideális eszközzé olyan feladatoknál, ahol a sorrend megfordítása a cél.
Amikor egy számot tükrözni szeretnénk, valójában a számjegyeinek sorrendjét fordítjuk meg. Vegyük például a 123-at.
1. Az első számjegy (jobbról) a 3.
2. A második a 2.
3. A harmadik az 1.
Ha ezeket a számjegyeket egy verembe tesszük, majd kivesszük, akkor pont fordított sorrendben kapjuk meg őket: 1, 2, 3. Ebből már könnyedén újraépíthetjük a számot fordítva (321). És pontosan ez a veremhasználat lényege a tükörszám ellenőrzésénél!
A Logika Lépésről Lépésre 👣
Nézzük meg, hogyan építhetjük fel a logikát lépésről lépésre egy adott szám verem segítségével történő ellenőrzéséhez:
1. Számjegyek kinyerése és verembe helyezése: Először is, az eredeti számból ki kell nyernünk a számjegyeket, méghozzá hátulról előre, azaz a legkevésbé jelentős számjegytől (egyes helyi érték) a legjelentősebb felé. Ezt a modulo operátor (%) és az egész szám osztás (/) segítségével tehetjük meg. Minden egyes kinyert számjegyet azonnal tegyünk fel a verembe.
* Példa a 123-ra:
* 123 % 10 = 3 (PUSH 3)
* 123 / 10 = 12
* 12 % 10 = 2 (PUSH 2)
* 12 / 10 = 1
* 1 % 10 = 1 (PUSH 1)
* 1 / 10 = 0 (vége a folyamatnak)
Ekkor a verem tetején az 1-es, alatta a 2-es, legalul pedig a 3-as van.
2. A tükrözött szám felépítése: Amikor kivesszük a számjegyeket a veremből (POP), éppen fordított sorrendben kapjuk meg őket, mint ahogyan bekerültek. Ezen kivett számjegyekből építjük fel a fordított számot.
* Példa a veremből kivéve (123-hoz):
* POP 1
* POP 2
* POP 3
Ebből a sorrendből (1, 2, 3) kellene felépítenünk a 321-et. Ez egy kulcsfontosságú pont, hiszen a verem most éppen az eredeti sorrendet adja vissza, nem a fordítottat! A LIFO elv azt jelenti, hogy az utoljára betett (az 1-es) jön ki először. Ez egy csapda!
Valójában a verem akkor adja vissza a fordított sorrendet, ha az eredeti számot NEM megfordítva, hanem sorban, elölről hátrafelé tesszük bele. De számjegyekre bontásnál mindig hátulról előre haladunk. Tehát a veremben a számjegyek „fordítva” fognak állni.
Akkor a helyes logika így néz ki:
* Az eredeti számot eltároljuk egy ideiglenes változóban, mert a számjegyek kinyerése során az eredeti szám megváltozik.
* Miközben kinyerjük a számjegyeket (hátulról előre), tegyük őket egy verembe.
* Ezután, a veremből kivéve a számjegyeket (ezek az eredeti szám „előlről hátrafelé” olvasott számjegyei), építsük fel belőlük a fordított számot.
Nézzük újra a 123-at:
* Verembe tesszük: 3, 2, 1 (legalul 3, tetején 1)
* Most vegyük ki a veremből és építsük fel a fordított számot:
* Kivesz 1 (reversed = 0 * 10 + 1 = 1)
* Kivesz 2 (reversed = 1 * 10 + 2 = 12)
* Kivesz 3 (reversed = 12 * 10 + 3 = 123)
Ez így nem jó, mert visszaadja az eredeti számot!
A verem akkor hasznos, ha KÉT verembe tesszük a számjegyeket, vagy ha az eredeti számot és a veremből visszaépített számot hasonlítjuk össze.
Ahhoz, hogy a verem tényleg a fordított számot hozza létre, a következő megközelítés szükséges:
1. **Számjegyek tárolása veremben:**
* Vegye az eredeti számot (pl. `num = 121`).
* Egy `tempNum = num` változóval dolgozzon.
* Amíg `tempNum > 0`:
* `digit = tempNum % 10`
* `stack.push(digit)`
* `tempNum /= 10`
* Ekkor a veremben a számjegyek fordított sorrendben vannak: 1, 2, 1 (alul 1, felette 2, legfelül 1).
2. **Összehasonlítás az eredeti számmal (vagy új fordított szám építése):**
Most, hogy a számjegyek bent vannak a veremben, hogyan ellenőrizzük, hogy az eredeti szám palindróma-e?
A verem LIFO természete miatt, amikor elkezdjük kivenni a számjegyeket, azokat pont fordított sorrendben kapjuk vissza, mint ahogyan az eredeti számban voltak (azaz a legkevésbé jelentőstől a legjelentősebbig).
* Egy `reversedNum = 0` változót inicializálunk.
* Amíg a verem nem üres:
* `digit = stack.top()`
* `stack.pop()`
* `reversedNum = reversedNum * 10 + digit`
* Ezzel a módszerrel a `reversedNum` pontosan a `num` számjegyeinek fordítottját fogja tartalmazni.
3. Összehasonlítás: Végül összehasonlítjuk az eredeti számot (`num`) a veremből visszaépített `reversedNum` értékkel. Ha megegyeznek, akkor a szám tükörszám.
Ez a megközelítés elegáns és pontosan kihasználja a verem LIFO elvét.
C++ Implementáció – A Kód Beszél 💻
Lássuk, hogyan valósíthatjuk meg ezt C++-ban! Szükségünk lesz az `
„`cpp
#include
#include
#include
#include
/**
* @brief Ellenőrzi, hogy egy adott pozitív egész szám tükörszám-e verem segítségével.
* @param num A vizsgálandó szám.
* @return true, ha a szám tükörszám; false, ha nem.
*/
bool isPalindromeStack(int num) {
// Negatív számok és a 0 speciális kezelése
// Hagyományosan a negatív számokat nem tekintjük tükörszámnak,
// mivel a „-” jel nem tükröződik.
// A 0 viszont tükörszám.
if (num < 0) {
return false;
}
if (num == 0) {
return true;
}
// Eltároljuk az eredeti számot, mert a számjegyek kinyerése során megváltozik
int originalNum = num;
std::stack
// A számjegyek kinyerése és verembe helyezése
// A loop addig fut, amíg a szám nagyobb, mint 0.
// Minden iterációban kinyerjük a szám utolsó számjegyét (modulo 10)
// és betesszük a verembe.
// Majd eltávolítjuk az utolsó számjegyet a számból (osztás 10-zel).
while (num > 0) {
digitsStack.push(num % 10); // A számjegy betétele a verembe
num /= 10; // A szám csökkentése (utolsó számjegy elhagyása)
}
// A fordított szám felépítése a verem tartalmából
// Ehhez szükségünk van az eredeti számra, de ez már megváltozott.
// Ezért tároltuk el az elején az `originalNum`-ot.
long long reversedNum = 0; // long long-ot használunk, hogy elkerüljük az esetleges túlcsordulást
// nagy számok esetén, amikor a fordított szám épül.
long long powerOfTen = 1; // Ezt a változót használtuk volna, ha tudnánk, hány számjegyből áll a szám,
// és elölről kezdenénk építeni.
// De itt egyszerűen 0-ról indulva szorozzuk 10-zel és hozzáadjuk a számjegyet.
// A verem LIFO (Last-In, First-Out) tulajdonsága miatt
// a verem tetején lévő számjegy az utolsó volt, amit beraktunk.
// Amikor kivesszük a számjegyeket, fordított sorrendben kapjuk meg őket,
// mint ahogyan az eredeti számban voltak elhelyezkedve (elölről hátra haladva).
// Ebből építjük fel a fordított számot.
while (!digitsStack.empty()) {
reversedNum = reversedNum * 10 + digitsStack.top(); // Hozzáadjuk a számjegyet a fordított számhoz
digitsStack.pop(); // Eltávolítjuk a számjegyet a veremből
}
// Végül összehasonlítjuk az eredeti és a fordított számot
return originalNum == reversedNum;
}
int main() {
std::cout << "Kérjük, adjon meg egy egész számot: ";
int inputNum;
std::cin >> inputNum;
if (isPalindromeStack(inputNum)) {
std::cout << inputNum << " egy tükörszám! ✅" << std::endl;
} else {
std::cout << inputNum << " NEM tükörszám. ❌" << std::endl;
}
// Teszt esetek futtatása:
std::cout << "nTeszt esetek:n";
std::cout << "121: " << (isPalindromeStack(121) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // IGAZ
std::cout << "123: " << (isPalindromeStack(123) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // HAMIS
std::cout << "7: " << (isPalindromeStack(7) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // IGAZ
std::cout << "0: " << (isPalindromeStack(0) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // IGAZ
std::cout << "5445: " << (isPalindromeStack(5445) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // IGAZ
std::cout << "-121: " << (isPalindromeStack(-121) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // HAMIS
std::cout << "10: " << (isPalindromeStack(10) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // HAMIS
std::cout << "2147483647 (max int): " << (isPalindromeStack(2147483647) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // HAMIS
std::cout << "2147447412 (valószínűleg nem): " << (isPalindromeStack(2147447412) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // HAMIS
std::cout << "2147474712 (valószínűleg nem): " << (isPalindromeStack(2147474712) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // HAMIS
std::cout << "123454321: " << (isPalindromeStack(123454321) ? "IGAZ ✅" : "HAMIS ❌") << std::endl; // IGAZ
Alternatív Megoldások Rövid Áttekintése 💡
Természetesen léteznek más módszerek is egy szám palindróma voltának ellenőrzésére:
* Matematikai fordítás: Ennél a megközelítésnél nem használunk extra adatstruktúrát, hanem tisztán matematikai műveletekkel (modulo és osztás) fordítjuk meg a számot, majd hasonlítjuk össze az eredetivel. Ez általában a leggyorsabb és memória szempontjából leggazdaságosabb megoldás.
* String konverzió: A számot átalakíthatjuk stringgé, majd ellenőrizhetjük, hogy a string megegyezik-e a fordítottjával. Ez kényelmes, de erőforrásigényesebb lehet, főleg nagy számok esetén, mivel a string konverzió és manipuláció plusz költséggel jár.
A verem alapú megközelítés azonban kiválóan szemlélteti az adatstruktúrák erejét és azt, hogy hogyan lehet egy elméleti koncepciót (LIFO) gyakorlati problémák megoldására alkalmazni. Különösen hasznos lehet, ha a számjegyek már eleve valamilyen veremhez hasonló struktúrában vannak tárolva, vagy ha oktatási célból szeretnénk bemutatni a verem működését.
Teljesítmény és Komplexitás – Egy Érdekesség ⚙️
Ha a verem alapú megoldás teljesítményét vizsgáljuk, két kulcsfontosságú metrikát érdemes figyelembe venni: az idő- és a térkomplexitást (Big O jelölés).
* Időkomplexitás (Time Complexity): A számjegyek kinyeréséhez és verembe helyezéséhez, majd a veremből való kivételéhez és a fordított szám felépítéséhez annyi műveletre van szükség, ahány számjegyből áll a szám. Egy `N` értékű számjegyek száma logaritmikusan növekszik az `N` értékével (pontosabban `log10(N)`). Tehát az időkomplexitás O(log N), ami rendkívül hatékony. Ezt a valós adatokra alapozott megállapítást azért tartom fontosnak kiemelni, mert bár a matematikai módszer is hasonlóan hatékony, a veremhasználat extra lépéseket igényel, de az algoritmikus növekedés szempontjából hasonlóan skálázódik.
* Térkomplexitás (Space Complexity): A veremben tárolnunk kell a számjegyeket. A verem mérete szintén a számjegyek számával arányos, tehát a térkomplexitás is O(log N). Ez a matematikai módszerhez képest extra memóriaigényt jelent, hiszen az nem használ kiegészítő adatstruktúrát.
„A programozásban sokszor nem a legközvetlenebb út a legszebb, hanem az, amelyik a legtöbb tudást adja, és elegánsan ötvözi az elméletet a gyakorlattal. A verem alapú tükörszám-ellenőrzés pontosan ilyen: nem csak megoldja a problémát, hanem elmélyíti az adatstruktúrák megértését.”
Mikor érdemes a vermet választani?
Ahogyan a fentiekben láttuk, van gyorsabb és memóriatakarékosabb megoldás is. Akkor mégis miért foglalkozunk a veremmel?
1. Oktatási cél: Kiválóan szemlélteti a verem működését és LIFO elvét. Ez egy klasszikus feladat, amit gyakran használnak az adatstruktúrák tanításakor.
2. Konceptuális tisztaság: Néha a verem használata érthetőbbé teszi a logikát, különösen, ha valaki most ismerkedik az adatstruktúrákkal. A „számjegyek sorrendjének megfordítása” feladat vizuálisan is jól értelmezhető a verem segítségével.
3. Kiegészítő funkciók: Ha a feladat része az is, hogy a számjegyekkel más műveleteket is végezzünk a fordítás során (például ellenőrizzük, hogy minden számjegy páros-e), a verem átmeneti tárolóként is jól funkcionálhat.
Gyakorlati tippek és Edge esetek kezelése 💡
* Negatív számok: Ahogy a példakódban is látható, a negatív számokat általában nem tekintjük tükörszámnak, mivel a mínusz előjel megszakítja a szimmetriát. A függvényünk `false` értéket ad vissza rájuk.
* Nulla: A nulla (0) egyjegyű szám, és önmagával megegyezik visszafelé olvasva is, tehát tükörszám.
* Egyjegyű számok: Minden egyjegyű pozitív szám (1-9) tükörszám. A logikánk ezekre is helyesen működik.
* Túlcsordulás: Nagy bemeneti számok esetén a fordított szám (pl. `123456789` fordítva `987654321`) meghaladhatja egy `int` típus tárolási kapacitását. Ezért kritikus, hogy a `reversedNum` változó `long long` típusú legyen, hogy elkerüljük az adatvesztést és a hibás eredményeket.
Összefoglalás ✅
A számok tükörszám-e vizsgálata egy rendkívül hasznos és tanulságos feladat, amely bevezeti az embert a programozás alapvető logikai gondolkodásmódjába és az adatstruktúrák praktikus alkalmazásába. A verem használata ebben a kontextusban nem feltétlenül a leggyorsabb vagy a legmemóriatakarékosabb módszer, de vitathatatlanul az egyik legáttekinthetőbb és oktatási szempontból legértékesebb. Lehetővé teszi, hogy mélyebben megértsük a LIFO elvet, és azt, hogyan használható a sorrendiség megfordítására, ami számos más programozási feladatban is kulcsfontosságú. Ahogy a C++-ban is láttuk, néhány sornyi kóddal elegánsan és érthetően oldhatjuk meg ezt a problémát, miközben értékes tudásra teszünk szert az algoritmikus gondolkodás és az adatstruktúrák világában. Ez a megközelítés nem csupán egy megoldás, hanem egy eszköz is a programozói képességeink fejlesztésére.
