Număr palindrom

Un număr nenegativ este palindrom dacă șirul cifrelor sale se citește la fel în ambele sensuri: 121 și 7 sunt exemple, 123 nu. O metodă este să construiești numărul cu cifrele în ordine inversă și să-l compari cu valoarea inițială. Pentru 120, inversul numeric este 21, deci numărul nu este palindrom.

Oglinditul unui număr

Ultima cifră a lui n este n % 10, iar n / 10 o elimină. Dacă iei cifrele lui n de la dreapta la stânga și le adaugi, pe rând, la dreapta unui număr nou, cu inv * 10 + cifra, obții cifrele în ordine inversă. Pentru n = 5281: inv trece prin 1, 18, 182, 1825.

citește n (număr natural)
m ← n; inv ← 0
┌cât timp m > 0 execută
│  inv ← inv * 10 + m % 10
│  m ← [m / 10]
└■
┌dacă inv = n atunci
│  scrie "DA"
│altfel
│  scrie "NU"
└■

Algoritmul lucrează pe copia m, pentru că la final trebuie să compare oglinditul cu valoarea inițială a lui n.

Zerourile de la final

Oglinditul lui 52810 este 1825, nu 01825: zeroul de la final ar deveni cifră de început, iar un număr nu începe cu 0. Din același motiv, un număr nenul terminat în 0 nu poate fi palindrom. Algoritmul de mai sus tratează corect cazul: 10 are oglinditul 1, diferit de 10.

Depășirea tipului int

Oglinditul poate fi mai mare decât numărul, chiar dacă numărul încape în int. Pentru 1000000009, oglinditul este 9000000001, peste valoarea maximă a tipului int (2147483647). Dacă datele pot avea 10 cifre, declari oglinditul long long. Altă soluție este să oglindești doar jumătate din număr: muți cifre din n în inv până când inv ≥ n, apoi compari n cu inv (număr par de cifre) sau n cu inv / 10 (număr impar de cifre). Exemplul 5 folosește această variantă.

Cuvinte palindrom

Pentru un șir de caractere s cu L litere, compari prima literă cu ultima, a doua cu penultima și așa mai departe, până la mijloc. Dacă o pereche diferă, cuvântul nu e palindrom. În programa veche, șirurile de caractere sunt la clasa a XI-a; funcțiile pentru ele sunt în capitolul Șiruri de caractere.

În Python (clasa a IX-a, programa nouă)

Programa nouă cere operațiile cu cifrele unui număr, în Python. Oglinditul se calculează la fel, cu // pentru câtul împărțirii:

def oglindit(n):
    inv = 0
    while n > 0:
        inv = inv * 10 + n % 10
        n = n // 10
    return inv

for n in [12321, 52810, 7]:
    print(n, oglindit(n), oglindit(n) == n)

12321 12321 True
52810 1825 False
7 7 True

Un exemplu cu do…while

#include <iostream>
using namespace std;
int main() {
    long long initial, n, invers = 0;
    cin >> initial;
    n = initial;
    do {
        invers = invers * 10 + n % 10;
        n /= 10;
    } while (n > 0);
    cout << (invers == initial);
    return 0;
}

Pentru intrarea 12321 programul afișează 1, iar pentru 120 afișează 0: inversul numeric al lui 120 este 21, pentru că zeroul final devine zero inițial și nu mai contează.

Exemplul 2 — palindroamele dintr-un interval. Pentru intervalul $[100;140]$ se aplică testul fiecărui număr.

1. Pentru fiecare $x$ din interval se copiază $x$ în n și se construiește invers.
2. Dacă invers == x, numărul se afișează și se crește un contor.
3. La final, contorul este numărul de palindroame ale intervalului.

În $[100;140]$ palindroamele sunt 101, 111, 121 și 131, deci contorul este 4. Un număr de trei cifre $abc$ este palindrom dacă $a=c$, iar cifrele $a$, $b$ pot fi alese în $9\cdot 10=90$ de moduri între 100 și 999. Cifrele de la capete se compară mai economic pe un șir, dar pentru numere memorate ca întregi metoda inversului este cea standard.

Varianta cu șir de caractere (Python). Când numărul poate avea multe cifre, îl transformi în text și compari fiecare caracter cu cel simetric:

