Cet article est issu d'une question que je me suis posée hier.
"Y a-t-il une année au cours de laquelle aucun mois ne commence lundi?"
À première vue, oui. Une année peut commencer à partir de n'importe quel jour de la semaine, les mois commencent également chaque fois à différents jours de la semaine. Il existe de nombreuses options, très probablement, il y aura plus d'une telle année.
J'ai donc pensé la première minute après que je me suis demandé. Cela devrait être prouvé. Passez par toutes les années, par exemple. Un moyen simple et rapide, mais pas intéressant. Prouver mathématiquement était une idée beaucoup plus tentante, mais je ne comprenais pas du tout comment aborder cela. Par conséquent, je viens de commencer à écrire la durée de chaque mois sur papier.
Ici, il convient de mentionner que nous parlerons davantage du
calendrier grégorien , selon lequel nous vivons depuis 1918. Cependant, une partie du raisonnement sera vraie pour
Julian .
En fait, une telle année n'existe pas. Voyons pourquoi.
Partie 1. Mois
Tout d'abord, rappelez-vous combien de jours dans chaque mois:
Voyons maintenant combien de jours dans chaque mois sont supérieurs à quatre semaines.
À ce stade, l'idée suivante se pose. Si vous ajoutez 7 jours à la date, le jour de la semaine ne changera pas. Travaux arithmétiques modulaires. À partir d'ici, il est facile de comprendre que s'il y a deux jours de plus dans un mois que dans quatre semaines, le premier jour du mois suivant sera décalé de deux jours de la semaine par rapport au premier jour du mois en cours. Bref,
s'il y a (28 + N) jours dans un mois, le premier jour du mois suivant sera décalé de N jours par rapport au jour de la semaine du premier jour du mois en cours.
Par exemple, cette année, janvier a commencé mardi, alors février a commencé vendredi. Mar + 3 = ven
Combien coûte le jour de la semaine le premier jour d'un certain mois? Pour le trouver, vous devez additionner les jours «excédentaires» sur quatre semaines au cours de tous les mois précédents. Le tableau montre les changements par rapport au jour de la semaine du 1er janvier. La première ligne est pour une année sans bissextile, la seconde est pour une année bissextile.
Mais cela ne semble pas très révélateur, et nous savons qu'un décalage de sept jours ne change pas le jour de la semaine. Par conséquent, nous écrivons maintenant dans le tableau les résidus de la division des changements totaux par 7.
Maintenant une autre chose! On voit clairement comment déterminer le jour de la semaine le premier jour de n'importe quel mois si le jour de la semaine le premier janvier est connu. Vous avez juste besoin d'ajouter un décalage pour le mois d'intérêt. Je connais le schéma février-mars-novembre depuis le lycée, mais je n'ai pas remarqué les autres.
Nous avons obtenu la réponse à la question au début de l'article.
Étant donné que pour les deux variantes de l'année dans le tableau, il y a tous les décalages de 0 à 6, alors dans chaque année, il y a un mois qui commence un jour spécifique de la semaine.
Mais maintenant, vous pouvez poser d'autres questions. Par exemple, "en quelles années n'y a-t-il qu'un seul de ces mois?" ou "en quelles années de tels mois le nombre maximal de ces mois est-il?" Pour ce faire, vous devez pouvoir déterminer le jour de la semaine le premier janvier de chaque année.
Partie 2. Années
Lorsque j'ai appris à programmer, et c'était en 10e année de l'école à PascalABC, l'une des premières tâches sérieuses a été de mettre en œuvre une procédure qui imprime un calendrier pour l'année, qui a été passé en argument. Nous avons eu des conseils sur les fonctions à implémenter. En général, il s'agissait de compter les jours entre deux dates: la référence et le courant, pour déterminer le jour de la semaine au 1er janvier de l'année souhaitée.
Cette approche a fonctionné, mais la vitesse dépendait de la proximité de l'année requise avec la référence. Cela m'a bouleversé, mais je ne pouvais pas trouver quelque chose de mieux alors. Maintenant, le moment parfait est venu de bien comprendre cela.
Les années bissextiles du calendrier grégorien sont réparties comme suit:
- une année dont le nombre est un multiple de 400 est une année bissextile
- les années restantes, dont le nombre est un multiple de 100, sont sans saut
- les années restantes, dont le nombre est un multiple de 4, sont des années bissextiles
- le reste des années est sans saut
Cette description montre que le cycle de saut a une période de 400 ans. Mais il n'est pas clair si de tels cycles de 400 ans commenceront le même jour de la semaine.
Notez que le premier janvier d'une année à l'autre est décalé d'un ou deux jours de la semaine, et écrivez
du code.bool is_leap_year(int year) { if ((year % 400) == 0) return true; if ((year % 100) == 0) return false; if ((year % 4) == 0) return true; return false; } void first_weekdays_table() { ofstream file("weekdays.txt", ios_base::out); int weekday = 3; for (int i = 1801; i <= 3000; ++i) { file << weekday; if ((i % 100) != 0) { file << " "; } else { file << endl; } weekday += is_leap_year(i) ? 2 : 1; weekday %= 7; } file.close(); }
Les jours de la semaine sont affichés le premier janvier de chaque année, de 1801 à 3000. Le lundi est désigné par «0», le mardi par «1», etc. Nous présenterons le tout sous la forme d'un tableau de deux cycles complets de 400 ans et de deux moitiés. Les siècles vont horizontalement, la verticale de l'année en ces siècles. Dans les cellules à l'intersection du siècle et de l'année, le jour de la semaine où cette année a commencé est écrit. Par exemple, le jour de la semaine de 1997 a commencé à l'intersection de la colonne «1900» et de la ligne «97». C'est mercredi. Version complète du tableau:
partie 1 ,
partie 2 .
Dans le tableau, vous pouvez immédiatement remarquer deux choses: les cycles de quatre cents ans commencent vraiment le même jour de la semaine (2001, 2401 et 2801; lundi), et au lieu de 2000, il y a "mille neuf centième". Ce dernier a été fait exprès, pour plus de commodité. Le premier fait nous permet d'avancer sans obstacles.
Dans le calendrier grégorien, tous les cycles de quatre cents ans commencent le lundi.
Mais le plus intéressant réside dans la version complète du tableau. Vous pouvez constater que chaque siècle dans un cycle de quatre cents ans consiste en un cycle de vingt-huit ans qui se répète:
Le premier siècle commence par un décalage du cycle égal à 0, le deuxième avec un décalage de 4, le troisième avec un décalage de 8 et le quatrième avec un décalage de 12. Pour cela, le tableau est présenté sous la forme où il y a des «centièmes» d'un siècle et il n'y a pas de zéro. Il convient de dire qu'au total, il existe 14 options différentes pour l'année. Dans un cycle de vingt-huit ans, une fois pour chaque jour de la semaine, le début d'une année bissextile tombe et trois fois le début d'une année non bissextile.
Nous pouvons maintenant déterminer le jour de la semaine pour n'importe quelle date sans utiliser de dates de référence. Pour ce faire, nous devons comprendre à quel siècle, dans un cycle de 400 ans, est une année, et quel est son compte dans ce siècle. Selon le tableau, nous déterminons le jour de la semaine le premier janvier de l'année et à l'aide de la première partie de l'article - le jour de la semaine le jour spécifique du mois souhaité. Au lieu de mille mots
nous allons Ă©crire un peu plus de code. int get_weekday(int year, int month, int day) { int weekdays[] = {0, 1, 2, 3, 5, 6, 0, 1, 3, 4, 5, 6, 1, 2, 3, 4, 6, 0, 1, 2, 4, 5, 6, 0, 2, 3, 4, 5}; int shift_not_leap[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}; int shift_leap[] = {0, 3, 4, 0, 2, 5, 0, 3, 6, 1, 4, 6}; bool is_leap = is_leap_year(year); year -= 1; year %= 400; int century = year / 100; year %= 100; int index = (year + (4 * century)) % 28; int weekday = weekdays[index]; weekday += is_leap ? shift_leap[month - 1] : shift_not_leap[month - 1]; weekday += (day - 1); weekday %= 7; return weekday; }
Mise Ă jour du 07/03/2019
Si nous présentons le cycle de vingt-huit ans sous la forme d'un tableau,
0, 1, 2, 3, 5, 6, 0, 1, 3, 4, 5, 6, 1, 2, 3, 4, 6, 0, 1, 2, 4, 5, 6, 0, 2, 3, 4, 5
il devient clair comment vous pouvez calculer le décalage du jour de la semaine au 1er janvier:
weekday = (index + (index / 4)) % 7;
Compte tenu de cela, ainsi que du fait que les compensations pour les mois d'une année bissextile peuvent être calculées par les compensations d'une année non bissextile, nous écrivons
fonction suivante int get_weekday_c(int year, int month, int day) { int shifts[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}; int shift = shifts[month - 1]; if (is_leap_year(year) and (month > 2)) { shift += 1; }; year = (year - 1) % 400; int century = year / 100; int index = ((4 * century) + (year % 100)) % 28; int weekday = (index + (index / 4)) + shift + (day - 1); return (weekday % 7); }
Ainsi, vous pouvez calculer le jour de la semaine pour n'importe quelle date, en ne connaissant que 12 nombres: le décalage des jours de la semaine au premier jour de chaque mois.
Partie 3. Résumé
Avec seulement deux tableaux, vous pouvez déterminer le jour de la semaine pour n'importe quelle date sans utiliser de dates de référence.
La séquence des jours de la semaine au 1er janvier dans un cycle de vingt-huit ans:
Et un tableau des décalages en semaine le premier jour de chaque mois pour les années non bissextiles et bissextiles:
Au moment de la rédaction de l'article, j'ai trouvé sur Habré deux sujets similaires:
un et
deux . L'auteur du premier, à l'aide d'un tableau spécial, montre comment trouver dans l'esprit le jour de la semaine pour les dates des XX et XXI siècles. Le tableau qu'il a présenté contient 56 chiffres. L'algorithme proposé dans l'article utilise le tableau des jours de la semaine et deux tableaux de décalage contenant (28 + 2 * 12) = 52 nombres dont vous devez vous souvenir. Tout le code source est sur
GitHub .
Un fait intéressant: du 1er au 13 février 1918, pas une seule personne n'est née en Russie soviétique.
Posez-vous des questions le dimanche matin =)