Ich habe eine Formel gelesen, um den Unterschied zwischen zwei Daten mithilfe von Mathematik mit O (1) Zeitkomplexität zu bestimmen

365*year + year/4 - year/100 + year/400 + (153*month - 457)/5 + day - 306

Mit Überlegung

Wenn die Monatszahl kleiner als 3 ist, ist Jahr- = 1 und Monat + = 12

Der folgende Link zeigt den gesamten Code, aus dem ich zitiere

https://codeforces.com/contest/304/submission/3715756

Also wenn jemand es bitte erklären kann?

1
user7639165 19 Jän. 2019 im 16:27

3 Antworten

Beste Antwort

Dies ist keine vollständige Antwort, aber eine Erklärung.

Zuallererst die

Wenn die Monatszahl kleiner als 3 ist, ist Jahr- = 1 und Monat + = 12

Wird verwendet, um das Jahr effektiv ab März zu beginnen und den sehr unregelmäßigen Februar bis zum Ende zu verschieben. Eigentlich wurde dieser Kalender ursprünglich so entworfen, was Sie immer noch in den Namen einiger Monate wie Oktober oder Dezember sehen können (Sie hören wahrscheinlich, dass Okt = 8 und Dez = 10).

Der 365*year + year/4 - year/100 Beat behandelt nur die Schaltjahre.

Der Teil day ist ebenfalls klar.

Entfernen wir nun die Bits, die irrelevant sind, wenn wir zwei Werte subtrahieren und diesen Wert für month erhalten.

30*month + (3*month - 2)/5

Ich kenne die Logik nicht, wie es entstanden ist (ich habe nur eine Vermutung am Ende), aber ich kann sagen, warum es funktioniert. Das 30*month Bit ist offensichtlich. Und jetzt, als wir den Februar auf seine letzte Position verschoben haben, haben alle Monate in der Mitte des Jahres entweder 30 oder 31 Tag. Schreiben wir sie auf:

  • 31. März - +1
  • 30. April - +0
  • 31. Mai - +1
  • 30. Juni - +0
  • 31. Juli - +1
  • 31. August - +1
  • 30. September - +0
  • 31. Oktober - +1
  • 30. November - +0
  • 31. Dezember - +1
  • 31. Januar - +1

Der Februar ist uns egal, da es keine Monate danach gibt (wir haben uns vorher darum gekümmert). Wir kümmern uns nur um diesen +1 Tag seit dem nächsten Monat danach!

Was wir jetzt brauchen, ist eine Formel, die dieser Verteilung von +1 und +0 entspricht. Und es scheint, dass der Wert

(3*month - 2)/5

Mit Integer Division macht genau das. Sie können es leicht von Hand überprüfen.

Wahrscheinlich war der Weg, um auf diese Idee zu kommen, zu bemerken, dass das Jahr (außer Februar) dem folgenden 5-Monats-Zyklus folgt

+1 +0 +1 +0 +1

Ich meine, März-Juli und August-Dezember stimmen genau überein und dann ist Januar wieder +1, also ist es wie das erste Element des nächsten Zyklus.

2
SergGr 21 Jän. 2019 im 13:35

Versuchen wir es formal zu schreiben:

f(y,m,d) = 365*y+ y/4 - y/100 + y/400 + (153*m- 457)/5 + d - 306
date_diff(y1,m1,d1,y2,m2,d2) = f(y1,m1,d1) - f(y2,m2,d2)

Vereinfachung:

date_diff = (y1-y2)*(365+1/4-1/100+1/400) + (m1-m2)*30.6 + (d1-d2)

Und das macht Sinn, weil:

  1. Wir haben alle 4 Jahre ein Schaltjahr, es sei denn, das Jahr wird durch 100 und nicht durch 400 geteilt.
  2. Die durchschnittliche Anzahl von Tagen in einem Monat beträgt ~ 30,6
  3. Alle seltsamen magischen Zahlen (306 und 457) verschwinden
0
Uri Goren 19 Jän. 2019 im 19:41

Der einzige "lustige" Teil ist, dass Sie erhalten, wenn Sie (153*m-457)/5 für die Werte von 3 bis 15 berechnen

0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337

Dabei subtrahieren wir jedes Element vom vorherigen, beginnend mit dem zweiten

31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31

Das ist die Anzahl der Tage in jedem Monat, wenn wir ab März beginnen

Die Idee ist also: Drehen Sie sich so, dass der "seltsame" Februar-Monat der letzte ist, zählen Sie die Jahre, Schalttage und Tage für vergangene Monate mit der "magischen" Formel, um eine saubere Zahl zu erhalten, die sich für jeden Tag um eins erhöht.

Das Subtrahieren von zwei dieser Zahlen ergibt die Datumsdifferenz.

PS: Beachten Sie, dass sogar eine "reguläre" Berechnung O (1) wäre.

0
6502 19 Jän. 2019 im 20:28