t = input().strip()
ok = True
for i in range(len(t) // 2):
    if t[i] != t[len(t) - 1 - i]:
        ok = False
        break
print(ok)

Pentru 12321 se compară perechile (1, 1) și (2, 2); cifra din mijloc nu are pereche, iar programul afișează True. Pentru 1231 prima pereche (1, 1) coincide, a doua (2, 3) nu, iar programul se oprește și afișează False.

Timpul pentru un număr cu $d$ cifre este proporțional cu $d$, iar memoria auxiliară este constantă. Numerele negative nu se tratează aici ca palindroame decât dacă enunțul le definește prin modul.

Exemplul 3 — urmărirea pentru 1231. La început invers = 0 și n = 1231. După primul pas, invers = 0·10 + 1 = 1 și n = 123. După al doilea, invers = 1·10 + 3 = 13 și n = 12. După al treilea, invers = 13·10 + 2 = 132 și n = 1. După al patrulea, invers = 132·10 + 1 = 1321 și n = 0, deci bucla se oprește. Cum $1321\ne 1231$, numărul nu este palindrom.

Câte palindroame există. Un palindrom cu 4 cifre are forma $abba$, cu $a\in \{1,\dots ,9\}$ și $b\in \{0,\dots ,9\}$, deci sunt $9\cdot 10=90$ de astfel de numere. Unul cu 5 cifre are forma $abcba$, deci sunt $9\cdot 10\cdot 10=900$. Numărul de palindroame depinde doar de jumătatea din față a cifrelor.

Exemple rezolvate

Exemplul 1: oglinditul și verificarea

Verifică dacă 12321 și 52810 sunt palindroame.

1. Pentru 12321, oglinditul trece prin 1, 12, 123, 1232, 12321 și este egal cu numărul: DA.
2. Pentru 52810, oglinditul este 1825, diferit de 52810: NU.

#include <iostream>
using namespace std;

int main() {
    long long n, m, inv = 0;
    cin >> n;
    m = n;
    while (m > 0) {
        inv = inv * 10 + m % 10;
        m = m / 10;
    }
    if (inv == n)
        cout << "DA\n";
    else
        cout << "NU\n";
    return 0;
}

Pentru intrarea 12321, programul afișează:

DA

Pentru 52810 afișează NU. Variabilele sunt long long, ca programul să funcționeze și pentru numere de 10 cifre.

Exemplul 2: câte palindroame sunt până la 1000

1. Palindroamele de o cifră sunt 1, …, 9: 9 numere.
2. Cele de două cifre au forma aa: 11, 22, …, 99: 9 numere.
3. Cele de trei cifre au forma aba: 9 · 10 = 90 de numere. 1000 nu este palindrom.
4. Total: 9 + 9 + 90 = 108.

#include <iostream>
using namespace std;

int oglindit(int n) {
    int inv = 0;
    while (n > 0) {
        inv = inv * 10 + n % 10;
        n = n / 10;
    }
    return inv;
}

int main() {
    int nr = 0;
    for (int x = 1; x <= 1000; x++)
        if (oglindit(x) == x)
            nr++;
    cout << nr << "\n";
    return 0;
}

Programul afișează:

108

Exemplul 3: un cuvânt palindrom

Se citește un cuvânt cu cel mult 100 de litere mici. Afișează DA dacă este palindrom și NU în caz contrar. „capac”, „cojoc” și „potop” sunt palindroame; „capace” nu este.

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char s[101];
    cin >> s;
    int L = strlen(s), ok = 1;
    for (int i = 0; i < L / 2; i++)
        if (s[i] != s[L - 1 - i])
            ok = 0;              // o pereche diferita ajunge
    if (ok == 1)
        cout << "DA\n";
    else
        cout << "NU\n";
    return 0;
}

Pentru intrarea capac, programul afișează:

DA

Pentru capace, prima pereche este „c” și „e”, deci afișează NU. La un cuvânt cu număr impar de litere, litera din mijloc nu se compară cu nimic, de aceea bucla merge până la L / 2 − 1.

Exemplul 4: cel mai mic palindrom mai mare decât n

Se citește n. Afișează cel mai mic număr palindrom strict mai mare decât n.

1. Încerci, pe rând, n + 1, n + 2, … și te oprești la primul palindrom.
2. Pentru 12345 se obține 12421; pentru 999, 1001; pentru 808, 818 (nu 808, pentru că se cere un număr strict mai mare).

#include <iostream>
using namespace std;

long long oglindit(long long n) {
    long long inv = 0;
    while (n > 0) {
        inv = inv * 10 + n % 10;
        n = n / 10;
    }
    return inv;
}

int main() {
    long long n;
    cin >> n;
    long long x = n + 1;
    while (oglindit(x) != x)
        x++;
    cout << x << "\n";
    return 0;
}

Pentru intrarea 12345, programul afișează:

12421

Exemplul 5: nivel de examen, palindroame divizibile cu 11

Scrie subprogramul palindrom, care primește prin parametrul n un număr natural și returnează 1 dacă n este palindrom, altfel 0, oglindind doar jumătate din cifre. Folosește-l ca să afli câte numere de la 1 la 10000 sunt palindroame divizibile cu 11.

1. Un număr nenul terminat în 0 nu e palindrom, deci subprogramul îl respinge din start.
2. Mută cifre din n în inv cât timp n > inv. La final, n are fie aceleași cifre ca inv (număr par de cifre), fie o cifră în plus, cea din mijloc, care ajunge la sfârșitul lui inv și se elimină cu inv / 10.
3. Orice palindrom cu număr par de cifre este divizibil cu 11, pentru că suma alternată a cifrelor lui este 0: toate cele 9 palindroame de două cifre și toate cele 90 de patru cifre. Dintre cele de trei cifre, aba, se divid cu 11 doar cele cu 2a − b divizibil cu 11: 121, 242, 363, 484, 616, 737, 858, 979. Total: 9 + 8 + 90 = 107.

