Nombre de zéros à la fin d'un entier⚓︎
On souhaite avoir une fonction nb_zeros
qui détermine le nombre de zéros à la fin de l'écriture décimale d'un entier \(n>0\), très grand.
Méthode
On s'interdit, ici, d'utiliser la fonction de conversion str
. Cette méthode est totalement inefficace avec des nombres très grands.
On demande plutôt de compter combien de fois on peut diviser un nombre par \(10\) avec un reste égal à zéro.
Par exemple,
- \(42000 = 4200×10 + 0\),
- \(4200 = 420×10 + 0\),
- \(420 = 42×10 + 0\),
- \(42\) n'est pas divisible par \(10\).
On a pu diviser \(42000\) trois fois par \(10\) avec un reste égal à \(0\). Ce nombre se finit donc par 3 zéros.
Exemples
>>> nb_zeros(42000)
3
>>> nb_zeros(3210)
1
>>> nb_zeros(282475249)
0
>>> nb_zeros(7**10000)
0
>>> nb_zeros(7**10000 * 1000)
3
Pour information,
- \(7^{10} = 282475249\) finit sans aucun zéro.
- \(7^{10000}\) est un nombre très grand qui finit sans aucun zéro.
def nbpy-undzeros(n):bksl-nl ...bksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undzeros(42000) == 3bksl-nlassert nbpy-undzeros(3210) == 1bksl-nlassert nbpy-undzeros(282475249) == 0bksl-nlassert nbpy-undzeros(7py-strpy-str10000) == 0bksl-nlassert nbpy-undzeros(7py-strpy-str10000 py-str 1000) == 3bksl-nlbksl-nldef nbpy-undzeros(n):bksl-nl # non valable pour n = 0bksl-nl resultat = 0bksl-nl while n % 10 == 0:bksl-nl n = n // 10bksl-nl resultat += 1bksl-nl return resultatbksl-nlbksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undzeros(42000) == 3bksl-nlassert nbpy-undzeros(3210) == 1bksl-nlassert nbpy-undzeros(282475249) == 0bksl-nlassert nbpy-undzeros(7py-strpy-str10000) == 0bksl-nlassert nbpy-undzeros(7py-strpy-str10000 py-str 1000) == 3bksl-nlbksl-nl
A
On fait attention ; la fonction bouclerait à l'infini pour \(n=0\) ; elle n'est pas clairement définie.
Étudions des variantes.
Version avec divmod
⚓︎
divmod
renvoie le quotient et le reste dans une division entière. Par exemple divmod(1789, 100)
renvoie (17, 89)
. En effet, \(1789\) divisé par \(100\) donne un quotient de \(17\) et un reste de \(89\). On peut vérifier que \(1789 = 17×100 + 89\).
def nb_zeros(n):
# non valable pour n = 0
resultat = -1
reste = 0
while reste == 0:
n, reste = divmod(n, 10)
resultat += 1
return resultat
Ici, on initialise reste
à \(0\) et resultat
à \(-1\) ; on est sûr de faire au moins un tour de boucle, et il y en aura un de plus que le nombre cherché.
On ne fait qu'une seule division par tour de boucle grâce à divmod
.
Dans la version précédente, il y a avait une division et un modulo par tour de boucle.
Soyons honnête : cette version apporte très peu en efficacité, mais rend le code plus complexe. La première version est largement recommandée.
Z