Dieser Artikel entstand aus einer Frage, die ich mir gestern gestellt habe.
"Gibt es ein Jahr, in dem kein einziger Monat am Montag beginnt?"
Auf den ersten Blick ja. Ein Jahr kann an jedem Wochentag beginnen, Monate auch jedes Mal an verschiedenen Wochentagen. Es gibt viele Möglichkeiten, höchstwahrscheinlich wird es mehr als ein solches Jahr geben.
Also dachte ich in der ersten Minute, nachdem ich mich gefragt hatte. Dies sollte bewiesen werden. Gehen Sie zum Beispiel all die Jahre durch. Ein einfacher und schneller Weg, aber nicht interessant. Mathematisch zu beweisen war eine viel verlockendere Idee, aber ich verstand überhaupt nicht, wie ich das angehen sollte. Deshalb habe ich gerade angefangen, die Dauer eines jeden Monats auf Papier zu schreiben.
Hier ist zu erwähnen, dass wir mehr über den
Gregorianischen Kalender sprechen werden, nach dem wir seit 1918 leben. Ein Teil der Argumentation wird jedoch für
Julian zutreffen.
Tatsächlich existiert ein solches Jahr nicht. Lassen Sie uns herausfinden, warum.
Teil 1. Monate
Denken Sie zunächst daran, wie viele Tage in jedem Monat:
Nun wollen wir sehen, wie viele Tage in einem Monat mehr als vier Wochen sind.
An diesem Punkt entsteht die folgende Idee. Wenn Sie dem Datum 7 Tage hinzufügen, ändert sich der Wochentag nicht. Modulare arithmetische Arbeiten. Von hier aus ist es leicht zu verstehen, dass sich der erste Tag des nächsten Monats um zwei Wochentage gegenüber dem ersten Tag des aktuellen Monats verschiebt, wenn in einem Monat zwei Tage mehr als in vier Wochen sind. Wie auch immer,
Wenn in den Tagen des Monats (28 + N), verschiebt sich der erste Tag des nächsten Monats um N Tage gegenüber dem Wochentag am ersten Tag des aktuellen Monats.
Zum Beispiel begann dieses Jahr der Januar am Dienstag, also begann der Februar am Freitag. Di + 3 = Fr.
Wie viel kostet der Wochentag am ersten Tag eines bestimmten Monats? Um dies zu finden, müssen Sie die „überschüssigen“ Tage über vier Wochen in allen vorherigen Monaten summieren. Die Tabelle zeigt die Verschiebungen relativ zum Wochentag am 1. Januar. Die erste Zeile ist für ein Nicht-Schaltjahr, die zweite für ein Schaltjahr.
Dies sieht jedoch nicht sehr aufschlussreich aus, und wir wissen, dass eine Verschiebung von sieben Tagen den Wochentag nicht ändert. Daher schreiben wir jetzt in die Tabelle die Residuen aus der Division der Gesamtverschiebungen durch 7.
Nun noch etwas! Es ist klar ersichtlich, wie der Wochentag am ersten Tag eines Monats bestimmt werden kann, wenn der Wochentag am ersten Januar bekannt ist. Sie müssen nur eine Schicht für den Monat des Interesses hinzufügen. Ich kenne das Muster Februar-März-November seit der High School, aber ich habe die anderen nicht bemerkt.
Wir haben die Antwort auf die Frage am Anfang des Artikels erhalten.
Da für beide Varianten des Jahres in der Tabelle alle Verschiebungen von 0 bis 6 vorliegen, gibt es in jedem Jahr einen Monat, der an einem bestimmten Wochentag beginnt.
Aber jetzt können Sie andere Fragen stellen. Zum Beispiel: "In welchen Jahren gibt es nur einen solchen Monat?" oder "in welchen Jahren solcher Monate ist die maximale Anzahl solcher Monate?" Dazu müssen Sie in der Lage sein, den Wochentag am 1. Januar eines jeden Jahres zu bestimmen.
Teil 2. Jahre
Als ich das Programmieren lernte und dies in der 10. Klasse der Schule bei PascalABC war, bestand eine der ersten ernsthaften Aufgaben darin, ein Verfahren zu implementieren, das einen Kalender für das Jahr druckt, der als Argument übergeben wurde. Wir hatten Tipps, welche Funktionen implementiert werden sollten. Im Allgemeinen ging es darum, die Tage zwischen zwei Daten zu zählen: der Referenz und der aktuellen, um den Wochentag am 1. Januar des gewünschten Jahres zu bestimmen.
Dieser Ansatz funktionierte, aber die Geschwindigkeit hing davon ab, wie nahe das erforderliche Jahr an der Referenz lag. Es hat mich verärgert, aber ich konnte mir dann nichts Besseres einfallen lassen. Jetzt ist der perfekte Moment gekommen, um dies vollständig zu verstehen.
Die Schaltjahre im Gregorianischen Kalender sind wie folgt zugeordnet:
- Ein Jahr mit einem Vielfachen von 400 ist ein Schaltjahr
- Die verbleibenden Jahre, deren Zahl ein Vielfaches von 100 ist, sind kein Sprung
- Die verbleibenden Jahre, deren Zahl ein Vielfaches von 4 ist, sind Schaltjahre
- Der Rest der Jahre ist kein Sprung
Diese Beschreibung zeigt, dass der Sprungzyklus einen Zeitraum von 400 Jahren hat. Es ist jedoch nicht klar, ob solche vierhundertjährigen Zyklen am selben Wochentag beginnen werden.
Beachten Sie, dass der erste Januar von Jahr zu Jahr um einen oder zwei Wochentage verschoben wird, und schreiben Sie
etwas 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(); }
Die Wochentage werden am ersten Januar eines jeden Jahres von 1801 bis 3000 angezeigt. Der Montag wird als „0“, der Dienstag als „1“ usw. bezeichnet. Wir werden alles in Form einer Tabelle mit zwei vollständigen vierhundertjährigen Zyklen und zwei Hälften präsentieren. Jahrhunderte verlaufen horizontal, die Vertikale des Jahres in diesen Jahrhunderten. In den Zellen an der Schnittstelle von Jahrhundert und Jahr steht der Wochentag, an dem dieses Jahr begann. Beispielsweise liegt der Wochentag, an dem 1997 begann, am Schnittpunkt der Spalte „1900“ und der Zeile „97“. Dies ist Mittwoch. Vollversion der Tabelle:
Teil 1 ,
Teil 2 .
In der Tabelle können Sie sofort zwei Dinge erkennen: Vierhundertjahreszyklen beginnen tatsächlich am selben Wochentag (2001, 2401 und 2801; Montag), und anstelle von 2000 gibt es "eintausendneunhundertstel". Letzteres wurde zur weiteren Bequemlichkeit absichtlich durchgeführt. Die erste Tatsache erlaubt es uns, ohne Hindernisse weiterzumachen.
Im Gregorianischen Kalender beginnen alle vierhundertjährigen Zyklen am Montag.
Am interessantesten ist jedoch die Vollversion der Tabelle. Sie können feststellen, dass jedes Jahrhundert innerhalb eines Vierhundertjahreszyklus aus einem sich wiederholenden Achtundzwanzigjahreszyklus besteht:
Das erste Jahrhundert beginnt mit einer Verschiebung des Zyklus gleich 0, das zweite mit einer Verschiebung von 4, das dritte mit einer Verschiebung von 8 und das vierte mit einer Verschiebung von 12. Dazu wird die Tabelle in der Form dargestellt, in der es „Hundertstel“ eines Jahrhunderts gibt und es keine Null gibt. Insgesamt gibt es 14 verschiedene Optionen für das Jahr. In einem 28-Jahres-Zyklus fällt einmal für jeden Wochentag der Beginn eines Schaltjahres und dreimal der Beginn eines Nicht-Schaltjahres.
Jetzt können wir den Wochentag für jedes Datum ohne Verwendung von Referenzdaten bestimmen. Um dies zu tun, müssen wir verstehen, in welchem Jahrhundert innerhalb eines vierhundertjährigen Zyklus ein Jahr ist und wie es in diesem Jahrhundert dargestellt wird. Gemäß der Tabelle bestimmen wir den Wochentag am ersten Januar des Jahres und mit Hilfe des ersten Teils des Artikels den Wochentag am bestimmten Tag des gewünschten Monats. Anstelle von tausend Wörtern
Wir werden noch mehr Code schreiben. 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; }
Update vom 07/03/2019
Wenn wir den 28-Jahres-Zyklus in Form einer Tabelle darstellen,
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
Es wird deutlich, wie Sie die Verschiebung des Wochentags zum 1. Januar berechnen können:
weekday = (index + (index / 4)) % 7;
In Anbetracht dessen sowie der Tatsache, dass die Offsets für Monate in einem Schaltjahr durch die Offsets in einem Nicht-Schaltjahr berechnet werden können, schreiben wir
nächste Funktion 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); }
Auf diese Weise können Sie den Wochentag für jedes Datum berechnen, wobei Sie nur 12 Zahlen kennen: die Verschiebung der Wochentage zum ersten Tag eines jeden Monats.
Teil 3. Zusammenfassung
Mit nur zwei Tabellen können Sie den Wochentag für jedes Datum ohne Verwendung von Referenzdaten bestimmen.
Die Reihenfolge der Wochentage am 1. Januar in einem 28-Jahres-Zyklus:
Und eine Tabelle mit Wochentagsversätzen bis zum ersten Tag eines jeden Monats für Nicht-Schalt- und Schaltjahre:
Zum Zeitpunkt des Schreibens des Artikels fand ich bei Habré zwei ähnliche Themen:
eins und
zwei . Der Autor des ersten zeigt anhand einer speziellen Tabelle, wie man den Wochentag für Daten im 20. und 21. Jahrhundert im Kopf findet. Die Tabelle, die er präsentierte, enthält 56 Zahlen. Der im Artikel vorgeschlagene Algorithmus verwendet die Tabelle der Wochentage und zwei Versatztabellen mit (28 + 2 * 12) = 52 Zahlen, an die Sie sich erinnern müssen. Der gesamte Quellcode befindet sich auf
GitHub .
Eine interessante Tatsache: Vom 1. bis 13. Februar 1918 wurde in Sowjetrussland keine einzige Person geboren.
Stellen Sie sich sonntags morgens Fragen =)