#include <iostream>
using namespace std;

int palindrom(int n) {
    if (n % 10 == 0 && n != 0)
        return 0;
    int inv = 0;
    while (n > inv) {
        inv = inv * 10 + n % 10;
        n = n / 10;
    }
    return n == inv || n == inv / 10;
}

int main() {
    int nr = 0;
    for (int x = 1; x <= 10000; x++)
        if (x % 11 == 0 && palindrom(x))
            nr++;
    cout << nr << "\n";
    return 0;
}

Programul afișează:

107

Varianta cu jumătate de oglindit nu depășește niciodată valoarea lui n, deci funcționează în int pentru orice n de tip int.

Fragmentele de palindrom cer atenție la trei locuri: variabila cu care se compară, inițializarea inversului și tipul lui. Compararea inversului cu n după buclă este greșită, deoarece n a ajuns 0. Dacă invers nu este inițializat cu 0, rezultatul este nedefinit. Același test poate fi folosit într-un ciclu pe un interval: la fiecare număr copiezi valoarea înainte de a o consuma. Numerele terminate în 0 (precum 120 sau 100) nu sunt palindroame, pentru că un număr întreg nu are zerouri în față.

Exemplu în formatul examenului. Câte numere din intervalul $[10;40]$ fac ca secvența de mai jos să afișeze 1 pentru valoarea citită în x?

int x, n, invers = 0;
cin >> x;
n = x;
while (n > 0) {
    invers = invers * 10 + n % 10;
    n /= 10;
}
cout << (invers == x);

• a) 3
• b) 4
• c) 9
• d) 31

Răspunsul corect este a). Secvența afișează 1 exact pentru palindroame. În $[10;40]$ palindroamele sunt 11, 22 și 33, adică trei numere. Numerele 10, 20, 30 și 40 au inversul 1, 2, 3 și 4, deci nu sunt palindroame. Varianta d) ar rezulta dacă s-ar număra toate cele 31 de valori din interval. Varianta c) numără cifrele 1–9, care sunt palindroame, dar nu aparțin intervalului $[10;40]$.

Al doilea exemplu: suma palindroamelor. Ce valoare are s la sfârșitul secvenței, dacă testul de palindrom este cel de mai sus?

int s = 0;
for (int x = 1; x <= 30; ++x) {
    int n = x, invers = 0;
    while (n > 0) { invers = invers * 10 + n % 10; n /= 10; }
    if (invers == x) s += x;
}
cout << s;

Cifrele de la 1 la 9 sunt palindroame, cu suma $1+2+\cdots +9=45$. Dintre numerele de două cifre, între 10 și 30 sunt palindroame doar 11 și 22, iar 33 depășește limita. Rezultatul este $45+11+22=78$.

Unde apare la examen

• Bacalaureatul, informatică, matematică-informatică: programa de examen cuprinde „Probleme care operează asupra cifrelor unui număr”, la algoritmii elementari, și tipul șir de caractere, la tipurile structurate de date (programa de examen, anexa 2 la OMECTS 4800/2010). La sesiunea din iunie–iulie 2026, primul subprogram de la Subiectul al III-lea a construit un număr nou din cifrele altuia, cu aceleași operații ca oglinditul, iar programul următor a verificat o proprietate a literelor de pe poziții consecutive dintr-un cuvânt (subiectele și baremele Bac 2026). Formatul descris este cel din 2026; potrivit proiectului de ordin pentru Bacalaureatul 2027, programa rămâne aceeași.
• Programa școlară: programa veche de clasa a IX-a dă testarea proprietății de palindrom ca exemplu de prelucrare a cifrelor unui număr (programa de clasa a IX-a, OMECI 5099/2009); șirurile de caractere sunt în programa veche de clasa a XI-a (programa de clasa a XI-a).

Greșeli frecvente

• Greșit: după ce oglindești direct pe n, compari inversul cu n.
  Corect: după buclă n este 0, iar comparația inv == n dă adevărat numai pentru n = 0; oglindești o copie și compari cu valoarea inițială păstrată.
• Greșit: inv se inițializează în buclă sau nu se inițializează.
  Corect: inv pornește de la 0, înaintea buclei; inițializat în buclă, își pierde cifrele la fiecare pas.
• Greșit: inv = inv + n % 10 * 10.
  Corect: formula care construiește oglinditul este inv = inv * 10 + n % 10.
• Greșit: oglinditul unui număr de 10 cifre se ține într-un int.
  Corect: poate depăși int; folosești long long sau metoda cu jumătate de număr.
• Greșit: 120 este palindrom deoarece are cifra 2 la mijloc.
  Corect: inversul numeric este 21, diferit de 120.
• Greșit: numărul 0 are zero cifre.
  Corect: are o cifră; la numărarea cifrelor, folosești un caz separat sau do…while.
• Greșit: la cuvinte, bucla merge până la L și se compară s[L - i] cu s[i].
  Corect: bucla merge până la L / 2, iar perechea este s[i] cu s[L - 1 - i]; cu s[L - i], prima comparație se face cu terminatorul șirului și rezultatul e greșit.

Înainte și după

Întrebări frecvente