Strona główna » Algorytmy » Artykuły » Dzień tygodnia
 

Dzień tygodnia

Wstęp

W dzisiejszych czasach dostęp do kalendarza jest bardzo prosty: tradycyjny podręczny kalendarz, aplikacja na komputer, telefon czy smartfon. Jednak jak wyznaczyć dzień tygodnia dowolnej daty bez użycia komputera ?

Szukanie daty

Weźmy przykładowo datę 12.07.2017. Jest to środa. Gdyby ktoś się nas zapytał jaki dzień tygodnia będzie za 4 dni to praktycznie bez namysłu można odpowiedzieć, że niedziela. Problem może się pojawić, gdy padnie pytanie jaki dzień tygodnia będzie za miesiąc. Wtedy odpowiedź nie musi być oczywista. Warto jednak zauważyć, że za każdym razem będziemy dążyć do tego, aby określić różnicę dni pomiędzy datami. Jest to bardzo wygodne, ponieważ każda różnica będąca wielokrotnością 7 nie zmienia dnia tygodnia. Innymi słowy jeśli między dwoma datami różnica wynosi p to szukamy takiego dnia tygodnia, który jest p mod 7 dni po początkowym.

Wyznaczanie różnicy pomiędzy datami utrudnia fakt, że co jakiś czas pojawiają się lata przestępne. Rok przestępny to zazwyczaj rok podzielny przez 4, ale wyjątkami są lata z dwoma zerami na końcu np. 2000. Jeśli takiego rodzaju rok podzielimy przez 400 i reszta wyniesie 0 to to też jest rok przestępny.

Podczas wyliczania reszty dni q = p mod 7 przyjmuje się, że wartości 0 odpowiada Niedziela, 1 Poniedziałek, ..., a wartości 6 sobota.

Przykład 1

Weźmy przykładowo 01.01.2000 r. Wiadomo, że w ciągu 2000 lat było 24·20 + 5 = 485 lat przestępnych. Oznacza to, że przesunięcie p to suma 1514·365 + 485·366 =7 = 1514 + 2·485. Warto zauważyć, że po roku normalnym dzień tygodnia zmienia się o 1, a w roku przestępnym o 2. Po podzieleniu przez 7 otrzymujemy 6. Czyli początek roku 2000 był w Sobotę.

Przykład 2

Sytuacja nieco się komplikuje, gdyby należało wyliczyć dla 16.06.2001 r. Wtedy ilość lat przestępnych zwiększa się o 1. Do sumy p należy jeszcze doliczyć wszystkie dni od początku roku. Oznacza to, że suma p to suma kolejno przesunięć: lat przestępnych p1 = 24·20 + 6 = 486, lat normalnych p2 = 1514, kolejnych miesięcy p3 = 31 + 28 + 31 + 30 + 31 oraz samego miesiąca p4 = 16 - 1. W sumie p = 2·486 + 1514 + 151 + 15 = 2653. Po podzieleniu przez 7 wynik to 0. Oznacz to, że 16.06.2001 r. była Niedziela.

Implementacja

Z kartki na komputer

Czy przestępny

Do implementacji wyliczania dnia tygodnia należy wiedzieć, który rok jest przestępny, a który nie. Z tego powodu podczas implmentowania została napisana funkcja czyPrzestepny(), która ma za zadanie stwierdzić na podstawie roku czy jest przestępny.

  1. bool czyPrzestepny(int rok) {
  2.   if (rok % 4 == 0 && rok % 100 != 0) {
  3.     return true;
  4.   } else
  5.   if (rok % 400 != 0) {
  6.     return true;
  7.   }
  8.   return false;
  9. }

Ile dni w miesięcu

Kolejną kluczową sprawą jest wiedza dotycząca tego ile jest dni w miesiącu. Należy tu pamiętać, że dla lat przestępnych luty ma o jeden dzień więcej. Funkcja ileDniMiesiac() na podstawie numeru miesiąca oraz tego czy rok jest przestępny zwraca ile dni ma dany miesiąc.

  1. int ileDniMiesiac(int miesiac, bool przestepny) {
  2.   switch (miesiac) {
  3.     case 2:
  4.       return przestepny ? 29 : 28;
  5.     case 4: case 6: case 9: case 11:
  6.       return 30;
  7.     default:
  8.       return 31;
  9.   }
  10. }

