Cifra maximă și bazele de numerație

Legătura dintre cifra maximă și baza de numerație

Un număr poate fi considerat scris în baza b dacă toate cifrele lui sunt din intervalul [0, b−1]. Pentru verificarea acestei condiții este suficientă cifra cea mai mare a numărului. Dacă cifra maximă nu depășește b−1, atunci nici celelalte nu o depășesc, deci numărul poate fi considerat scris în baza b.

Condiția de apartenență la baza b devine astfel cMax(n) ≤ b − 1. Rezultă că, dacă un număr poate fi considerat scris în baza b, atunci poate fi considerat scris și în orice bază mai mare. Numărul 100, de pildă, are cifra maximă 1 și intră în numărătoarea tuturor bazelor, de la 2 la 10.

Descrierea algoritmului în limbaj natural

Numerele nu se memorează. Se folosește un vector de frecvență cu zece poziții, numerotate de la 0 la 9, în care poziția c reține câte numere din șir au cifra maximă egală cu c.

Se citesc numerele din fișier unul câte unul, până la epuizarea lui. Pentru fiecare număr citit se determină cifra maximă, prin apelul subprogramului cMax, și se mărește cu 1 elementul de pe poziția corespunzătoare din vectorul de frecvență.

După citirea întregului șir se parcurg bazele, de la 2 la 10. Pentru baza b, numărul valorilor care pot fi considerate scrise în ea este numărul valorilor cu cifra maximă cel mult b−1, adică suma primelor b elemente din vectorul de frecvență. Fiindcă bazele se parcurg în ordine crescătoare, această sumă nu se recalculează de fiecare dată: se pornește de la numărul valorilor cu cifra maximă 0 și, la fiecare bază nouă, se adaugă numărul valorilor cu cifra maximă b−1.

Se afișează cele nouă valori obținute, separate prin câte un spațiu.

Programul

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

ifstream f("def2020.in");

/* Intoarce cifra maxima din scrierea lui n. Instructiunea do…while
   trateaza corect si cazul n = 0, pentru care raspunsul este 0. */
int cMax(int n) {
    int maxim = 0, c;
    do {
        c = n % 10;
        if (c > maxim)
            maxim = c;
        n = n / 10;
    } while (n != 0);
    return maxim;
}

int main() {
    int cate[10] = {0};
    int x;

    while (f >> x)
        cate[cMax(x)]++;

    f.close();

    /* In baza 2 intra numerele cu cifra maxima 0 sau 1; pentru fiecare baza
       urmatoare se adauga numerele cu cifra maxima egala cu b-1. */
    int total = cate[0];
    for (int b = 2; b <= 10; b++) {
        total = total + cate[b - 1];
        cout << total << " ";
    }

    return 0;
}