Correction de l'algorithme de Sakamoto pour trouver le jour de la semaine

Question

J'utilise l'algorithme de Sakamoto pour connaître le jour de la semaine à partir d'une date donnée. Quelqu'un peut-il me dire la justesse de cet algorithme? Je veux juste cela de 2000 à 2099.

L'algorithme de Wikipedia est donné à titre de référence.

 int dow(int y, int m, int d)
{
   static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
   y -= m < 3;
   return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}
 

Answer 1

Eh bien, vous pouvez dire tout simplement en regardant ce que c'est correct... en Supposant que l' t[] tableau est correct, ce que vous pouvez vérifier avec seulement 12 des vérifications ponctuelles (une pour chaque mois à l'aide de n'importe quel jour/année).

L' y -= m < 3 est une belle astuce. Il crée un "virtuel année" qui commence le 1er Mars et se termine le 28 février (ou 29), en mettant la journée supplémentaire (le cas échéant) à la fin de l'année; ou plutôt, à la fin de la précédente année. Ainsi, par exemple, virtuel année 2011 a commencé sur Mar 1 et prendra fin le 29 février, alors que virtuel année 2012 débutera le 1er Mars et fin sur la suivante, le 28 février.

En mettant l'ajoutés les jours pour les années bissextiles à la fin de la virtuel de l'année, le reste de l'expression est grandement simplifiée.

Regardons la somme:

(y + y/4 - y/100 + y/400 + t[m-1] + d) % 7

Il y a 365 jours dans une année normale. C'est 52 semaines et 1 jour. Donc, le jour de la semaine décale d'un jour par an, en général. C'est ce que l' y terme est de contribuer; il additionne un jour pour chaque année.

Mais tous les quatre ans, c'est une année bissextile. Ceux contribuer un jour supplémentaire tous les quatre ans. Grâce à l'utilisation de virtual années, il suffit d'ajouter y/4 de la somme de compter combien de jours intercalaires arriver en y ans. (Notez que cette formule suppose division entière tours vers le bas.)

Mais ce n'est pas tout à fait le droit, parce que tous les 100 ans n'est pas une année bissextile. Donc, nous devons soustraire off y/100.

Sauf que tous les 400 ans, c'est une année bissextile de nouveau. Nous devons donc ajouter y/400.

Enfin, nous ajoutons le jour du mois, d et un décalage à partir d'une table qui dépend du mois (car le mois de frontières à l'intérieur de l'année sont assez arbitraire).

Puis prendre la chose entière mod 7 puisque c'est combien de temps une semaine.

(Si les semaines ont été les huit jours, par exemple, ce qui aura changé dans cette formule? Ainsi, il serait mod 8, évidemment. Aussi l' y faudrait 5*y, en raison de 365 % 8 == 5. Aussi le mois de la table t[] auraient besoin d'ajuster. C'est tout.)

D'ailleurs, Wikipédia est énoncé que le calendrier est "bon jusqu'à 9999" est totalement arbitraire. Cette formule est bonne, tant que nous restons avec le calendrier Grégorien, si c'est 10 ans, 100 ans, 1000 ans, ou 1 million d'années.

[modifier]

L'argument ci-dessus est essentiellement une preuve par induction. C'est, en supposant que la formule fonctionne pour un particulier (y,m,d), vous prouver que ça marche pour (n+1,m,d) et (y,m,d+1). (Où y est un "virtuel année" à partir du 1er Mars.) Donc, la question clé est, la somme de changement par la quantité correcte lorsque vous vous déplacez d'une année à l'autre? Avec les connaissances de l'année bissextile règles, et avec le "virtuel année" avoir une journée supplémentaire à la fin de l'année, il trivialement n'.