L'exactitude de l'algorithme de Sakamoto pour trouver le jour de la semaine

StackOverflow https://stackoverflow.com/questions/6385190

Question

J'utilise l'algorithme de Sakamoto pour découvrir le jour de la semaine à partir d'une date donnée. Quelqu'un peut-il me dire l'exactitude de cet algorithme? Je veux juste ça de 2000 à 2099.

L'algorithme de Wikipédia est donné pour 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;
}
Était-ce utile?

La solution

Eh bien, vous pouvez dire simplement en regardant que c'est correct ... en supposant que le t[] Le tableau est correct, que vous pouvez vérifier avec seulement 12 contrôles ponctuels (un pour chaque mois en utilisant n'importe quel jour / année).

La y -= m < 3 est une belle astuce. Il crée une "année virtuelle" qui commence le 1er mars et se termine le 28 février (ou 29), en mettant le jour supplémentaire (le cas échéant) fin de l'année; ou plutôt, à la fin du précédent an. Ainsi, par exemple, Virtual Year 2011 a commencé le 1er mars et se terminera le 29 février, tandis que l'année virtuelle 2012 débutera le 1er mars et se terminera le 28 février suivant.

En mettant le jour supplémentaire pour les années de saut à la fin de l'année virtuelle, le reste de l'expression est massivement simplifié.

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 plus 1 jour. Ainsi, le jour de la semaine change d'un jour par an, en général. C'est ce que le y Le terme contribue; Il en ajoute un à la journée pour chaque année.

Mais tous les quatre ans, c'est une année de saut. Ceux-ci contribuent un jour supplémentaire tous les quatre ans. Grâce à l'utilisation d'années virtuelles, nous pouvons simplement ajouter y/4 à la somme pour compter combien de jours de saut se produisent y années. (Notez que cette formule assume des tours de division entier vers le bas.)

Mais ce n'est pas tout à fait vrai, car tous les 100 ans n'est pas une année de saut. Nous devons donc soustraire y/100.

Sauf que tous les 400 ans sont à nouveau une année saut. Nous devons donc ajouter y/400.

Enfin, nous ajoutons juste le jour du mois d et un décalage d'un tableau qui dépend du mois (car les limites du mois dans l'année sont assez arbitraires).

Ensuite, prenez le tout Mod 7 car c'est combien de temps une semaine.

(Si les semaines avaient huit jours, par exemple, qu'est-ce qui changerait dans cette formule? Eh bien, ce serait le mod 8, évidemment. Aussi le y devrait être 5*y, car 365% 8 == 5. Aussi le tableau du mois t[] aurait besoin de réglage. C'est ça.)

Soit dit en passant, la déclaration de Wikipedia selon laquelle le calendrier est "bon jusqu'au 9999" est totalement arbitraire. Cette formule est bonne pour aussi longtemps que nous respectons le calendrier Grégorien, que ce soit 10 ans, 100 ans, 1000 ans ou 1 million d'années.

Éditer

L'argument ci-dessus est essentiellement une preuve par induction. C'est-à-dire, en supposant que la formule fonctionne pour un particulier (y, m, d), vous prouver qu'il fonctionne pour (y + 1, m, d) et (y, m, d + 1). (Où y est une "année virtuelle" à partir du 1er mars.) Donc, la question clé est: la somme change-t-elle par le montant correct lorsque vous passez d'un an à l'autre? Avec la connaissance des règles de l'année Leap, et avec «l'année virtuelle» ayant la journée supplémentaire à la fin de l'année, il le fait trivialement.

Autres conseils

Récemment, j'ai écrit un article de blog sur cet algorithme ici.

L'idée de base derrière l'algorithme est pour février et janvier pour compter le jour de la semaine à partir du 31 décembre de la année précédente. Pour tous les autres mois, nous compterons le jour de la semaine courant Année 31 décembre. Nous faisons cela en deux étapes en premier, nous calculons le jour de la semaine du dernier jour du mois précédent le mois en cours m Ensuite, nous ajoutons juste d modulo sept.

