Mise en garde

** Cet article contient l'histoire du "Atcoder Beginner Contest 148 E --Double Factorial". Veuillez vous abstenir de naviguer si vous prévoyez de résoudre ce problème vous-même. ** **

Aperçu

J'ai eu un problème de titre lors de la résolution d'Atcoder, donc je posterai cet article comme rappel et pour entendre les opinions des experts Python.

problème

Atcoder Beginner Contest 148 E - Double Factorial

Pour un entier n supérieur ou égal à 0, définissez f (n) comme suit:

· F(n) = 1 [n <Quand]\\
· F(n) = nf(n-2) [n \Lorsque geq 2]

Étant donné l'entier N. Trouvez combien de 0 suivent lorsque f (N) est écrit en décimal.

environnement

MacBook Pro（64bit）
Python 3.8

La version Python 3 d'Atcoder est "3.4.3", mais il a été confirmé à l'avance que des résultats similaires peuvent être obtenus dans l'environnement ci-dessus.

phénomène

Dans les deux codes suivants, ** la partie supérieure est AC (réponse correcte) **, mais la partie inférieure est WA (réponse incorrecte) **.

`AC.py`


import math
N = int(input())
ans = 0
if N % 2 != 0:
    pass
else:
    for i in range(0, 25):
        ans += N // (10 * 5 ** i)
print(ans)

`WA.py`


import math
N = int(input())
ans = 0
if N % 2 != 0:
    pass
else:
    for i in range(0, 25):
        ans += math.floor(N / (10 * 5 ** i))
print(ans)

Il existe 15 cas de test pour ce problème, mais les 2 cas de test suivants sont devenus WA.

[15.txt]
IN:  237590337949089028
OUT: 29698792243636116

[16.txt]
IN:  999003990299500294
OUT: 124875498787437525

Cause attendue

** La cause probable est une orthographe de ce que j'ai essayé de diverses manières jusqu'à ce que j'identifie la cause. ** ** ** Je veux juste connaître le résultat! J'espère que vous pourrez passer au chapitre suivant. ** **

Les parties suivantes concernent AC et WA.

ans += N // (10 * 5 ** i) #AC
ans += math.floor(N / (10 * 5 ** i)) #WA

Les deux font des choses similaires et sont susceptibles de donner le même résultat, mais pas.

Pour le moment, sortons où l'erreur se produit. Faites comme suit.

Utilisez le scénario de test "237590337949089028" dont la valeur N est WA.

`debug.py`


import math
N = int(input())
ans_ac = 0
ans_wa = 0
if N % 2 != 0:
    pass
else:
    for i in range(0, 25):
        ans_ac = N // (10 * 5 ** i)
        ans_wa = math.floor(N / (10 * 5 ** i))
        print('i =', i)
        print('d =', N / (10 * 5 ** i))
        print('AC:', ans_ac)
        print('WA:', ans_wa)

Le résultat est le suivant.

i = 0 #Erreur: 2
d = 2.3759033794908904e+16
AC:  23759033794908902
WA:  23759033794908904

i = 1 #Erreur: 1
d = 4751806758981781.0
AC: 4751806758981780
WA: 4751806758981781

i = 2 #Erreur: 0
d = 950361351796356.1
AC: 950361351796356
WA: 950361351796356

i = 3 #Erreur: 0
d = 190072270359271.22
AC: 190072270359271
WA: 190072270359271

(Omis ci-dessous)

Les répétitions suivantes (i vaut 3 ou plus et moins de 25) avaient toutes 0 erreurs AC et WA (AC et WA sont égaux). Il semble qu'il n'y ait eu une erreur qu'au début de l'itération (i = 0, 1). Pour le moment, je ne semble rien savoir tel quel, alors j'ai décidé de penser à quelque chose de différent.

Il y avait une chose qui m'est venue à l'esprit ici. Quels sont les types de ces calculs? Il existe deux types en Python qui représentent des nombres réels.

int
float

Le premier n'a pas de limites de précision, mais le second en a. Quel type de décalage ont les deux méthodes de calcul en question?

abc.001.jpeg

