Cifra de control a unui număr

Cum se obține cifra de control

Cifra de control se calculează prin aplicarea repetată a aceleiași operații, adunarea cifrelor, până când rezultatul are o singură cifră. Subprogramul cerut face un singur pas al acestui proces, așa că el se apelează în mod repetat, cât timp valoarea obținută este mai mare decât 9.

Pentru 8997899: prima sumă este 59, care are două cifre, deci se reia; a doua sumă este 14, tot cu două cifre; a treia sumă este 5, formată dintr-o singură cifră, deci acesta este rezultatul.

Un număr care are de la început o singură cifră este propria lui cifră de control. Condiția n > 9 este falsă de la început, deci structura repetitivă nu se execută, iar numărul rămâne nemodificat. Cazul apare în exemplul din enunț, la termenul 7.

Cifra de control are valori între 0 și 9. Valoarea 0 se obține numai pentru numărul 0, așa că pentru șirul din fișier, format din numere de cel puțin două cifre, cea mai mică valoare posibilă este 1.

Descrierea algoritmului în limbaj natural

Numerele nu se memorează. Se citesc din fișier unul câte unul, iar pentru fiecare se determină cifra de control: se aplică subprogramul suma numărului, apoi rezultatului obținut, și tot așa, cât timp rezultatul este mai mare decât 9.

Se folosesc două variabile: una pentru cea mai mică cifră de control întâlnită până în acel moment și una pentru numărul termenilor care o au. Pentru primul termen citit, cifra lui de control devine minimul, iar numărătoarea pornește de la 1. Pentru fiecare termen următor se compară cifra lui de control cu minimul curent:

• dacă este mai mică, ea devine noul minim, iar numărătoarea repornește de la 1;
• dacă este egală, se mărește numărul termenilor;
• dacă este mai mare, termenul se ignoră.

Fiindcă numărătoarea repornește odată cu găsirea unui minim nou, la sfârșitul parcurgerii cele două variabile conțin exact cea mai mică cifră de control și numărul termenilor care o au, oricâte schimbări de minim ar fi avut loc pe parcurs.

La sfârșit se afișează cele două valori, separate printr-un spațiu.

Programul

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

ifstream f("def2023.in");

/* Suma cifrelor lui n — un singur pas al calculului cifrei de control. */
int suma(int n) {
    int s = 0;
    do {
        s = s + n % 10;
        n = n / 10;
    } while (n != 0);
    return s;
}

/* Aplica repetat subprogramul, pana ramane o singura cifra. */
int cifraDeControl(int n) {
    while (n > 9)
        n = suma(n);
    return n;
}

int main() {
    int x, minim = 10, cate = 0;

    while (f >> x) {
        int c = cifraDeControl(x);

        if (c < minim) {
            minim = c;
            cate = 1;
        } else if (c == minim)
            cate++;
    }

    f.close();

    cout << minim << " " << cate;

    return 0;
}