31 décembre 1 BC est dimanche qui est codé comme 0, lundi est 1 etc. Nous avons donc: 0 + y + y/4 - y/100 + y/400 avec y -= m < 3 Calose le jour de la semaine du 31 décembre de l'année en cours ou de l'année précédente (selon le mois). Noter: 365 % 7 == 1 Cela explique pourquoi nous avons écrit y à la place de 365*y. Le dernier composant d est évident depuis que nous commençons à compter le jour de la semaine par rapport au mois précédent le dernier jour.

La dernière partie qui doit être expliquée sont des valeurs dans le tableau, pour les deux premières valeurs, ce sont le nombre de jours depuis le 31 décembre de l'année dernière au début du mois % 7. Pour le reste des mois, ils sont Nired modulo sept Nombre de jours à partir de la fin du mois de prev au 31 décembre de l'année en cours. En d'autres termes, nous soustrayons les jours par modulo supplémentaire 7, par exemple (a-b)%7 = (a+(7-b%7))%7.

Plus d'explications que vous pouvez trouver dans mon article de blog.

Ce n'est peut-être pas une réponse complète comme certains mentionnés ci-dessus, mais je voudrais simplement ajouter une chose concernant ce tableau: 0 3 2 5 0 3 5 1 4 6 2 4

Considérez des mois à partir de mars et se terminant en février comme les autres l'ont dit:

  1. Mars
  2. Avril
  3. Peut
  4. Juin
  5. Juillet
  6. Août
  7. Septembre
  8. Octobre
  9. Novembre
  10. Décembre
  11. Janvier
  12. Février

Écriture de janvier à décembre par le style de numérotation ci-dessus:

Considérez donc cela comme un tableau:int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

Maintenant, pour tous les éléments de la table, faites-le: faites: (2.6*m - 0.2) mod 7Analyser le résultat entier et vous obtiendrez ceci:0 3 2 5 0 3 5 1 4 6 2 4

  • Vous pouvez trouver cette formule ici: Wikipédia
int dayOfWeek(int d, int m, int y){
  // Months Array
  int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

  // Convert months array
  for (int i = 0; i < 12; i++){
    int ans = t[i] * 2.6 - 0.2;
    t[i] = ans % 7;
  }

  // Continue Algo
  if(m<3)
    y -= 1;

  int day = (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
  return day;
}

cette : + y/4 - y/100 + y/400 est lié à l'année de saut. L'algo pour vérifier l'année Leap est:

  1. Parfaitement divisible par 400 -> vrai
  2. Si parfaitement divisible par 100 mais pas par 400 ->> Faux
  3. Divisible par 4 -> Vrai

Effectuez des vérifications sur la commande ci-dessus. C'est peut-être pourquoi ils ont soustrait Y / 100 et ajouté Y / 4 & Y / 400. Ouais logique idiote 😅

Je sais que ce n'est peut-être pas la réponse, Mais cela pourrait aider ceux qui ont du mal à se souvenir / comprendre des choses, Oui! Nous n'avons pas tous des niveaux de QI de compréhension de QI élevés et malheureusement, certains d'entre nous ne se souviennent pas non plus de choses, lol.

Pour le calendrier grégorien

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

Explication:

  • Voir le tableau commenté pour
 t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};

et comparez-le avec un calendrier d'une année entière (courir cal 2Pour générer un calendrier dans le terminal en Linux / Unix), notez le jour de départ de la semaine de la journée pour chaque mois.

  • Chaque année normale, changez un jour de la semaine et sautant l'année de déplacement de deux jours de la semaine. comme (365% 7) = 1 et (366% 7) = 2
 i= y+y/4-y/100+y/400
  • Mais nous ne devons pas calculer le jour supplémentaire si y est une année de saut pour le mois 0 et 1
y-=m<3

  • Mais de cette façon, nous supprimons également la journée supplémentaire des années non-laures. Nous allons donc combler l'écart en soustrayant 1 jour pour chaque mois après février.

    int t[12]={0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top