Korrektheit von Sakamotos Algorithmus zur Ermittlung des Wochentags

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

Frage

Ich verwende den Sakamoto-Algorithmus, um den Wochentag eines bestimmten Datums herauszufinden.Kann mir jemand die Richtigkeit dieses Algorithmus sagen?Ich möchte das nur von 2000 bis 2099.

Der Algorithmus von Wikipedia wird als Referenz angegeben.

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;
}
War es hilfreich?

Lösung

Nun, Sie können es nur durch einen Blick darauf erkennen, dass es korrekt ist ... Angenommen, das t[]-Array ist korrekt, was Sie mit nur 12 Stichproben überprüfen können (eine für jeden Monat an einem beliebigen Tag / Jahr).

Der y -= m < 3 ist ein schöner Trick. Es wird ein "virtuelles Jahr" erstellt, das am 1. März beginnt und am 28. (oder 29.) Februar endet, wobei der zusätzliche Tag (falls vorhanden) am Ende des Jahres liegt. oder besser gesagt am Ende des vorherigen Jahres. So begann beispielsweise das virtuelle Jahr 2011 am 1. März und endet am 29. Februar, während das virtuelle Jahr 2012 am 1. März beginnt und am folgenden 28. Februar endet.

Indem der hinzugefügte Tag für Schaltjahre am Ende des virtuellen Jahres steht, wird der Rest des Ausdrucks massiv vereinfacht.

Schauen wir uns die Summe an: 

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

Ein normales Jahr hat 365 Tage. Das sind 52 Wochen plus 1 Tag. Der Wochentag verschiebt sich also im Allgemeinen um einen Tag pro Jahr. Dazu trägt der Begriff y bei. Für jedes Jahr wird ein Tag hinzugefügt.

Aber alle vier Jahre ist ein Schaltjahr. Diese tragen alle vier Jahre einen zusätzlichen Tag bei. Dank der Verwendung von virtuellen Jahren können wir der Summe einfach y/4 hinzufügen, um zu zählen, wie viele Schalttage in y-Jahren auftreten. (Beachten Sie, dass diese Formel davon ausgeht, dass die Ganzzahldivision abrundet .)

Aber das ist nicht ganz richtig, denn alle 100 Jahre ist kein Schaltjahr. Wir müssen also y/100 abziehen.

Nur dass alle 400 Jahre wieder ein Schaltjahr ist. Also müssen wir y/400 hinzufügen.

Schließlich fügen wir einfach den d des Monats und einen Versatz aus einer Tabelle hinzu, die vom Monat abhängt (da die Monatsgrenzen innerhalb des Jahres ziemlich willkürlich sind).

Dann nimm das Ganze Mod 7, da so lange eine Woche dauert.

