Вопросы Теги

Эффективный алгоритм преобразования количества дней в годы (, включая високосные годы)

Проблема

Я пишу класс для хранения дат на С++ и обнаружил следующую проблему:

У меня есть количество дней Nс контрольной даты (, в моем случае это будет 1 января 0001 года нашей эры ), включая високосные дни, прошедшие с контрольного дня. Как я могу эффективно преобразовать это число в год Y, месяц Mи день D?

Я хотел бы сделать это максимально эффективно, поэтому наилучшая реализация, очевидно, будет иметь сложность O (1 ).

Следующие разделы объяснят некоторые вещи, которые я уже изучил.

Високосные годы

Чтобы определить, високосный год или нет, есть несколько правил:

  1. Годы, которые делятся на 4, являются високосными
  2. . Исключение из правила 1 :Годы, которые делятся на 100, не являются високосными
  3. Исключение из правила 2 :Годы, которые делятся на 400, являются високосными

. Это будет переведено в такой код:

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

Эффективным методом подсчета количества лет, предшествующих году, является:

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

Вычисление месяца

Как только я найду год, я могу подсчитать, сколько дней осталось до текущего года, и я могу вычесть это число из N. Это даст мне день года.

Имея таблицу с номером дня, с которого начинается каждый месяц, мы можем легко вычислить месяц. Я также создал функцию, которая будет добавлять 1, если год високосный, а месяц больше или равен 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];
}

Моя идея

Мой алгоритм довольно сложен, и выглядит он так:

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

Функция может иметь несколько ошибок (, например, она не работала, когда N было равно 0 ).

Другие примечания

Я надеюсь, что мой алгоритм все еще верен, потому что я сделал некоторые изменения по сравнению с оригиналом для этого вопроса. Если я что-то пропустил или что-то было не так, дайте мне знать, чтобы изменить это. И извините за длинный вопрос.

12
задан Tibi 23 July 2012 в 09:39
поделиться