Page 36 - MATINF Nr.2

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

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

UCN(m) :
p ← m; a ← 0; b ← 0;
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 ← 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 3. Algoritmul UCN are complexitatea Θ(a(m) + b(m) + 1).

Demonstrat¸ie. Conform Definit , iei 2 avem m = 2 a(m) · 5 b(m) · (M10 + c(m)), cu a(m), b(m) ∈ N
s , i c(m) ∈ {1, 3, 7, 9}. Corpul primului ciclu while din algoritmul UCN are dou˘a instruct , iuni
s , i se execut˘a de a(m) ori, corpul celui de-al doilea ciclu while are tot dou˘a instruct , iuni s , i
se execut˘a de b(m) ori, iar corpul ciclului for are o instruct , iune s , i se execut˘a de cel mult 3
ori. Algoritmul mai cont , ine 4 atribuiri s , i una sau dou˘a comparat , ii, deci are complexitatea
Θ(a(m) + b(m) + 1).

Corolarul 1. Algoritmul UCN are complexitatea O (ln m).

Demonstrat¸ie. Avem 2 a(m) ≤ m s , i 5 b(m) ≤ m, deci a(m) ≤ log m s , i b(m) ≤ log m. Obt , inem c˘a
5
2
Ä ä
a(m) + b(m) + 1 ≤ 1 + 1 ln m + 1, deci conform propozit , iei anterioare rezult˘a c˘a algoritmul
ln 2 ln 5
UCN are complexitatea O (ln m).
Observat ,ia 3. Mai mult, ˆın cazul cˆand m este o putere a lui 2, adic˘a m = 2 a(m) , avem b(m) = 0
s , i astfel a(m) + b(m) + 1 = log m + 1 = ln m + 1. Conform rezultatelor anterioare rezult˘a c˘a
2 ln 2
algoritmul UCN are timpul de execut , ie ˆın acest caz particular chiar de ordinul Θ(ln m), care
este mai precis decˆat O (ln m). Evident, acelas , i ordin se obt , ine s , i ˆın cazul cˆand m este o putere
a lui 5 sau a lui 10, s , i nu numai.

Determinarea ultimei cifre nenule a produsului unor numere naturale

ˆ
In aceast˘a sect , iune ne propunem s˘a determin˘am ultima cifr˘a nenul˘a a produsului m 1 ·m 2 ·. . .·m n ,
adic˘a r(m 1 · m 2 · . . . · m n ), unde m 1 , m 2 , . . . , m n sunt numere naturale nenule arbitrare, n ∈ N,
n ≥ 2.

Observat ,ia 4. Evident, u(m 1 · m 2 · . . . · m n ) = u (u(m 1 ) · u(m 2 ) · . . . · u(m n )) , pentru orice
m 1 , m 2 , . . . , m n ∈ N (n ∈ N, n ≥ 2).