Subprogram BAC: numere cu cifre distincte în C++

Un subprogram de verificare a cifrelor distincte răspunde la o întrebare precisă: apare vreo cifră de cel puțin două ori în scrierea numărului? La BAC, poți construi o funcție cu rezultat logic și o poți apela pentru fiecare valoare dintr-un șir. Astfel, separi verificarea proprietății de numărarea valorilor care o respectă.

Lecția privește subprogramele definite de utilizator de la matematică-informatică. Numerele analizate sunt naturale, cel mult un miliard, iar zero este considerat un număr cu o singură cifră. După înțelegerea funcției, folosește aceeași separare a responsabilităților într-un exercițiu de BAC la informatică.

Ce înseamnă cifre distincte

Numărul o mie două sute trei are cifrele unu, doi, zero și trei, fiecare o singură dată. Proprietatea este adevărată. Numărul o mie doi are două apariții ale cifrei zero, deci proprietatea este falsă.

Nu este suficient să compari numai cifrele vecine. În numărul o sută douăzeci și unu, cifrele egale se află la capete și nu sunt alăturate. O verificare limitată la vecini ar accepta greșit acest număr.

De asemenea, ordinea crescătoare a cifrelor este o proprietate mai restrictivă. Numărul trei sute douăzeci și unu are cifre distincte, deși ele sunt descrescătoare. Funcția trebuie să testeze exact cerința, fără condiții suplimentare.

Un tablou cu zece marcaje

Există zece cifre zecimale, deci putem păstra câte un marcaj pentru fiecare. La începutul fiecărui apel, toate marcajele sunt false. Un marcaj adevărat înseamnă că cifra respectivă a fost deja întâlnită în numărul curent.

Extragem pe rând ultima cifră. Dacă marcajul ei este deja adevărat, am găsit o repetare și putem returna imediat fals. În caz contrar, activăm marcajul și continuăm cu restul numărului.

Cifră extrasă din 1203	Întâlnită înainte?	Acțiune
3	Nu	Marchează cifra 3
0	Nu	Marchează cifra 0
2	Nu	Marchează cifra 2
1	Nu	Marchează cifra 1

Ordinea extragerii nu contează pentru această proprietate. Avem nevoie de existența unei apariții anterioare, nu de poziția exactă sau de ordinea cifrelor păstrate.

Program C++: funcție logică și numărare

Programul citește numărul valorilor, apoi valorile naturale. Numărul valorilor poate fi zero. Afișează câte dintre ele au toate cifrele distincte. Funcția primește numărul prin valoare, astfel încât poate modifica copia în timpul parcurgerii.

#include <iostream>
using namespace std;

bool cifreDistincte(long long n) {
    bool vazut[10] = {};
    do {
        int cifra = int(n % 10);
        if (vazut[cifra]) return false;
        vazut[cifra] = true;
        n /= 10;
    } while (n != 0);
    return true;
}

int main() {
    int m;
    cin >> m;
    int numar = 0;
    for (int i = 0; i < m; ++i) {
        long long x;
        cin >> x;
        if (cifreDistincte(x)) ++numar;
    }
    cout << numar;
    return 0;
}

Funcția returnează adevărat numai după ce a terminat toate cifrele fără să găsească repetări. Un singur pas reușit nu este suficient pentru acest rezultat. În schimb, o singură repetare este suficientă pentru fals.

De ce marcajele se reinițializează la fiecare apel

Tabloul de marcaje descrie un singur număr. Dacă ai păstra marcajele de la valoarea anterioară, o cifră întâlnită într-un alt număr ar putea fi confundată cu o repetare în numărul curent.

Pentru valorile doisprezece și douăzeci și trei, ambele au cifre distincte. Cifra doi apare în ambele numere, dar aceasta nu încalcă proprietatea cerută. Verificăm repetările în interiorul fiecărei valori, nu în întregul șir.

Inițializarea locală a tabloului face contractul funcției mai clar: rezultatul depinde numai de argumentul primit. Nu depinde de numerele analizate anterior sau de ordinea apelurilor din programul principal.

Zero și zerourile din interior