Concernant «//», selon le Document officiel

x // y Le quotient de x et y est arrondi vers le bas Également connue sous le nom de division entière. Le type de résultat n'est pas nécessairement un type entier, mais la valeur de résultat est un entier. Le résultat est toujours arrondi vers l'infini négatif.

Il y a. Dans le calcul AC, il semble qu'elle soit affectée à une variable sans devenir une seule fois un type flottant.

Mais qu'en est-il des calculs WA? Cela passe par le type float une fois en fonction du résultat du calcul de «x / y». Je l'ai vérifié dans l'environnement à portée de main.

`test.py`


A = 4
B = 2
print(type(A), type(B))
print(type(A / B))
print(A / B)

'''
<class 'int'> <class 'int'>
<class 'float'>
2.0
'''

En d'autres termes, c'est déjà un type float avant d'utiliser math.floor (). «//» et «math.floor ()» ne sont-ils pas similaires et différents? J'ai pensé, mais cela ne semble pas être la cause.

La définition de «math.floor ()» dans Official Documents est la suivante.

Renvoie le "plancher" de x (le plus grand entier inférieur ou égal à x). Si x n'est pas un nombre à virgule flottante, x .__ floor __ () est exécuté en interne et une valeur intégrée est renvoyée.

Au contraire, je m'attendais à ce que le calcul WA soit via ** float type **, en passant une valeur inappropriée à math.floor () en premier lieu.

Comme mentionné au moment de l'introduction du type, le type float a une limitation de précision contrairement au type int. Il y avait les moyens suivants pour vérifier cela.

`dig.py`


import sys
print(sys.float_info.dig)
# 15

Le Document officiel est le suivant.

sys.float_info Taples nommés contenant des informations sur les types de flotteurs dig: Chiffre décimal maximum pouvant être affiché avec précision en virgule flottante

Apparemment, le type de flotteur peut être précis jusqu'à 15 chiffres, mais les chiffres au-delà sont suspects ... Maintenant, reconfirmons le cas de test qui a émis le WA plus tôt. Cette fois, nous allons nous concentrer sur le nombre de chiffres.

i = 0 #Erreur: 2
d = 2.3759033794908904e+16 #17 chiffres,Minorité 0 chiffres
AC:  23759033794908902     # 23759033794908904
WA:  23759033794908904     #17 chiffres>15 chiffres

i = 1 #Erreur: 1
d = 4751806758981781.0     #16 chiffres,Minorité 1 chiffre
AC: 4751806758981780       #16 chiffres>15 chiffres
WA: 4751806758981781

i = 2 #Erreur: 0
d = 950361351796356.1      #15 chiffres,Minorité 1 chiffre
AC: 950361351796356        #15 chiffres=15 chiffres
WA: 950361351796356

i = 3 #Erreur: 0
d = 190072270359271.22     #15 chiffres,2 chiffres
AC: 190072270359271        #15 chiffres=15 chiffres
WA: 190072270359271

(Omis ci-dessous)

La partie chiffre entier est cette fois importante pour la réponse au problème d'Atcoder. Il s'avère qu'une erreur se produit lorsque les chiffres entiers sont supérieurs à la précision de type float de 15 chiffres! Lorsque 4 <= i <25, le chiffre entier ne dépasse jamais 15 chiffres, il semble donc qu'il n'y ait pas eu d'erreur.

Il semblait que AC n'était pas cette fois en mordant le type float d avec l'erreur dans math.floor ().

Résumé

--ʻA // Betmath.floor (A / B) font la même chose --Lorsque ʻA et B sont de type entier (int) ʻA // B est sorti comme ** type entier ** --Même si ʻA et B sont de type entier (int), math.floor (A / B) est ʻA / B` via ** type float **.

Si le résultat de «A / B» dépasse la précision du type float, une erreur se produira.
** Selon la valeur de «A», «B», le résultat de «A // B» et de «math.floor (A / B)» peut être différent **
** Attention aux pros de la compétition! !! ** **

C'est tout. Merci pour la lecture!

[Python3] "A // B" et "math.floor (A / B)" ne sont pas toujours les mêmes! ??