4-maths
7-mémo
9-prog.dynamique
Nombre de zéros de n factoriel ; n petit
On rappelle que, pour un entier naturel, la factorielle de se note et se définit comme le produit des entiers de à .
On constate que
se termine par aucun zéro.
se termine par 2 zéros.
se termine par 9 zéros.
Construire un tableau de longueur 1000, tel que nb_zeros_factorielle[n]
contient le nombre de zéros dans l'écriture décimale de , pour entier inférieur à .
Exemples
🐍 Console Python >>> nb_zeros_factorielle [ 3 ]
0
>>> nb_zeros_factorielle [ 11 ]
2
>>> nb_zeros_factorielle [ 42 ]
9
>>> len ( nb_zeros_factorielle ) >= 1000
True
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
Lancer # testsbksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[3] == 0bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[11] == 2bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[42] == 9bksl-nlbksl-nlassert len(nbpy-undzerospy-undfactorielle) >= 1000bksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlNBpy-undZEROS = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 33, 33, 33, 33, 33, 34, 34, 34, 34, 34, 35, 35, 35, 35, 35, 37, 37, 37, 37, 37, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 43, 43, 43, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 46, 46, 46, 46, 46, 47, 47, 47, 47, 47, 49, 49, 49, 49, 49, 50, 50, 50, 50, 50, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 53, 53, 53, 53, 53, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 68, 68, 68, 68, 68, 69, 69, 69, 69, 69, 70, 70, 70, 70, 70, 71, 71, 71, 71, 71, 72, 72, 72, 72, 72, 74, 74, 74, 74, 74, 75, 75, 75, 75, 75, 76, 76, 76, 76, 76, 77, 77, 77, 77, 77, 78, 78, 78, 78, 78, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 82, 82, 82, 82, 82, 83, 83, 83, 83, 83, 84, 84, 84, 84, 84, 86, 86, 86, 86, 86, 87, 87, 87, 87, 87, 88, 88, 88, 88, 88, 89, 89, 89, 89, 89, 90, 90, 90, 90, 90, 93, 93, 93, 93, 93, 94, 94, 94, 94, 94, 95, 95, 95, 95, 95, 96, 96, 96, 96, 96, 97, 97, 97, 97, 97, 99, 99, 99, 99, 99, 100, 100, 100, 100, 100, 101, 101, 101, 101, 101, 102, 102, 102, 102, 102, 103, 103, 103, 103, 103, 105, 105, 105, 105, 105, 106, 106, 106, 106, 106, 107, 107, 107, 107, 107, 108, 108, 108, 108, 108, 109, 109, 109, 109, 109, 111, 111, 111, 111, 111, 112, 112, 112, 112, 112, 113, 113, 113, 113, 113, 114, 114, 114, 114, 114, 115, 115, 115, 115, 115, 117, 117, 117, 117, 117, 118, 118, 118, 118, 118, 119, 119, 119, 119, 119, 120, 120, 120, 120, 120, 121, 121, 121, 121, 121, 124, 124, 124, 124, 124, 125, 125, 125, 125, 125, 126, 126, 126, 126, 126, 127, 127, 127, 127, 127, 128, 128, 128, 128, 128, 130, 130, 130, 130, 130, 131, 131, 131, 131, 131, 132, 132, 132, 132, 132, 133, 133, 133, 133, 133, 134, 134, 134, 134, 134, 136, 136, 136, 136, 136, 137, 137, 137, 137, 137, 138, 138, 138, 138, 138, 139, 139, 139, 139, 139, 140, 140, 140, 140, 140, 142, 142, 142, 142, 142, 143, 143, 143, 143, 143, 144, 144, 144, 144, 144, 145, 145, 145, 145, 145, 146, 146, 146, 146, 146, 148, 148, 148, 148, 148, 149, 149, 149, 149, 149, 150, 150, 150, 150, 150, 151, 151, 151, 151, 151, 152, 152, 152, 152, 152, 156, 156, 156, 156, 156, 157, 157, 157, 157, 157, 158, 158, 158, 158, 158, 159, 159, 159, 159, 159, 160, 160, 160, 160, 160, 162, 162, 162, 162, 162, 163, 163, 163, 163, 163, 164, 164, 164, 164, 164, 165, 165, 165, 165, 165, 166, 166, 166, 166, 166, 168, 168, 168, 168, 168, 169, 169, 169, 169, 169, 170, 170, 170, 170, 170, 171, 171, 171, 171, 171, 172, 172, 172, 172, 172, 174, 174, 174, 174, 174, 175, 175, 175, 175, 175, 176, 176, 176, 176, 176, 177, 177, 177, 177, 177, 178, 178, 178, 178, 178, 180, 180, 180, 180, 180, 181, 181, 181, 181, 181, 182, 182, 182, 182, 182, 183, 183, 183, 183, 183, 184, 184, 184, 184, 184, 187, 187, 187, 187, 187, 188, 188, 188, 188, 188, 189, 189, 189, 189, 189, 190, 190, 190, 190, 190, 191, 191, 191, 191, 191, 193, 193, 193, 193, 193, 194, 194, 194, 194, 194, 195, 195, 195, 195, 195, 196, 196, 196, 196, 196, 197, 197, 197, 197, 197, 199, 199, 199, 199, 199, 200, 200, 200, 200, 200, 201, 201, 201, 201, 201, 202, 202, 202, 202, 202, 203, 203, 203, 203, 203, 205, 205, 205, 205, 205, 206, 206, 206, 206, 206, 207, 207, 207, 207, 207, 208, 208, 208, 208, 208, 209, 209, 209, 209, 209, 211, 211, 211, 211, 211, 212, 212, 212, 212, 212, 213, 213, 213, 213, 213, 214, 214, 214, 214, 214, 215, 215, 215, 215, 215, 218, 218, 218, 218, 218, 219, 219, 219, 219, 219, 220, 220, 220, 220, 220, 221, 221, 221, 221, 221, 222, 222, 222, 222, 222, 224, 224, 224, 224, 224, 225, 225, 225, 225, 225, 226, 226, 226, 226, 226, 227, 227, 227, 227, 227, 228, 228, 228, 228, 228, 230, 230, 230, 230, 230, 231, 231, 231, 231, 231, 232, 232, 232, 232, 232, 233, 233, 233, 233, 233, 234, 234, 234, 234, 234, 236, 236, 236, 236, 236, 237, 237, 237, 237, 237, 238, 238, 238, 238, 238, 239, 239, 239, 239, 239, 240, 240, 240, 240, 240, 242, 242, 242, 242, 242, 243, 243, 243, 243, 243, 244, 244, 244, 244, 244, 245, 245, 245, 245, 245, 246, 246, 246, 246, 246]bksl-nlbksl-nlfor n, attendu in enumerate(NBpy-undZEROS):bksl-nl assert nbpy-undzerospy-undfactorielle[n] == attendu, f"Erreur avec n = {n}"bksl-nlbksl-nl Valider ∞/∞ Télécharger Téléverser Recharger Sauvegarder
nbpy-undzerospy-undfactorielle = [...]bksl-nl...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[3] == 0bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[11] == 2bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[42] == 9bksl-nlbksl-nlassert len(nbpy-undzerospy-undfactorielle) >= 1000bksl-nlbksl-nl nbpy-undzerospy-undfactorielle = [0]bksl-nlbksl-nldef nbpy-undzeros(n):bksl-nl resultat = 0bksl-nl while n % 10 == 0:bksl-nl n //= 10bksl-nl resultat += 1bksl-nl return resultatbksl-nlbksl-nlfactorielle = 1bksl-nlfor n in range(1, 1000):bksl-nl factorielle py-str= nbksl-nl suivant = nbpy-undzeros(factorielle)bksl-nl nbpy-undzerospy-undfactorielle.append(suivant)bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[3] == 0bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[11] == 2bksl-nlbksl-nlassert nbpy-undzerospy-undfactorielle[42] == 9bksl-nlbksl-nlassert len(nbpy-undzerospy-undfactorielle) >= 1000bksl-nlbksl-nl
Ici, on appelle la fonction nb_zeros
sur un nombre factoriel qui est très grand .
Version efficace 🐍 Script Python def nb_facteurs_5 ( n ):
resultat = 0
while n % 5 == 0 :
n //= 5
resultat += 1
return resultat
nb_zeros_factorielle = [ 0 ]
for n in range ( 1 , 1000 ):
apport = nb_facteurs_5 ( n )
suivant = nb_zeros_factorielle [ n - 1 ] + apport
nb_zeros_factorielle . append ( suivant )
Cette version ressemble beaucoup à la précédente ; presque la même fonction.
La différence essentielle est qu'ici nb_facteurs
est appelé avec un nombre petit en paramètre.
À méditer. Cette différence subtile est très importante. Ici, on gagne sérieusement en efficacité grâce à la taille réduite du paramètre dont le cout est plus faible à traiter.
Indice 1
Pour une version facile, on pourra utiliser une fonction qui renvoie le nombre de zéros d'un entier, on passera en argument la factorielle d'un entier.
Après avoir réussi. Tenter une version efficace avec l'indice 2.
Indice 2
Pour une version efficace, on cherchera à calculer l'augmentation du nombre de zéros, d'une factorielle à une autre, en fonction du nouveau facteur.
Il s'agit du nombre de fois que l'on peut diviser par 5 ce nouveau facteur.