Page 34 - MATINF Nr.2

˘
MATEMATICA PENTRU PROGRAMATORI SI
,
PROGRAMARE PENTRU MATEMATICIENI

Determinarea ultimei cifre nenule pentru produse de

numere naturale

2
1
3
Stelian Corneliu Andronescu , Costel B˘alc˘au , Doru Constantin s , i
Doru Anastasiu Popescu 4

ˆ
In acest articol vom prezenta algoritmi eficient , i pentru determinarea ultimei cifre nenule a
unui num˘ar natural, a unui produs de numere naturale s , i a factorialului unui num˘ar natural.

Determinarea ultimei cifre nenule a unui num˘ar natural

Definit , ia 1. a) Pentru orice num˘ar natural m (scris ˆın baza 10), not˘am cu u(m) ultima cifr˘a
a num˘arului m.
b) Pentru orice num˘ar natural nenul m, not˘am cu r(m) ultima cifr˘a nenul˘a a num˘arului
m.

Observat ,ia 1. Evident, u(m) = m MOD 10, pentru orice m ∈ N. Pe de alt˘a parte, pentru orice
∗
m ∈ N avem r(m) = m MOD 10 k , unde k este cel mai mic num˘ar natural nenul cu proprietatea
10 k−1
k
c˘a m MOD 10 6= 0.
Cifra r(m) poate fi calculat˘a prin ˆımp˘art , iri succesive la 10, cˆat timp restul este egal cu zero,
ˆ
algoritm care are complexitatea O (ln m). Intr-adev˘ar, num˘arul de imp˘art , iri succesive la 10 este
egal cu 1 plus num˘arul de zerouri ˆın care se termin˘a m, deci ˆın cazul cel mai defavorabil, s , i
anume cˆand m = c 1 00 . . . 0, se efectueaz˘a 1 + [lg m] ˆımp˘art , iri ([x] reprezint˘a partea ˆıntreag˘a a
num˘arului real x). Definit , iile s , i propriet˘at , i ale ordinelor de complexitate ale algoritmilor pot fi
g˘asite, de exemplu, ˆın [1].

Un algoritm echivalent pentru calcului lui r(m), util ˆın sect , iunile urm˘atoare, se bazeaz˘a pe
urm˘atoarea proprietate.

Propozit , ia 1. Pentru orice num˘ar natural nenul m exist˘a un unic triplet (a, b, c) cu a, b ∈ N
s , i c ∈ {1, 3, 7, 9} astfel ˆıncˆat
a
b
m = 2 · 5 · (M10 + c) (1)
(notat ,ia M10 reprezint˘a un multiplu al lui 10).
1 Lect. univ. dr., Universitatea din Pites , ti, corneliuandronescu@yahoo.com
2
Conf. univ. dr., Universitatea din Pites , ti, cbalcau@yahoo.com
3
Conf. univ. dr., Universitatea din Pites , ti, doru.constantin@upit.ro
4
Conf. univ. dr., Universitatea din Pites , ti, dopopan@yahoo.com
34