Page 38 - MATINF Nr.2

38 S.C. Andronescu, C. B˘alc˘au, D. Constantin, D.A. Popescu

Obt , inem astfel urm˘atorul algoritm pentru determinarea lui r(m 1 · m 2 · . . . · m n ).

UCNP(M, n) : // M = (m 1 , m 2 , . . . , m n )
a ← 0; b ← 0; c ← 1;
for k = 1, n do
p ← m k ;
while p MOD 2 = 0 do
a ← a + 1; p ← p/2;
while p MOD 5 = 0 do
b ← b + 1; p ← p/5;
c ← (c · p) MOD 10;

if a = b then
return c;
else
if a < b then
return 5;
else
for i = 1, (a − b) MOD 4 do
c ← 2 · c;
return (6 · c) MOD 10;

Propozit , ia 5. Algoritmul UCNP are complexitatea Θ(n + a(m 1 ) + b(m 1 ) + a(m 2 ) + b(m 2 ) +
. . . + a(m n ) + b(m n )).

Demonstrat¸ie. Conform Propozit , iilor 3 s , i 4, complexitatea algoritmului UCNP este

n n
! !
X X
Θ (1 + a(m i ) + b(m i )) = Θ n + (a(m i ) + b(m i ))
i=1 i=1
.

Corolarul 3. Algoritmul UCNP are complexitatea O (n + ln(m 1 · m 2 · . . . · m n )).

Demonstrat¸ie. Conform demonstrat , iei Corolarului 1 avem
n Ç å n
X 1 1 X
(a(m i ) + b(m i )) ≤ + ln m i ,
ln 2 ln 5
i=1 i=1
deci conform propozit , iei anterioare rezult˘a c˘a algoritmul UCNP are complexitatea

n n
! !
X Y
O n + ln m i = O n + ln m i .
i=1 i=1

Determinarea ultimei cifre nenule a factorialului unui num˘ar natural

ˆ
In aceast˘a sect , iune ne propunem s˘a determin˘am ultima cifr˘a nenul˘a a lui n!, adic˘a r(n!), unde n
este un num˘ar natural arbitrar. Avem nevoie de cˆateva rezultate preg˘atitoare.