Programare Competitivă

Palindromuri

Un palindrom este un număr (sau un cuvânt) care citit de la stânga la dreapta este la fel ca citit de la dreapta la stânga.

Exemple de numere palindrom:

  • 121 → citit invers: 121 → palindrom
  • 1331 → citit invers: 1331 → palindrom
  • 7 → un singur cifră → palindrom
  • 123 → citit invers: 321 → nu este palindrom

Cum verificăm dacă un număr este palindrom?

Ideea este simplă:

Construim oglinditul (inversul) numărului și verificăm dacă este egal cu numărul original.

Dacă n == oglinditul lui n, atunci n este palindrom.

Oglinditul unui număr

Înainte de a verifica palindromuri, trebuie să știm cum inversăm un număr.

Ideea

Extragem cifrele de la dreapta la stânga (cu % 10) și le construim într-un număr nou, de la stânga la dreapta.

Exemplu pas cu pas pentru n = 345

Pas n Cifra (n % 10) oglindit
start 345 - 0
1 34 5 0 * 10 + 5 = 5
2 3 4 5 * 10 + 4 = 54
3 0 3 54 * 10 + 3 = 543

Oglinditul lui 345 este 543.

Formula la fiecare pas

oglindit = oglindit * 10 + n % 10
n = n / 10

Codul pentru oglindit

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int copie = n;
    int oglindit = 0;

    while (copie > 0) {
        oglindit = oglindit * 10 + copie % 10;
        copie = copie / 10;
    }

    cout << oglindit;

    return 0;
}
Input:
1234
Output:
4321

Important: lucrăm pe o copie a lui n, pentru că bucla distruge valoarea originală. Avem nevoie de n intact la final, pentru comparație.

Verificarea palindromului

Acum că știm să calculăm oglinditul, verificarea este directă:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int copie = n;
    int oglindit = 0;

    while (copie > 0) {
        oglindit = oglindit * 10 + copie % 10;
        copie = copie / 10;
    }

    if (n == oglindit) {
        cout << "DA";
    } else {
        cout << "NU";
    }

    return 0;
}
Input:
12321
Output:
DA
Input:
123
Output:
NU

Explicație pas cu pas pentru 12321

Pas copie Cifra oglindit
start 12321 - 0
1 1232 1 1
2 123 2 12
3 12 3 123
4 1 2 1232
5 0 1 12321

n = 12321, oglindit = 12321 → sunt egale → palindrom.

Alte exemple

Număr Oglindit Palindrom?
121 121 DA
1001 1001 DA
45 54 NU
7 7 DA
1234321 1234321 DA
100 001 = 1 NU

Observație despre 100

Oglinditul lui 100 este 001, adică 1. Și 100 != 1, deci 100 nu este palindrom.

Numerele care se termină cu 0 (în afară de 0 singur) nu pot fi palindromuri, pentru că un număr nu poate începe cu 0.

Cel mai mare palindrom cu k cifre

O întrebare interesantă: care este cel mai mare palindrom cu exact 3 cifre?

Răspunsul: 999. Dar cel mai mare palindrom cu 3 cifre care nu e format doar din 9? Este 989.

Putem verifica toate numerele de la 999 în jos:

#include <iostream>
using namespace std;

int main()
{
    for (int n = 999; n >= 100; n--) {
        int copie = n;
        int oglindit = 0;

        while (copie > 0) {
            oglindit = oglindit * 10 + copie % 10;
            copie = copie / 10;
        }

        if (n == oglindit) {
            cout << n;
            break;
        }
    }

    return 0;
}
De ce folosim break?

Instrucțiunea break oprește bucla imediat ce am găsit primul palindrom. Fără ea, programul ar continua să caute și ar afișa toate palindromurile.

Noi vrem doar primul (cel mai mare), deci ne oprim imediat.

Numărarea palindromurilor dintr-un interval

Câte palindromuri sunt între 100 și 999?

#include <iostream>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;

    int cnt = 0;

    for (int n = a; n <= b; n++) {
        int copie = n;
        int oglindit = 0;

        while (copie > 0) {
            oglindit = oglindit * 10 + copie % 10;
            copie = copie / 10;
        }

        if (n == oglindit) {
            cnt++;
        }
    }

    cout << cnt;

    return 0;
}
Input:
100 999
Output:
90

De ce 90? Palindromurile de 3 cifre au forma ABA, unde A poate fi 1-9 (9 variante) și B poate fi 0-9 (10 variante). Deci 9 × 10 = 90.

Greșeli frecvente

1. Lucrul direct pe n fără copie

while (n > 0) {
    oglindit = oglindit * 10 + n % 10;
    n = n / 10;
}
// Aici n este 0, nu mai putem compara!

Trebuie salvat n într-o copie înainte de buclă.

2. Uitarea inițializării oglinditului

// oglindit nu este inițializat cu 0
int oglindit;

Variabila oglindit trebuie să fie 0 la început, altfel conține o valoare aleatoare.

3. Confuzia cu numere negative

Numerele negative nu sunt considerate palindromuri. Dacă problema cere, adaugă o verificare la început:

if (n < 0) {
    cout << "NU";
    return 0;
}

Ce să reții

  • Un palindrom este un număr egal cu oglinditul său.
  • Oglinditul se construiește cu formula: oglindit = oglindit * 10 + n % 10.
  • Lucrează întotdeauna pe o copie a numărului.
  • Numerele care se termină cu 0 nu sunt palindromuri (exceptând 0 singur).
  • Verificarea palindromului combină descompunerea în cifre cu compararea.

Probleme

pbinfoPal1234→

pbinfoPalmax→

pbinfoPalindrom1→

Cuprins Inapoi Inainte