将天数转换为年数(包括闰年)的高效算法

Question

问题

我正在编写一个用c ++保存日期的类,我发现了以下问题:

我N自参考日期(在我的情况下将是公元0001年1月1 日)以来有多天,包括自参考日以来经过的闰日.我怎么能转换这个数字到一年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时它不起作用).

其他说明

我希望我的算法仍然正确,因为我对这个问题做了一些改动.如果我错过了什么,或者出了什么问题,请告诉我修改它.抱歉这个长期的问题.

Answer 1

要使用一个老笑话的妙语,"我不会从这里开始".

你会想要在"现代"时代之前阅读有关日历的各种变化,例如,1752年发生的事情

Answer 2

这里有一些提示。注意：对于这个练习，我将假设N=0当Y % 400 == 0.

1：每400年有固定的天数(400 * 365) + 100 + 1 - 4。

是+100闰年， 是+1每 400 年有一次闰年， 是-4每 100 年没有闰年。

所以你的第一行代码将是：

GetDate(int N, int &Y, int &M, int &D) {
  const int DAYS_IN_400_YEARS = (400*365)+97;
  int year = (N / DAYS_IN_400_YEARS) * 400;
  N = N % DAYS_IN_400_YEARS;

2：如果你把 3 月 1 日当作一年的第一天，你的生活就会轻松很多

3：加上(1)中的代码，我们可以算出年份。请记住，每第四个世纪都会以闰年开始。因此，您可以使用以下命令完成年份的计算：

  const int DAYS_IN_100_YEARS = (100*365) + 24;
  year += 100 * (N / DAYS_IN_100_YEARS) + (N < DAYS_IN_100_YEARS ? 1 : 0); // Add an extra day for the first leap year that occurs every 400 years.
  N = N - (N < DAYS_IN_100_YEARS ? 1 : 0);
  N = N % DAYS_IN_400_YEARS;

4：现在你已经整理好了年份，剩下的就很简单了（只要记住（2），过程就很简单）。

或者，您可以使用boost::date。