Проблема
Я пишу класс для хранения дат в С++, и я нашел следующую проблему:
У меня есть количество дней N со ссылочной даты (в моем случае это будет 1 января 0001 г. н.э.), включая дни високосного перехода, прошедшие со дня ссылки. Как я могу преобразовать это число в год Y, месяц M и день D эффективно?
Я хотел бы сделать это максимально эффективно, поэтому наилучшая реализация, очевидно, будет иметь сложность O (1).
В следующих разделах рассказывается о некоторых вещах, которые я уже узнал.
Високосные годы
Чтобы определить, является ли год прыжком или нет, существует несколько правил:
- Годы, которые делятся на 4, являются прыжками
- Исключение к правилу 1: годы, делящиеся на 100, не являются прыжками.
- Исключение к правилу 2: годы, делящиеся на 400, являются прыжками
Это будет выглядеть так:
bool IsLeapYear(int year)
{
// Corrected after Henrick 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).
Другие примечания
Я надеюсь, что мой алгоритм все еще верен, потому что я внес некоторые изменения из оригинала для этого вопроса. Если я что-то пропустил или что-то не так, сообщите мне, чтобы изменить его. И извините за длинный вопрос.
