Problem

Piszę klasę do przechowywania dat w c ++ i znalazłem następujący problem:

Mam kilka dniN od daty odniesienia (w moim przypadku będzie to 1 stycznia 0001 r.), w tym dni przestępnych, które upłynęły od dnia odniesienia.Jak mogę przekonwertować tę liczbę na rokY, miesiącM i dzieńD wydajnie?

Chciałbym to zrobić tak efektywnie, jak to możliwe, więc najlepsza implementacja miałaby oczywiście złożoność O (1).

Następne rozdziały wyjaśnią niektóre rzeczy, których się już nauczyłem.

Lata przestępne

Aby ustalić, czy rok jest skokiem, czy nie, istnieje kilka zasad:

Lata podzielne przez 4 to skokWyjątek od reguły 1: lata podzielne przez 100 nie są skokoweWyjątek od reguły 2: lata podzielne przez 400 to skok

Tłumaczyłoby to w następujący sposób:

bool IsLeapYear(int year)
{
    // Corrected after Henrick's suggestion
    if (year % 400 == 0) return true;
    if ((year % 4 == 0) && (year % 100 != 0)) return true;
    return false;
}

Skuteczną metodą obliczenia, ile lat minie przed rokiem, byłaby:

int LeapDaysBefore(int year)
{
    // Years divisible by 4, not divisible by 100, but divisible by 400
    return ((year-1)/4 - (year-1)/100 + (year-1)/400);
}

Obliczanie miesiąca

Kiedy znajdę rok, mogę obliczyć, ile dni pozostało do bieżącego roku i mogę odjąć tę liczbę od N. To da mi dzień roku.

Trzymając tabelę z numerem dnia, od którego zaczyna się każdy miesiąc, możemy łatwo obliczyć miesiąc. Stworzyłem także funkcję, która doda 1, jeśli rok jest skokiem, a miesiąc jest większy lub równy 2.

// What day each month starts on (counting from 0)
int MonthDaySt[] = { 0, 31, 59, 90, 120, 151, 181, 212, 
    243, 273, 304, 334, 365 };

int MonthDayStart(int month, bool leap)
{
   if (leap && month >= 2) return MonthDaySt[month]+1;
   return MonthDaySt[month];
}

Mój pomysł

Mój algorytm jest dość skomplikowany i wygląda tak:

void GetDate(int N, int &Y, int &M, int &D)
{
    int year_days;

    // Approximate the year, this will give an year greater or equal
    // to what year we are looking for.
    Y = N / 365 + 1;

    // Find the actual year, counting leap days
    do {
        Y--;

        // Calculate the actual number of days until the
        // approximate year
        year_days = Y * 365 + LeapDaysBefore(year);

    } while (year_days > N);

    // Add 1, because we start from year 1 AD (not 0)
    Y++;

    // Calculate month
    uint64_t diff = N - year_days; // Will give us the day of the year
    bool leap = IsLeapYear(Y);  // Is current year leap?

    // Use table to find month
    M = 0;
    while (MonthDayStart(M, leap) <= diff && M <= 12)
        M++;

    // Calculate day
    D = diff - MonthDayStart(M - 1, leap) + 1;
}

Funkcja może mieć kilka błędów (na przykład nie zadziałała, gdy N wynosiła 0).

Inne notatki

Mam nadzieję, że mój algorytm jest nadal poprawny, ponieważ dokonałem pewnych zmian w stosunku do oryginału dla tego pytania. Jeśli coś przeoczyłem lub coś było nie tak, daj mi znać, aby je zmodyfikować. I przepraszam za długie pytanie.