#178Programare

Sortarea numerelor după cifra de control

Enunț

Se citesc de la tastatură un număr n (n ≤ 10000) și apoi n numere naturale de maximum patru cifre. Să se afișeze numerele sortate crescător după cifra de control. Dacă două numere au aceeași cifră de control, ele se vor sorta crescător după valoare.

Cifra de control a unui număr este cifra obținută prin însumări repetate ale cifrelor sale — cifra de control a numărului 1999 este 1.

Pentru n = 7 și numerele 23 2001 9 78 2732 1001 19 se va afișa:

19 1001 2001 23 2732 78 9

Rezolvare

C++

#include <iostream>
using namespace std;

int v[10005], cc[10005];                    // valorile si cifrele lor de control

int cifraDeControl(int x) {
    while (x > 9) {                         // cat timp are mai mult de o cifra
        int sum = 0;
        while (x > 0) { sum += x % 10; x /= 10; }
        x = sum;                            // se reia pe suma obtinuta
    }
    return x;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        cc[i] = cifraDeControl(v[i]);
    }

    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (cc[j] < cc[i] || (cc[j] == cc[i] && v[j] < v[i])) {
                int t = v[i]; v[i] = v[j]; v[j] = t;
                t = cc[i]; cc[i] = cc[j]; cc[j] = t;
            }

    for (int i = 0; i < n; i++) cout << v[i] << " ";
    cout << "\n";
    return 0;
}

Cum funcționează

Problema adaugă două lucruri față de sortarea după suma cifrelor: o cheie care se calculează repetat, și un criteriu secundar la egalitate.

Cifra de control (numită și rădăcină digitală) se obține însumând cifrele până rămâne una singură. Pentru 1999: 1+9+9+9 = 28, apoi 2+8 = 10, apoi 1+0 = 1. Deci bucla exterioară rulează cât timp numărul are mai mult de o cifră, adică x > 9.

Verificare pe exemplu:

Număr	Însumări	Cifră de control
19	1+9 = 10 → 1+0	1
1001	1+0+0+1	2
2001	2+0+0+1	3
23	2+3	5
2732	2+7+3+2 = 14 → 1+4	5
78	7+8 = 15 → 1+5	6
9	—	9

23 și 2732 au amândouă cifra de control 5, deci se departajează după valoare: 23 înaintea lui 2732. Exact ce arată modelul.

Criteriul dublu se scrie într-o singură condiție:

cc[j] < cc[i]  ||  (cc[j] == cc[i] && v[j] < v[i])

Se citește: interschimbă dacă al doilea are cheia mai mică, sau dacă au chei egale și valoarea e mai mică. Paranteza e obligatorie — fără ea, && se evaluează înaintea lui || în alt mod decât intenționezi și condiția devine greșită pentru jumătate din cazuri.

Scurtătură matematică, utilă de știut: cifra de control a unui număr x > 0 este 1 + (x - 1) % 9. Rezultatul e identic, într-o singură operație. Merită menționată la examen ca observație, dar scrie bucla — ea arată că ai înțeles definiția, iar formula fără explicație pare copiată.

Greșeli frecvente

while (x >= 9) — pentru x = 9 bucla rulează la nesfârșit, pentru că suma cifrelor lui 9 e tot 9. Condiția corectă e x > 9.
O singură însumare, fără bucla exterioară — pentru 1999 obții 28 în loc de 1. Trece pe numerele mici și cade pe cele de patru cifre.
Lipsa parantezelor la condiția dublă — precedența operatorilor schimbă sensul.
Criteriul secundar aplicat pe cheie în loc de valoare — la egalitate de cifre de control, compari tot cifrele de control, deci ordinea rămâne arbitrară.

Apariții

Galati 2026 — problema 18 · sursa oficială