Articolele lui Mititelu Ana Mirela (AnaMititelu)

Cifra de control a unui număr se obține efectuând suma cifrelor sale, apoi suma cifrelor acestei sume, până când suma obținută este un număr format dintr-o singură cifră. Această ultimă cifră poartă numele de cifră de control.

Exemplu: Cifra de control \((cc)\) a numărului \(n= 4568248\):
\(cc(4568258)= cc(38)=cc(11)=2\).

Secvență de implementare C++:

while (n>9)
{
    s=0;
    while (n>0)
    {
        s+=n%10;
        n/=10;
    }
    n=s;
}

Algoritmul prezentat este intuitiv, ușor de înțeles și contribuie la dezvoltarea gândirii algoritmice.

Tot pentru calcularea cifrei de control se poate folosi și următoarea metodă: se trunchiază numărul prin eliminarea ultimei cifre apoi se adună cu aceasta până se obține un număr format dintr-o singură cifră.

Exemplu:

\(n=4568258\)
\(n=456825+8=456833\)
\(n=45683+3=45686\)
\(n=4568+6=4574\)
\(n=457+4=461\)
\(n=46+1=47\)
\(n=4+7=11\)
\(n=1+1=2\)

Secvența de implementare C++:

while(n>9)
{
    n=n/10+n%10;
}

În ambele cazuri timpul de execuție depinde de numărul de cifre ale numărului și de valorile acestora.

Pornind de la criteriul de divizibilitate cu 9, un număr se divide cu 9 dacă suma cifrelor sale este multiplu de 9 și cum cifra cea mai mare în baza 10 este 9, putem afla cifra de control calculând restul împărțirii numărului la 9. Dacă restul este 0 atunci cifra de control este 9, altfel este acel rest.

Secvența de implementare C++:

r=n%9;
if (r==0) 
    cc =  9;
else
    cc = r;

În acest caz numărul de operații elementare nu mai depinde de valoarea lui n.

Există o serie de probleme pentru care rezolvarea lor se rezumă la aflarea exponentului unui număr dat \( k, exp(k) \) , într-un produs factorial \((n!)\), fără a calcula acel produs.

O metodă naivă ar fi căutarea multiplior lui k mai mici sau egali cu n și de câte ori de divid acestia cu k.

Exemplu:

\(n=75, k=7\)
\(n!=1 * 2 * 3 * 4 * 5 * 6 * 7 * … * 14 * … * 21 * … * 28 * … * 35 * … * 42 * … * 49 * … * 56 * … * 63 * … * 70 * … * 75\)
\(n!=1 * … * 1 * 7 * … * 2 * 7 * … * 3 * 7 * … * 4 * 7 * … * 5 * 7 * … * 6 * 7 * … * 7 * 7 * … * 8 * 7 * … * 9 * 7 *… * 7 * 10 * … * 75\) \( exp(7)=11\)

O soluție ar fi parcurgerea intervalului \([k, n] \)cu pasul \(k \) și contorizarea multiplilor.

C++

exp=0
for (int i=k;i<=n;i+=k)
  {
    int x=i;
    while(x%k==0)
      {exp++;x/=k;}
  }
cout<<exp;

Termenul dominant este T(n) ->n/k (algoritm linear).

O altă soluție ar fi folosirea unei formule de calcul a exponentului lui \(k\) în \(n!\) notat \( {exp}_{n!}{\left(k\right)} \), numită formula lui Legendre.

Dacă numărul k este prim \( {exp}_{n!}{\left(k\right)}=\left[\frac{n}{k}\right]+\left[\frac{n}{k^2}\right]+\left[\frac{n}{k^3}\right]+… \)

Exemplu:\( n=75, k=7\)
\( {exp}_{75!}{\left(7\right)}=\left[\frac{75}{7}\right]+\left[\frac{75}{49}\right]+\left[\frac{75}{343}\right]=10+1+0=11 \)
Se poate deduce că după un anumit număr de pași raportul va deveni subunitar ceea ce determină că suma va avea un număr finit de termeni. Pornind de la această relație, valoarea acelui exponent se poate calcula însumând câturile împărțirilor succesive.

Implementarea C++.

exp=0
while(n>=k)
{
    n=n/k;
    exp+=n;
}

Termenul dominant este T(n) ->log(n) (algoritm logaritmic)

Dacă numărul \(k\) este un număr compus și în descompunerea în factori primi se obține produsul \( k=d_1^{e_1}\cdot d_2^{e_2}\cdot…\cdot d_l^{e_l} \) unde \( d_1, d_2,…, d_l\) sunt factorii primi iar \( e_1, e_2,…, e_l\) exponenții acestora, vom folosi relațiile matematice (1) și (2), unde:
\( {exp}_{n!}{\left(d^e\right)}=\left[\frac{{exp}_{n!}{\left(d\right)}}{e}\right] \)(1)
\( {exp}_{n!}{\left(k\right)}=min{\left\{{exp}_{n!}{\left(d_1^{e_1}\right)},{exp}_{n!}{\left(d_2^{e_2}\right)},{exp}_{n!}{\left(d_3^{e_3}\right)},…{exp}_{n!}{\left(d_l^{e_l}\right)}\right\}} \)(2)

Exemplu:
\( n=75, k=12\)
\( 12=2^2\cdot3 \)
\( {exp}_{75!}{\left(2^2\right)}=\left[\frac{{exp}_{75!}{\left(2\right)}}{2}\right]=\left(\left[\frac{75}{2}\right]+\left[\frac{75}{4}\right]+\left[\frac{75}{8}\right]+\left[\frac{75}{16}\right]+\left[\frac{75}{32}\right]+\left[\frac{75}{64}\right]+\left[\frac{75}{128}\right]\right)/2=\left(37+28+4+1+0\right)/2=35 \).
\( {exp}_{75!}{\left(3\right)}=\left[\frac{75}{3}\right]+\left[\frac{75}{9}\right]+\left[\frac{75}{27}\right]+\left[\frac{75}{81}\right]=25+8+2+0=35 \).
În concluzie,
 \( {exp}_{75!}{\left(12\right)}=min(35,35)=35 \)

Implementare C++

int a,b,divi[100],puterea[100],poz,minim;
int putere(int n,int p)
{
    int x=0;
    while(n>p)
    {
        x+=n/p;
        n=n/p;
    }
    return x;
}
int main()
{
    f>>b>>a;
    int d=2;
    while(d*d<=a)
    {
        if(a%d==0)
        {
            divi[++poz]=d;
            int c=0;
            while(a%d==0)
            {
                a/=d
                puterea[poz]++; 
            }
        }
        d++;
    }
    if(a!=1)
    {
        divi[++poz]=a;
        puterea[poz]=1;
    }
    minim=1000000;
    for(int i=1;i<=poz;i++)
    {
        puterea[i]=putere(b,divi[i])/puterea[i];
        if(minim>puterea[i])
            minim=puterea[i];
    }
    g << minim;
    return 0;
}