(Wenn Wochen zum Beispiel acht Tage wären, was würde sich in dieser Formel ändern? Nun, es wäre natürlich Mod 8. Auch der y müsste 5*y sein, weil 365% 8== 5. Auch der Monat Tabelle t[] müsste angepasst werden. Das war's.)

Übrigens ist die Aussage von Wikipedia, dass der Kalender "gut bis 9999" ist, völlig willkürlich. Diese Formel ist gut, egal wie lange wir uns an den Gregorianischen Kalender halten, ob das nun 10 Jahre, 100 Jahre, 1000 sind Jahre oder 1 Million Jahre.

[Bearbeiten]

Das obige Argument ist im Wesentlichen ein Beweis durch Induktion. Unter der Annahme, dass die Formel für ein bestimmtes (y, m, d) funktioniert, beweisen Sie, dass sie für (y + 1, m, d) und ( y, m, d + 1). (Wobei y ab dem 1. März ein "virtuelles Jahr" ist.) Die Schlüsselfrage lautet also: Ändert sich die Summe um den richtigen Betrag, wenn Sie von einem Jahr zum nächsten wechseln? Mit Kenntnis der Schaltjahrregeln und dem "virtuellen Jahr" mit dem zusätzlichen Tag zum Jahresende ist dies trivial.

Andere Tipps

Kürzlich habe ich hier geschrieben >.

Die Grundidee hinter dem Algorithmus ist, dass Februar und Januar den Tag zählen der Woche vom 31. Dezember des Vorjahres . Für alle anderen Monate zählen wir den Wochentag ab dem aktuellen Jahr, dem 31. Dezember. Wir tun dies in zwei Schritten Schritte zuerst berechnen wir den Wochentag des letzten Tages des Monats vor dem aktuellen Monat m, dann fügen wir einfach d modulo sieben hinzu.

31 Dez 1 BC ist Sonntag, der als 0 codiert ist, Montag ist 1 usw. Wir haben also: 0 + y + y/4 - y/100 + y/400 dies mit y -= m < 3 berechnet Wochentag vom 31. Dezember des laufenden Jahres oder des Vorjahres (je nach Monat). Hinweis: 365 % 7 == 1 Dies erklärt, warum wir y anstelle von 365*y geschrieben haben. Der d der letzten Komponente ist offensichtlich, da wir den Wochentag vom letzten Tag des Vormonats zählen.

Der letzte Teil, der erklärt werden muss, sind Werte im Array. Bei den ersten beiden Werten handelt es sich um die Anzahl der Tage seit dem 31. Dezember des letzten Jahres bis zum Beginn des Monats % 7. Für den Rest der Monate werden sie vom Ende des vorherigen Monats bis zum 31. Dezember des laufenden Jahres mit einer Anzahl von sieben Tagen negiert. Mit anderen Worten, wir subtrahieren Tage durch Addition von Modulo 7, z. (a-b)%7 = (a+(7-b%7))%7.

Weitere Erklärungen finden Sie in meinem Blog-Beitrag.

Dies ist möglicherweise keine vollständige Antwort wie die oben genannten, möchte jedoch nur eines in Bezug auf dieses Array hinzufügen: 0 3 2 5 0 3 5 1 4 6 2 4

Betrachten Sie Monate, die von März bis Februar beginnen, genau wie andere sagten:

  1. März
  2. April
  3. Mai
  4. Juni
  5. Juli
  6. August
  7. September
  8. Oktober
  9. November
  10. Dezember
  11. Januar
  12. Februar

    Schreiben von Januar bis Dezember aus dem obigen Nummerierungsstil:

    Betrachten Sie dies als Array: int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

    Führen Sie nun für alle Elemente im Array Folgendes aus: (2.6*m - 0.2) mod 7 Wenn Sie das Ergebnis als Ganzzahl analysieren, erhalten Sie Folgendes: 0 3 2 5 0 3 5 1 4 6 2 4

    • Diese Formel finden Sie hier: wikipedia 
      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;
}

      this: + y/4 - y/100 + y/400 bezieht sich auf das Schaltjahr. Das Algo für das Schaltjahr ist:

      1. Perfekt teilbar durch 400 -> wahr
      2. WENN perfekt durch 100 teilbar, aber nicht durch 400 -> Falsch
      3. Teilbar durch 4 -> Wahr

        führt Überprüfungen der obigen Reihenfolge durch. Vielleicht haben sie deshalb y / 100 subtrahiert und y / 4 & y / 400 addiert. Ja, dumme Logik

Für Gregorianischen Kalender

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;
}

Erläuterung:

  • Siehe das kommentierte Array für
 t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};

und vergleiche es mit einem Kalender eines ganzen Jahres (run cal 2um einen Kalender im Terminal unter Linux/Unix zu generieren) beachten Sie den Starttag der Woche des Tages für jeden Monat.

  • Jedes normale Jahr verschiebt einen Wochentag und jedes Schaltjahr verschiebt zwei Tage der Woche.als (365 %7)=1 und (366 %7)=2
 i= y+y/4-y/100+y/400
  • Wir sollten den zusätzlichen Tag jedoch nicht berechnen, wenn y ein Schaltjahr für Monat 0 und 1 ist
y-=m<3

  • Aber auf diese Weise entfernen wir auch den zusätzlichen Tag aus Nicht-Schaltjahren.Deshalb füllen wir die Lücke, indem wir für jeden Monat nach Februar einen Tag abziehen.

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

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top