L'algorithme de Tomohiko Sakamoto - trouver le jour de la semaine

Dans cet article, nous discuterons de ce qu'est l'algorithme de Tomohiko Sakamoto et comment l'utiliser pour identifier le jour de la semaine à une date donnée. Il existe plusieurs algorithmes pour connaître le jour de la semaine, mais celui-ci est le plus puissant. Cet algorithme trouve le jour du mois au cours duquel cette date apparaît dans le plus petit temps possible et avec la plus petite complexité spatiale.

Énoncé du problème - On nous donne une date basée sur le calendrier géorgien et notre tâche est de savoir quel jour de la semaine la date donnée est en utilisant l'algorithme de Tomohiko Sakamoto.

Exemple

Entrez - Date = 30, Mois = 04, Année = 2020

Sortie - La date indiquée est lundi

Entrez - Date = 15, Mois = 03, Année = 2012

Sortie - La date indiquée est jeudi

Entrée - Date = 24, Mois = 12, Année = 2456

Sortie - La date indiquée est dimanche

Algorithme de Sakamoto Tomohiko

Parlons maintenant de l’intuition derrière l’algorithme de Tomohiko Sakamoto.

Comme nous le savons tous, selon le calendrier géorgien, le 1er janvier après JC tombe un lundi.

Cas 1 Ignorer les années bissextiles

Nous discutons d'abord du cas où toutes les années bissextiles sont ignorées, c'est-à-dire qu'il y a 365 jours dans une année.

Puisque janvier a 31 jours et qu'une semaine a 7 jours, on peut dire que janvier a 7*4 + 3 jours, ce qui signifie que le premier jour de février est toujours 3 jours après le premier jour de janvier. p>

Comme février compte 28 jours (sauf les années bissextiles), ce qui est lui-même un multiple de 7, on peut dire que le 1er mars sera le même jour que le 1er février, ce qui veut dire que le 1er mars sera aussi le 3 janvier quelques jours après la date.

Maintenant, pour avril, mars compte 31 jours, soit 7*4 +3, ce qui signifie que cela se produira 3 jours après le 1er mars. On peut donc dire que le 1er avril surviendra 6 jours après le 1er janvier.

Nous allons maintenant construire un tableau où arr[i] représente le nombre de jours supplémentaires depuis le mois i par rapport au 1er janvier.

Nous avons arr[] = { 0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5 }.

Cas 2 Année bissextile

Parlons maintenant de la situation des années bissextiles.

Tous les quatre ans, un jour est ajouté à nos calculs, mais pas tous les cent ans. Nous devons tenir compte de ces jours supplémentaires. Pour cela nous utiliserons la formule -

Année/4 (Tous les 4 ans)

– Année / 100 (pour chaque 100 années qui est un multiple de 4 mais qui n'est toujours pas bissextile, on le retire de l'année bissextile)

+ année / 400 (tous les 400 ans, c'est un multiple de 100, mais toujours une année récurrente)

Cette formule nous donnera le nombre précis d’années bissextiles. Il existe cependant une exception.

Maintenant, nous savons que le 29 février est considéré comme un jour bissextile, et non le 0 janvier.

Cela signifie que nous n’avons pas besoin d’inclure les deux premiers mois de l’année dans le calcul car les jours bissextiles n’ont aucun effet sur eux. Donc si c'est janvier ou février, on soustraira 1 à l'année pour compenser. Par conséquent, au cours de ces mois, la valeur de année/4 doit être basée sur l’année précédente plutôt que sur l’année en cours.

Pour tenir compte du problème des années bissextiles, nous pouvons soustraire 1 de la valeur arr[] pour chaque mois après février pour combler les lacunes. Cela résout le problème des années bissextiles. Nous devons apporter les modifications suivantes à l’algorithme afin qu’il fonctionne à la fois dans les années bissextiles et dans les années plates.

arr[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 }

Si le mois en cours est janvier ou février, nous devons soustraire 1 à l'année.

Nous devons modifier l'incrément d'année dans le module en année + année/4 – année/100 + année/400 au lieu de année. Ce changement est nécessaire pour tenir compte du jour supplémentaire dans une année bissextile et ajuster les calculs en conséquence.

Exemple

Le code de cette méthode est :

#include <bits/stdc++.h>
using namespace std;
// code to find out the day number of the given date
int Weekday(int year, int month, int day) {
   int arr[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
	
   if ( month < 3 )
      year -= 1;
   return ( ( year + year / 4 - year / 100 + year / 400 + arr[month - 1] + day) % 7 );
}

int main(void) {
   int day = 9, month = 9, year = 2020;
   int d = Weekday(year, month, day);
   string days[] = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" };
   cout<< " The given date is on "; 
   cout << days[d];
   return 0;
}

Sortie

The given date is on Wednesday

Complexité

Complexité temporelle - La complexité temporelle de cette méthode est O(1)

Complexité spatiale - La complexité spatiale de cette approche est O(1) puisque nous n'utilisons aucun espace supplémentaire.

Conclusion - Dans cet article, nous avons discuté de l'algorithme de Tomohiko Sakamoto et de l'intuition qui se cache derrière lui

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!