J'ai lu une formule pour déterminer la différence entre deux dates en utilisant des mathématiques avec une complexité temporelle O (1)
365 * année + année / 4 - année / 100 + année / 400 + (153 * mois - 457) / 5 + jour - 306
en considérant
si le numéro du mois est inférieur à 3, année- = 1 et mois + = 12
le lien suivant montre tout le code dont je cite
https://codeforces.com/contest/304/submission/3715756
Alors si quelqu'un peut l'expliquer, s'il vous plaît?
3 Réponses :
Essayons de l'écrire formellement:
date_diff = (y1-y2)*(365+1/4-1/100+1/400) + (m1-m2)*30.6 + (d1-d2)
Simplifier:
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)
Et cela a du sens car:
ne pas dire que vous avez tort, mais en général l'arithmétique entière n'est pas si simple. Il faut considérer que a / b + c / b n'est pas forcément égal à (a + c) / b
Ce n'est pas une réponse complète mais c'est une explication.
Tout d'abord,
si le numéro du mois est inférieur à 3, année- = 1 et mois + = 12
est utilisé pour démarrer effectivement l'année à partir de mars en déplaçant le février très irrégulier jusqu'à la fin. En fait, c'est ainsi que ce calendrier a été conçu à l'origine que vous pouvez toujours voir dans les noms de certains mois comme octobre ou décembre (vous entendez probablement que Oct = 8 et Dec = 10).
Le rythme 365 * année + année / 4 - année / 100 ne fait que gérer les années bissextiles.
Le jour une partie est également claire.
Supprimons maintenant les bits qui ne sont pas pertinents lorsque nous soustrayons deux valeurs et obtenons cette valeur pour month
(3*month - 2)/5
Je ne connais pas la logique de la façon dont cela a été obtenu (je n'ai qu'une estimation à la fin) mais je peux dire pourquoi cela fonctionne. Le bit 30 * mois est évident. Et maintenant, lorsque nous avons déplacé le mois de février à sa dernière position, tous les mois du milieu de l'année ont soit 30 soit 31 jour. Écrivons-les:
Nous ne nous soucions pas de février car il n'y a pas de mois après (nous nous en préoccupions avant). Nous ne nous soucions que de ce +1 jour depuis le mois suivant!
Nous avons donc besoin maintenant d'une formule qui correspondrait à cette distribution de +1 et + 0 . Et il semble que la valeur
30*month + (3*month - 2)/5
avec division entière fait exactement cela. Vous pouvez facilement le vérifier à la main.
Probablement la façon de trouver cette idée était de remarquer que l'année (sauf pour février) suit le cycle de 5 mois suivant
+1 +0 +1 +0 +1
Je veux dire que mars-juillet et août-décembre correspondent exactement, puis janvier est à nouveau +1, donc c'est comme le premier élément du cycle suivant.
La seule partie "drôle" est que si vous calculez (153 * m-457) / 5 pour les valeurs de 3 à 15, vous obtenez
31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31
où en soustrayant chaque élément du précédent à partir de la seconde, nous obtenons
0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337
qui sont le nombre de jours de chaque mois si nous commençons à partir de mars
L'idée est donc la suivante: roulez pour que le mois "étrange" de février soit le dernier, comptez les années, les jours bissextiles et les jours des mois passés en utilisant la formule "magique" pour obtenir un nombre net augmentant de un pour chaque jour.
La soustraction de deux de ces nombres donne la différence de date.
PS: notez que même un calcul "normal" serait O (1)
Qu'est-ce qui n'est pas clair pour vous exactement?
(153 * mois - 457) / 5 + jour - 306, Cette partie en fait
Le
306n'est pas pertinent, et(153 * month-457) / 5est probablement de prendre en compte un grégorien par rapport à un autre calendrier.vous pouvez demander à l'auteur du code ici , si le code n'est pas documenté, c'est ce que je ferais