将天数转换为年（包括闰年）的有效算法 [英] Efficient algorithm for converting number of days to years (including leap years)
问题描述
我正在写一个用于在c ++中保存日期的类，我发现了以下问题：
I am writing a class for holding dates in c++, and I found the following problem:
自从参考日期（在我的案例中为0001年1月1日）之后，我有一些天 N ，包括自参考后过去的闰日天。 如何将此数字转换为一年 Y ，月 M 和日
I have a number of days N since a reference date (in my case that would be Jan 1, 0001 AD), including the leap days that passed since the reference day. How can I convert this number to a year Y, month M and day D efficiently?
我想尽可能高效地执行此操作，所以最好的实现显然会有O（1） ）复杂性。
I would like to do this as efficiently as possible, so the best implementation would obviously have O(1) complexity.
下一节将解释一些我已经学到的东西。
The next sections will explain some of the things I already learned.
要确定一年是否是闰年，有几个规则：
To determine if a year is leap or not, there are a few rules:
- 可以被4整除的年份是跳跃
- 例外情况：规则1：可以用100整除的年份不会跳跃
- 例外情况：可以用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;
}
一个有效的方法来计算一年之前的闰年是多少年：
An efficient method to calculate how many years are leap before an year would be:
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中减去这个数字。这将给我一年中的日子。
Calculating the month
Once I find the year, I can calculate how many days there are until the current year, and I can subtract this number from N. This will give me the day of the year.
保存每个月开始的日期表，我们可以轻松计算月份。我还创建了一个函数，如果年是跳跃，则该函数将添加1，并且该月大于或等于2。
Keeping a table with the day number on which every month starts, we can easily calculate the month. I also created a function which will add 1 if the year is leap, and the month is greater or equal to 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];
}
我的想法
我的算法很复杂，它看起来像这样：
My idea
My algorithm is pretty complicated, and it looks like this:
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时）。
The function may have a few bugs (for example, it didn't work when N was 0).
我希望我的算法仍然正确，对于这个问题从原来的一些变化。如果我错过了什么，或者有什么问题，让我知道修改它。
I hope that my algorithm is still correct, because I made some changes from the original for this question. If I missed something, or something was wrong, let me know to modify it. And sorry for the long question.
推荐答案
这里有一些指针。注意：对于本练习，我假设当 N = 0 时， Y％400 == 0 。
Here are a few pointers. Note: For this exercise I will assume that when N=0 that Y % 400 == 0.
1：每400年期间有固定天数（400 * 365）+ 100 + 1 - 4 。
1: There are a fixed number of days in each 400 year period (400 * 365) + 100 + 1 - 4.
+100 是闰年， +1 是每400年的闰年， -4 是每100年没有闰年。
The +100 is for the leap years, the +1 is for the leap year every 400 years and the -4 is for not having a leap year every 100 years.
所以你的第一行代码是：
So your first line of code will be:
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日为一年的第一天
2: You can make your life a great deal easier if you treat March 1st as the first day of the year
3：将（1）可以工作一年。记住，每四个世纪开始一个闰年。因此，您可以使用以下内容完成年度计算：
3: Adding to the code in (1), we can work out the year. Bear in mind that every fourth century begins with a leap year. So you can complete the calculation of the year with the following:
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：现在您已经整理出年份，
4: Now you've sorted out the years, the rest is easy as pie (just remember (2), and the process is easy).
此外，您也可以使用的boost ::日期
这篇关于将天数转换为年（包括闰年）的有效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
