Question

Buna!
Cu ajutorul acestui algoritm aflu cate zerouri sunt la sfarsitul lui n!. Care este matematica din spatele acestui algoritm?
int nz(int m)
{
int s = 0, p = 5;
while(p <= m)
{
s = s + m / p;
p = p * 5;
}
return s;
}

Multumesc!

Answer 1

$n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot n$

Deoarece $10 = 2 \cdot 5$, avem $\textrm{numarul de zerouri de la sfarsitul lui n!} = min(\textrm{Exponentul lui 5}, \textrm{Exponentul lui 2})$.

Deoarece exponentul lui 2 este mai mare decat exponentul lui 5 in n!(pentru ca in intervalul [1,n] sunt mai multi multiplii de 2 decat de 5), numarul de zerouri este egal cu exponentul lui 5 in n!

Acum, trebuie sa aflam exponentul lui 5 in n!

$n! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10 \cdot ... \cdot n$

In acest produs, sunt (n div 5) multiplii ai lui 5, ii putem aduna la s.

Acum si pentru $(n \: div \: 5)!$

$(n \: div \: 5)! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot \cdots \cdot (n \: div \: 5)$

(1 vine de la 5, 2 de la 10, 3 de la 15, 4 de la 20, 5 de la 25, 6 de la 30 s.a.m.d.), si de aici la suma se mai aduna (n div 5) div 5 = n div 25 pentru $5^2$(trebuie sa adunam 1 + 1, dar pentru $5^1$ i-am adunat la inceput)

Apoi in

$(n \: div \: 25)! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdots (n \: div \: 25)$

De unde mai adunam (n div 25) div 5 = n div 125 la suma pentru $5^3$(trebuie sa adunam 1 + 1 + 1, dar pentru $5^2$ si $5^1$ i-am adunat deja)

...

In final, exponentul lui 5 in n! se poate scrie

$\displaystyle n \: div \: 5 + n \: div \: 25 + n \: div \: 125 + n \: div \: 625 + \cdots = \sum_{k=1}^{\infty} n \: div \: (5^k)$.

Nu se considera puterile lui 5 mai mari decat n, deci un algoritm posibil pentru determinarea numarului de zerouri de la sfarsitul lui n! este cel dat de tine.