Hinweis

** Dieser Artikel enthält die Geschichte von "Atcoder Beginner Contest 148 E - Double Factorial". Bitte stöbern Sie nicht, wenn Sie dieses Problem selbst lösen möchten. ** **.

Überblick

Ich bin beim Lösen von Atcoder auf ein Titelproblem gestoßen, daher werde ich diesen Artikel als Erinnerung veröffentlichen und die Meinungen von Python-Experten hören.

Problem

Atcoder Beginner Contest 148 E - Double Factorial

Definieren Sie für eine ganze Zahl n größer oder gleich 0 f (n) wie folgt:

・ F.(n) = 1 [n <Wann]\\
・ F.(n) = nf(n-2) [n \Wenn geq 2]

Angesichts der ganzen Zahl N. Finden Sie heraus, wie viele Nullen folgen, wenn f (N) dezimal geschrieben wird.

Umgebung

MacBook Pro（64bit）
Python 3.8

Die Python 3-Version von Atcoder ist "3.4.3", es wurde jedoch im Voraus bestätigt, dass ähnliche Ergebnisse in der oben genannten Umgebung erzielt werden können.

Phänomen

In den folgenden beiden Codes ist ** der obere Teil AC (richtige Antwort) **, der untere Teil WA (falsche Antwort) **.

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

Es gibt 15 Testfälle für dieses Problem, aber die folgenden 2 Testfälle wurden zu WA.

[15.txt]
IN:  237590337949089028
OUT: 29698792243636116

[16.txt]
IN:  999003990299500294
OUT: 124875498787437525

Erwartete Ursache

** Die wahrscheinliche Ursache ist eine Schreibweise dessen, was ich auf verschiedene Weise versucht habe, bis ich die Ursache identifiziert habe. ** **. ** Ich möchte nur das Ergebnis wissen! Ich hoffe, Sie können mit dem nächsten Kapitel fortfahren. ** **.

Die folgenden Teile beziehen sich auf AC und WA.

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

Beide machen ähnliche Dinge und werden wahrscheinlich das gleiche Ergebnis liefern, aber nicht.

Lassen Sie uns vorerst ausgeben, wo der Fehler auftritt. Gehen Sie wie folgt vor.

Verwenden Sie den Testfall "237590337949089028", dessen N-Wert WA ist.

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

Das Ergebnis ist wie folgt.

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

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

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

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

(Unten weggelassen)

Nachfolgende Wiederholungen (i ist 3 oder mehr und weniger als 25) hatten alle 0 AC- und WA-Fehler (AC und WA sind gleich). Es scheint, dass nur zu Beginn der Iteration ein Fehler aufgetreten ist (i = 0, 1). Im Moment scheine ich nichts so zu wissen, wie es ist, also habe ich beschlossen, über etwas anderes nachzudenken.

Hier kam mir eines in den Sinn. Welche Arten dieser Berechnungen gibt es? In Python gibt es zwei Typen, die reelle Zahlen darstellen.

int
float

Ersteres hat keine Genauigkeitsgrenzen, letzteres jedoch. Welche Art von Verschiebung haben die beiden fraglichen Berechnungsmethoden?

abc.001.jpeg

In Bezug auf "//" gemäß dem offiziellen Dokument

x // y Der Quotient aus x und y wird abgerundet Auch als Integer Division bekannt. Der Ergebnistyp ist nicht unbedingt ein Ganzzahltyp, aber der Ergebniswert ist eine Ganzzahl. Das Ergebnis wird immer auf negative Unendlichkeit gerundet.

Es gibt. Bei der AC-Berechnung scheint es, dass sie einer Variablen zugewiesen wird, ohne auch nur einmal ein Float-Typ zu werden.

Aber was ist mit WA-Berechnungen? Dies durchläuft den Float-Typ einmal in Abhängigkeit vom Berechnungsergebnis von "x / y". Ich habe es in der Umgebung überprüft.

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

Mit anderen Worten, es ist bereits ein Float-Typ, bevor math.floor () verwendet wird. Ist // und math.floor () nicht ähnlich und verschieden? Ich dachte, aber es scheint nicht die Ursache zu sein.

Die Definition von "math.floor ()" in Official Documents lautet wie folgt.

Gibt die "Etage" von x zurück (die größte Ganzzahl kleiner oder gleich x). Wenn x keine Gleitkommazahl ist, wird x .__ floor __ () intern ausgeführt und ein integrierter Wert zurückgegeben.

Vielmehr erwartete ich, dass die WA-Berechnung über ** float type ** erfolgte und zunächst einen unangemessenen Wert an math.floor () übergab.

Wie zum Zeitpunkt der Typeinführung erwähnt, weist der Float-Typ im Gegensatz zum int-Typ eine Genauigkeitsbeschränkung auf. Es gab folgende Möglichkeiten, dies zu überprüfen.

`dig.py`


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

Das offizielle Dokument lautet wie folgt.

sys.float_info Benannte Taples mit Informationen zu Float-Typen dig: Maximale Dezimalstelle, die im Gleitkomma genau angezeigt werden kann

Anscheinend kann der Float-Typ bis zu 15 Stellen genau sein, aber die darüber hinausgehenden Stellen sind verdächtig ... Lassen Sie uns nun den Testfall erneut bestätigen, der die WA früher ausgestellt hat. Dieses Mal konzentrieren wir uns auf die Anzahl der Ziffern.

i = 0 #Error: 2
d = 2.3759033794908904e+16 #17 Ziffern,Minderheit 0 Ziffern
AC:  23759033794908902     # 23759033794908904
WA:  23759033794908904     #17 Ziffern>15 Ziffern

i = 1 #Error: 1
d = 4751806758981781.0     #16 Ziffern,Minderheit 1 Ziffer
AC: 4751806758981780       #16 Ziffern>15 Ziffern
WA: 4751806758981781

i = 2 #Error: 0
d = 950361351796356.1      #15 Ziffern,Minderheit 1 Ziffer
AC: 950361351796356        #15 Ziffern=15 Ziffern
WA: 950361351796356

i = 3 #Error: 0
d = 190072270359271.22     #15 Ziffern,2 Ziffern
AC: 190072270359271        #15 Ziffern=15 Ziffern
WA: 190072270359271

(Unten weggelassen)

Der ganzzahlige Ziffernteil ist diesmal wichtig für die Antwort auf das Atcoder-Problem. Es stellt sich heraus, dass ein Fehler auftritt, wenn die ganzzahligen Ziffern die Float-Genauigkeit von 15 Ziffern überschreiten! Wenn "4 <= i <25", wird die ganzzahlige Ziffer nie größer als 15 Ziffern, so dass anscheinend kein Fehler aufgetreten ist.

Es schien, dass AC diesmal nicht war, indem der Float-Typ "d" mit dem Fehler in "math.floor ()" gebissen wurde.

Zusammenfassung

--A // B undmath.floor (A / B)machen dasselbe

Wenn sowohl A als auch B vom Typ Integer (int) sind, wird A // B als ** Integer-Typ ** ausgegeben.
Auch wenn sowohl "A" als auch "B" vom Typ Integer (int) sind, ist "math.floor (A / B)" über ** float type ** "A / B".
Wenn das Ergebnis von "A / B" die Genauigkeit des Float-Typs überschreitet, tritt ein Fehler auf.
** Die Ergebnisse von "A // B" und "math.floor (A / B)" können je nach den Werten von "A" und "B" unterschiedlich sein **
** Sei vorsichtig bei Wettkampfprofis! !! ** **.

Das ist es. Danke fürs Lesen!

[Python3] "A // B" und "math.floor (A / B)" sind nicht immer gleich! ??