Tomohiko Sakamotos Algorithmus – Ermitteln des Wochentags

In diesem Artikel besprechen wir, was der Tomohiko-Sakamoto-Algorithmus ist und wie man ihn verwendet, um zu ermitteln, welcher Wochentag ein bestimmtes Datum ist. Es gibt mehrere Algorithmen, um den Wochentag zu ermitteln, aber dieser Algorithmus ist der leistungsstärkste. Dieser Algorithmus findet den Tag des Monats, in dem dieses Datum liegt, in der kleinstmöglichen Zeit und mit der geringsten räumlichen Komplexität.

Problemstellung – Wir erhalten ein Datum basierend auf dem georgischen Kalender und unsere Aufgabe besteht darin, mithilfe des Algorithmus von Tomohiko Sakamoto herauszufinden, welcher Wochentag das angegebene Datum ist.

Beispiel

Geben Sie ein – Datum = 30, Monat = 04, Jahr = 2020

Ausgabe – Das angegebene Datum ist Montag

Geben Sie ein – Datum = 15, Monat = 03, Jahr = 2012

Ausgabe – Das angegebene Datum ist Donnerstag

Eingabe – Datum = 24, Monat = 12, Jahr = 2456

Ausgabe – Das angegebene Datum ist Sonntag

Sakamoto Tomohiko-Algorithmus

Lassen Sie uns nun die Intuition hinter Tomohiko Sakamotos Algorithmus besprechen.

Wie wir alle wissen, fällt der 1. Januar n. Chr. nach dem georgischen Kalender auf einen Montag.

Fall 1 Schaltjahre ignorieren

Wir besprechen zunächst den Fall, dass alle Schaltjahre ignoriert werden, d. h. ein Jahr hat 365 Tage.

Da der Januar 31 Tage und eine Woche 7 Tage hat, können wir sagen, dass der Januar 7*4 + 3 Tage hat, was bedeutet, dass der erste Tag im Februar immer 3 Tage nach dem ersten Tag im Januar liegt. p>

Da der Februar 28 Tage hat (mit Ausnahme von Schaltjahren), was selbst ein Vielfaches von 7 ist, können wir sagen, dass der 1. März am selben Tag wie der 1. Februar sein wird, was bedeutet, dass der 1. März einige Tage lang auch der 3. Januar sein wird nach dem Datum.

Für April hat der März 31 Tage, also 7*4 +3, was bedeutet, dass er 3 Tage nach dem 1. März stattfinden wird. Daher können wir sagen, dass der 1. April 6 Tage nach dem 1. Januar stattfinden wird.

Wir werden nun ein Array erstellen, in dem arr[i] die Anzahl der zusätzlichen Tage seit Beginn des Monats i relativ zum 1. Januar darstellt.

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

Fall 2 Schaltjahr

Lassen Sie uns nun die Situation mit dem Schaltjahr besprechen.

Alle vier Jahre wird ein Tag zu unseren Berechnungen hinzugefügt, aber nicht alle hundert Jahre. Wir müssen diese zusätzlichen Tage berücksichtigen. Dafür verwenden wir die Formel -

Jahr/4 (Alle 4 Jahre)

– Jahr / 100 (für alle 100 Jahre ist das ein Vielfaches von 4, aber immer noch kein Schaltjahr, wir entfernen es aus dem Schaltjahr)

+ Jahr / 400 (alle 400 Jahre ist es ein Vielfaches von 100, aber immer noch ein wiederkehrendes Jahr)

Diese Formel gibt uns die genaue Anzahl der Schaltjahre. Es gibt jedoch eine Ausnahme.

Jetzt wissen wir, dass der 29. Februar als Schalttag gilt und nicht der 0. Januar.

Das bedeutet, dass wir die ersten beiden Monate des Jahres nicht in die Berechnung einbeziehen müssen, da Schalttage keinen Einfluss darauf haben. Wenn es also Januar oder Februar ist, subtrahieren wir zum Ausgleich 1 vom Jahr. Daher sollte in diesen Monaten der Wert von Jahr/4 auf dem Vorjahr und nicht auf dem aktuellen Jahr basieren.

Um das Schaltjahrproblem zu lösen, können wir für jeden Monat nach Februar 1 vom arr[]-Wert subtrahieren, um die Lücken zu füllen. Dies löst das Schaltjahrproblem. Wir müssen die folgenden Änderungen am Algorithmus vornehmen, damit er sowohl in Schaltjahren als auch in flachen Jahren funktioniert.

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

Wenn der aktuelle Monat Januar oder Februar ist, müssen wir 1 vom Jahr subtrahieren.

Wir müssen das Jahresinkrement innerhalb des Moduls auf Jahr + Jahr/4 – Jahr/100 + Jahr/400 anstelle von Jahr ändern. Diese Änderung ist notwendig, um den zusätzlichen Tag in einem Schaltjahr zu berücksichtigen und die Berechnungen entsprechend anzupassen.

Beispiel

Der Code für diese Methode lautet:

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

Ausgabe

The given date is on Wednesday

Komplexität

Zeitkomplexität – Die Zeitkomplexität dieser Methode beträgt O(1)

Raumkomplexität – Die Raumkomplexität dieses Ansatzes beträgt O(1), da wir keinen zusätzlichen Raum verwenden.

Fazit – In diesem Artikel haben wir den Algorithmus von Tomohiko Sakamoto und die Intuition dahinter besprochen

Das obige ist der detaillierte Inhalt vonTomohiko Sakamotos Algorithmus – Ermitteln des Wochentags. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!