Wyznaczanie dnia tygodnia

Funkcja wyznaczająca dzień tygodnia dzienTygodnia() przyjmuje trzy argumenty: rok, miesiąc oraz dzień. Na ich podstawie wylicza różnice

  1. int dzienTygodnia(int rok, int miesiac, int dzien) {
  2.   int p = 0;
  3.   for (int i = 1; i < rok; i++)
  4.     p += czyPrzestepny(i) ? 2 : 1;
  5.   for (int i = 1; i < miesiac; i++)
  6.     p += ileDniMiesiac(i, czyPrzestepny(rok));
  7.   p += dzien - 1;
  8.   return p % 7;
  9. }

Algorytm realizuje dokładne to samo działanie jakie zostało zastosowane podczas wyliczania na papierze. W celu wyliczenia różnicy dni: (3. - 4.) dodawane są przesunięcia kolejnych lat, (5. - 6.) miesięcy oraz (7.) dzień. Na koniec (8.) wynikiem jest reszta z dzielenia przez 7.

Optymalizacja

Zauważmy, że w każdym wieku zagwarantowane jest wystąpienie 24 lat przestępnych i dodatkowo co 400 lat dodatkowego jednego. Oznacza to, że liczbę lat przestępnych można wyliczyć ze wzoru r/4 - r/100 + r/400. Dzięki temu nie trzeba wyliczać w pętli kolejnych przesunięć.

Z kolei dla miesięcy optymalizacja może polegać na tym, aby program posiadał wbudowaną tablicę przesunięć do k-tego miesiąca. Wtedy nie będzie istniała potrzeba sumowania, a wystarczy wybrać odpowiednią wartość.

  1. int dzienTygodnia(int rok, int miesiac, int dzien) {
  2.   int miesiacp[] = { 0, 3, 3, 6, 1, 4 , 6 ,2, 5, 0, 3, 5 };
  3.   int p = 0;
  4.   int q = (rok - 1)/4 - (rok - 1)/100 + (rok - 1)/400;
  5.   p += (rok - 1) + q;
  6.   p += miesiacp[miesiac - 1]
  7.   p += (miesiac > 2 && czyPrzestepny(rok)) ? 1 : 0;
  8.   p += dzien;
  9.   return p % 7;
  10. }

(2.) Tablica przesunięć do i-tego miesiąca. (3.) Inicjalizacja różnicy dni. (4.) Wyliczenie ile jest lat przestepnych mniejszych od rok. (5.) Zsumowanie przesunięć lat przestępnych i normalnych. (6. - 7.) Dodanie przesunięcia wynikającego z miesięcy oraz korekta dla lat przestepnych. Po zsumowaniu (8.) z liczbą dni można: (9.) zwrócić ostateczny wynik.

Testowanie funkcji

W celu przetestowania programu można skorzystać z poniższego fragmentu kodu:

  1. int main() {
  2.   char* T[] = {"Niedziela", "Poniedzialek", "Wtorek", "Sroda", "Czwartek", "Piatek", "Sobota"};
  3.   int rok, miesiac, dzien;
  4.   cout << "Podaj rok, miesiac i dzien:";
  5.   cin >> rok >> miesiac >> dzien;
  6.   cout << "Dzien tygodnia to: ";
  7.   cout << T[dzienTygodnia(rok, miesiac, dzien)];
  8.   system("pause");
  9.   return 0;
  10. }

Zadania

Zadanie 1

Wylicz przesunięcia dla 100 roku, 200 roku, 400 roku i 1600 roku. Zastosuj uzyskane wyniki w celu optymalizacji programu.

Wskazówka

Zsumuj przesunięcie dla podanych roków i podziel przez 7.

Odpowiedź

Podczas obliczania należy pamiętać, że zaczynamy od roku 0, więc do wyniku należy dodać wartość 1. Dla kolejnych lat otrzymujemy:

  • 100 rok: p = 100 + 25 mod 7 = 125 mod 7 = 6
  • 200 rok: p = 200 + 49 mod 7 = 249 mod 7 = 4
  • 400 rok: p = 400 + 97 mod 7 = 497 mod 7 = 0
  • 1600 rok: p = 1600 + 388 mod 7 = 1988 mod 7 = 0

Jak można zauważyć dla każdych pełnych 400 lat przesunięcie wynosi 0.