算法系列之十七：日历生成算法-中国公历（格里历）（上）
日历在我们的生活中扮演着十分重要的角色，上班、上学、约会都离不开日历。每年新年开始，人们都要更换新的日历，你想知道未来一年的这么多天是怎么被确定下来的吗？为什么去年的国庆节是星期五而今年的国庆节是星期三？那就来研究一下日历算法吧。本文将介绍日历的编排规则，确定某日是星期几的计算方法，以及如何在计算机上打印某一年的年历。
要研究日历算法，首先要知道日历的编排规则，也就是历法。所谓历法，指的就是推算年、月、日的时间长度和它们之间的关系，指定时间序列的法则。我国的官方历法是中国公历，也就是世界通用的格里历（Gregorian Calendar），中国公历的年分为平常年和闰年，平常年一年是365天，闰年一年是366天。判定一年是平常年还是闰年的规则如下：
1、 如果年份是4的倍数，且不是100的倍数，则是闰年；
2、 如果年份是400的倍数，则是闰年；
3、 不满足1、2条件的就是平常年。
总结成一句话就是：四年一闰，百年不闰，四百年再闰。
中国公历关于月的规则是这样的，一年分为十二个月，其中一月、三月、五月、七月、八月、十月和十二月是大月，一个月有31天。四月、六月、九月和十一月是小月，一个月有30天。二月天数要根据是否是闰年来定，如果是闰年，二月是29天，如果是平常年，二月是28天。
除了年月日，人们日常生活中还对日期定义了另一个属性，就是星期几。星期并不是公历范畴内的东西，但是人们已经习惯用星期来管理和规划时间，比如一个星期工作五天，休息两天等等，星期的规则彻底改变了人们的生活习惯，因此星期已经成为历法中的一部分了。星期的命名最早起源于古巴比伦文化。公元前7－6世纪，巴比伦人就使用了星期制，一个星期中的每一天都有一个天神掌管。这一规则后来传到古罗马，并逐渐演变成现在的星期制度。
如何知道某一天到底是星期几？除了查日历之外，是否有办法推算出来某一天是星期几呢？答案是肯定的，星期不象年和月那样有固定的历法规则，但是星期的计算也有自己的规律。星期是固定的7天周期，其排列顺序固定，不随闰年、平常年以及大小月的天数变化影响。因此，只要确切地知道某一天是星期几，就可以推算出其它日期是星期几。推算的方法很简单，就是计算两个日期之间相差多少天，用相差的天数对7取余数，这个余数就是两个日期的星期数的差值。举个例子，假设已经知道1977年3月27日是星期日，如何得知1978年3月27日是星期几？按照前面的方法，计算出1977年3月27日到1978年3月27日之间相差365天，365除以7余数是1，所以1978年3月27日就是星期一。
上述方法计算星期几的关键是求出两个日期之间相隔的天数。有两种常用的方法计算两个日期之间相隔的天数，一种是利用公历的月和年的规则直接计算，另一种是利用儒略日计算。利用公历规则直接计算两个日期之间相差的天数，简单地讲就是将两个日期之间相隔的天数分成三个部分：前一个日期所在年份还剩下的天数、两个日期之间相隔的整数年所包含的天数和后一个日期所在的年过去的天数。如果两个日期是相邻两个年份的日期，则第二部分整年的天数就是0。以1977年3月27日到2005年5月31日为例，1977年还剩下的天数是279天，中间整数年是从1978年到2005年（不包括2005年），共26年，包括7个闰年和20个平常年，总计9862天，最后是2005年从1月1日到5月31日经过的天数151天。三者总结10292天。直接利用公历规则计算日期相差天数的算法实现如下（为了简化算法复杂度，这个实现假设用于定位星期的那个日期总是在需要计算星期几的那个日期之前）：
99 int CalculateDays(int ys, int ms, int ds, int ye, int me, int de)
100 {
101 int days = CalcYearRestDays(ys, ms, ds);
102
103 if(ys != ye) /*不是同一年的日期*/
104 {
105 if((ye - ys) >= 2) /*间隔超过一年，要计算间隔的整年时间*/
106 {
107 days += CalcYearsDays(ys + 1, ye);
108 }
109 days += CalcYearPassedDays(ye, me, de);
110 }
111 else
112 {
113 days = days - CalcYearRestDays(ye, me, de);
114 }
115
116 return days;
117 }
43 /*计算一年中过去的天数，包括指定的这一天*/
44 int CalcYearPassedDays(int year, int month, int day)
45 {
46 int passedDays = 0;
47
48 int i;
49 for(i = 0; i < month - 1; i++)
50 {
51 passedDays += daysOfMonth[i];
52 }
53
54 passedDays += day;
55 if((month > 2) && IsLeapYear(year))
56 passedDays++;
57
58 return passedDays;
59 }
60
61 /*计算一年中还剩下的天数，不包括指定的这一天*/
62 int CalcYearRestDays(int year, int month, int day)
63 {
64 int leftDays = daysOfMonth[month - 1] - day;
65
66 int i;
67 for(i = month; i < MONTHES_FOR_YEAR; i++)
68 {
69 leftDays += daysOfMonth[i];
70 }
71
72 if((month <= 2) && IsLeapYear(year))
73 leftDays++;
74
75 return leftDays;
76 }
77
78 /*
79 计算years年1月1日和yeare年1月1日之间的天数，
80 包括years年1月1日，但是不包括yeare年1月1日
81 */
82 int CalcYearsDays(int years, int yeare)
83 {
84 int days = 0;
85
86 int i;
87 for(i = years; i < yeare; i++)
88 {
89 if(IsLeapYear(i))
90 days += DAYS_OF_LEAP_YEAR;
91 else
92 days += DAYS_OF_NORMAL_YEAR;
93 }
94
95 return days;
96 }
另一种计算两个日期相差天数的方法是利用儒略日（Julian Day，JD）进行计算。首先介绍一下儒略日，儒略日是一种不记年，不记月，只记日的历法，是由法国学者Joseph Justus Scaliger（1540－1609）在1583年提出来的一种以天数为计量单位的流水日历。儒略日和儒略历（Julian Calendar）没有任何关系，命名为儒略日也仅仅他本人为了纪念他的父亲――意大利学者Julius Caesar Scaliger（1484－1558）。简单来讲，儒略日就是指从公元前4713年1月1日UTC 12:00开始所经过的天数，JD0就被指定为公元前4713年1月1日 12:00到公元前4713年1月2日12:00之间的24小时，依次顺推，每一天都被赋予一个唯一的数字。例如从1996年1月1日12:00开始的一天就是儒略日JD2450084。使用儒略日可以把不同历法的年表统一起来，很方便地在各种历法中追溯日期。如果计算两个日期之间的天数，利用儒略日计算也很方便，先计算出两个日期的儒略日数，然后直接相减就可以得到两个日期相隔的天数。
由公历的日期计算出儒略日数是一个很简单的事情，有多个公式可以计算儒略日，本文选择如下公式计算儒略日：
其中y是年份，m是月份，d是日期，如果m小于或等于2，则m修正为m+12，同时年份修正为y-1。c值由以下方法计算：
下面就是由公历日期计算儒略日的算法实现：
119 int CalculateJulianDay(int year, int month, int day)
120 {
121 int B = 0;
122
123 if(month <= 2)
124 {
125 month += 12;
126 year -= 1;
127 }
128 if(IsGregorianDays(year, month, day))
129 {
130 B = year / 100;
131 B = 2 - B + year / 400;
132 }
133
134 double dd = day + 0.5000115740; /*本日12:00后才是儒略日的开始(过一秒钟)*/
135 return int(365.25 * (year + 4716) + 0.01) + int(30.60001 * (month + 1)) + dd + B - 1524.5;
136 }
儒略日的计算通常精确到秒，得到的JD数也是一个浮点数，本文仅仅是为了计算日期相隔的整数天数，因此都采用整数计算。由于儒略日的周期开始与每天中午12:00，而历法中的天数通常是从0:00开始的，因此儒略日计算上对日期的天数进行了修正。1977年3月27日的儒略日是2443230，2005年5月31日的儒略日是2453522，差值是10292，和前一种方法计算的结果一致。
我们用两种方法计算出两个日期之间的天数都是10292，现在用10292除以7得到余数是2，也就是说2005年5月31日与1977年3月27日星期数差两天，所以2005年5月31日就是是星期二。
上述计算星期的方法虽然步骤简单，但是每次都要计算两个日期的时间差，不是非常方便。如果能够有一个公式可以直接根据日期计算出对应的星期岂不是更好？幸运的是，这样的公式是存在的，下篇将继续介绍公式法直接计算某一天星期数的算法。
小知识1：公历的闰年
中国公历（也就是格里历）的置闰规则是四年一闰，百年不闰，四百年再闰，为什么会有这么奇怪的置闰规则呢？这实际上与天体运行周期与人类定义的历法周期之间的误差有关。地球绕太阳运转的周期是365.2422天，即一个回归年（Tropical Year），而公历的一年是365天，这样一年就比回归年短了0.2422日，四年积累下来就多出0.9688天（约1天），于是设置一个闰年，这一年多一天。这样一来，四个公历年又比四个回归年多了0.0312天，平均每年多0.0078天，这样经过四百年就会多出3.12天，也就是说每四百年要减少3个闰年才行，于是就设置了百年不闰，四百年再闰的置闰规则。
实际上公历的置闰还有一条规则，就是对于数值很大的年份，如果能整除3200，同时能整除172800则是闰年。这是因为前面即使四百年一闰，仍然多了0.12天，平均就是每天多0.0003天，于是每3200年就又多出0.96天，也就是说每3200年还要减少一个闰年，于是能被3200整除的年就不是闰年了。然而误差并没有终结，每3200年减少一个闰年（减少一天）实际上多减了0.04天，这个误差还要继续累计计算，这已经超出了本文的范围，有兴趣的读者可以自己计算。