Pentru numărul zero, bucla se execută o dată, marchează cifra zero și returnează adevărat. Există o singură cifră, deci nu poate exista repetare. Un test care ar sări complet peste zero ar putea obține același rezultat, dar nu ar reflecta explicit reprezentarea sa.

În numărul o sută, cifra zero este extrasă de două ori. A doua apariție produce imediat fals. Cifra unu nu mai trebuie analizată pentru a decide proprietatea, deoarece repetarea deja găsită nu poate fi anulată.

Zerourile inițiale nu sunt păstrate într-o valoare numerică obișnuită. Dacă datele sunt coduri precum zero, zero, unu, doi și se cere analiza tuturor simbolurilor, trebuie citite ca text. Funcția pentru numere nu distinge acel cod de numărul doisprezece.

Locul corect pentru returnare

O greșeală frecventă este returnarea lui adevărat imediat după prima cifră care nu a mai fost văzută. Prima cifră este întotdeauna nouă într-un tablou proaspăt inițializat, deci funcția ar accepta aproape orice număr fără să termine verificarea.

Pentru o proprietate care cere ca toate elementele să respecte o regulă, succesul se confirmă după parcurgerea completă. Eșecul poate fi confirmat la primul contraexemplu. Această asimetrie este utilă în multe funcții de verificare.

Dacă proprietatea ar cere existența unei cifre pare, situația s-ar inversa: o singură cifră pară ar confirma succesul, iar lipsa ei s-ar confirma numai la final. Formulează cerința cu „toate” sau „există” înainte să alegi locul returnării.

Numărarea rezultatelor în programul principal

Programul principal nu trebuie să cunoască detaliile tabloului de marcaje. El apelează funcția și incrementează contorul dacă rezultatul este adevărat. Aceasta permite verificarea separată a celor două componente.

Pentru valorile zero, o sută douăzeci și trei, o sută douăzeci și unu, o mie doi și nouăzeci și opt, sunt acceptate zero, o sută douăzeci și trei și nouăzeci și opt. Rezultatul afișat este trei.

Dacă enunțul cere afișarea valorilor acceptate în locul numărării lor, funcția de verificare poate rămâne aceeași. Se schimbă acțiunea din programul principal. Separarea aceasta ajută la înțelegerea și reutilizarea algoritmilor.

Eficiență și teste

Funcția analizează cel mult toate cifrele numărului și poate opri mai devreme la o repetare. Tabloul are zece poziții, indiferent de valoarea argumentului. Memoria auxiliară este constantă.

Pentru un șir, timpul total depinde de suma numerelor de cifre ale valorilor analizate. Nu memorăm întregul șir, deoarece fiecare valoare este verificată imediat după citire și contribuie doar la contorul final.

Testează o repetare la începutul extragerii, o repetare descoperită târziu, un număr cu cifre distincte în ordine descrescătoare și două apeluri consecutive care folosesc aceeași cifră. Aceste cazuri verifică atât logica, cât și izolarea stării locale.

Exerciții cu răspunsuri

Numărul este 987654320. Cifrele sunt distincte, inclusiv zero. Ordinea descrescătoare nu este o problemă.

Numărul este 1021. Cifra unu se repetă, deci rezultatul este fals, chiar dacă cifrele egale nu sunt vecine.

Șirul conține valorile 12, 23 și 34. Toate trei sunt acceptate. Repetarea unei cifre între numere diferite nu contează.

Întrebări frecvente

Este suficientă suma cifrelor?

Nu. Suma pierde informația despre aparițiile individuale. Numere diferite, cu sau fără repetări, pot avea aceeași sumă a cifrelor.

Pot folosi frecvențe întregi în loc de marcaje?

Da. Ai incrementa frecvența și ai respinge când aceasta depășește unu. Marcajele sunt suficiente aici deoarece ai nevoie doar să știi dacă cifra a mai apărut.

Cum verific antetul cerut la BAC?

Compară numele, tipul rezultatului, parametrii și domeniul admis cu enunțul. Pentru o corectare explicată, poți discuta implementarea cu un profesor de informatică.