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-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-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