演算法系列之十七：日曆生成演算法

05-28

【接上篇】

上述計算星期的方法雖然步驟簡單，但是每次都要計算兩個日期的時間差，不是非常方便。如果能夠有一個公式可以直接根據日期計算出對應的星期豈不是更好？幸運的是，這樣的公式是存在的。此類公式的推導原理仍然是通過兩個日期的時間差來計算星期，只是通過選擇一個特殊的日期來簡化公式的推導。這個所謂的特殊日期指的是某一年的12月31日這天剛好是星期日這種情況。選擇這樣的日子有兩個好處，一個是計算上可以省去計算標準日期這一年的剩餘天數，另一個是計算出來的日期差餘數是幾就是星期幾，不需要再計算星期的差值。人們知道公元元年的1月1日是星期一，那麼公元前1年的12月31日就是星期日，用這一天作為標準日期，就可以只計算整數年的時間和日期所在的年積累的天數，這個星期公式就是：

w = (L * 366 + N * 365 + D) % 7 (公式 2)

公式中的L是從公元元年到y年m月d日所在的年之間的閏年次數，N是平常年次數，D是y年內的積累天數。將整年數y - 1 = L + N帶入上式，可得：

w = ( (y - 1) * 365 + L + D) % 7 (公式 3)

根據閏年規律，從公元元年到y年之間的閏年次數是可以計算出來的，即：

將L帶入公式2，得到星期w的最終計算公式：

還以2005年5月31日為例，利用公式5計算w的值為：

得到2005年5月31日是星期二，和前面的計算方法得到的結果一致。根據上述分析，可得寫出使用公式5計算星期的演算法實現：

146 int TotalWeek(int year, int month, int day)

147 {

148 int d = CalcYearPassedDays(year, month, day);

149 int y = year - 1;

150 int w = y * DAYS_OF_NORMAL_YEAR + y / 4 - y / 100 + y / 400 + d;

151

152 return w % 7;

153 }

公式5的問題在於計算量大，不利於口算星期結果。於是人們就在公式5的基礎上繼續推導更簡單的公式。德國數學家克里斯蒂安·蔡勒（Christian Zeller, 1822- 1899）在1886年推導出了著名的為蔡勒（Zeller）公式：

對計算出的w值除以7，得到的餘數就是星期幾，如果餘數是0，則為星期日。蔡勒公式中各符號的含義如下：

w ：星期；

c ：世紀數 – 1的值，如21世紀，則 = 20；

m ：月數，的取值是大於等於3，小於等於14。在蔡勒公式中，某年的1月和2月看作上一年的13月和14月，比如2001年2月1日要當成2000年的14月1日計算；

y ：年份，取公元紀念的後兩位，如1998年， = 98，2001年， = 1；

d ：某月內的日數

為了方便口算，人們通常將公式6中的

一項改成

。目前人們普遍認為蔡勒公式是計算某一天是星期幾的最好的公式。但是蔡勒公式有時候可能計算出的結果是負數，需要對結果+7進行修正。比如2006年7月1日，用蔡勒公式計算出的結果是 -1，實際上這天是星期六。根據前面分析的結果整理出的蔡勒公式演算法實現如下：

155 int ZellerWeek(int year, int month, int day)

156 {

157 int m = month;

158 int d = day;

159

160 if(month <= 2) /*對小於2的月份進行修正*/

161 {

162 year--;

163 m = month + 12;

164 }

165

166 int y = year % 100;

167 int c = year / 100;

168

169 int w = (y + y / 4 + c / 4 - 2 * c + (13 * (m + 1) / 5) + d - 1) % 7;

170 if(w < 0) /*修正計算結果是負數的情況*/

171 w += 7;

172

173 return w;

174 }

蔡勒公式（公式6）和前面提到的公式5都只適用于格里曆法。羅馬教皇在1582年修改曆法，將10月5日指定為10月15日，從而正式廢止儒略曆法，開始啟用格里曆法。因此，上述求星期幾的公式只適用於1582年10月15日之後的日期，對於1582年將10月4日之前的日期，蔡勒也推導出了適用與儒略曆法的星期計算公式：

公式7適用於對1582年10月4日之前的日期計算星期，1582年10月5日與1582年10月15日之間的日期是不存在的，因為它們都是同一天。

格里曆曆法簡單，除二月外每月天數固定，二月則根據是否是閏年確定是28天還是29天，每天的星期數可以通過蔡勒公式（公式6）計算，有了這些信息，就可以按照一定的排版格式將某一年的日曆列印出來。排版列印的演算法非常簡單，就是按照順序列印12個月的月曆，因此，列印月曆的函數就是輸出演算法的重點。代碼沒什麼特別之處，就是用一些小技巧確定每個月的第一天的開始位置，列印月曆的核心代碼如下：

229 void PrintMonthCalendar(int year, int month)

230 {

231 int days = GetDaysOfMonth(year, month); /*確定這個月的天數*/

232 if(days <= 0)

233 return;

234

235 PrintMonthBanner(nameOfMonth[month - 1]);

236 PrintWeekBanner();

237 int firstDayWeek = ZellerWeek(year, month, 1);

238 InsertRowSpace(firstDayWeek);

239 int week = firstDayWeek;

240 int i = 1;

241 while(i <= days)

242 {

243 printf("%-10d", i);

244 if(week == 6) /*到一周結束，切換到下一行輸出*/

245 {

246 SetNextRowStart();

247 }

248 i++;

249 week = (week + 1) % 7;

250 }

251 }

GetDaysOfMonth()函數其實就是從daysOfMonth表中查一下每月的天數，如果是閏年，則對二月的天數修正（＋1），daysOfMonth表定義如下：

int daysOfMonth[MONTHES_FOR_YEAR] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

計算星期不必對每一天都計算一次，只要對每個月的第一天計算一次就可以了，以後的日期可以用 week = (week + 1) % 7 直接推算出星期幾。下面就是我們的演算法列印輸出的效果：

********************************************************************************

Calendar of 2012

********************************************************************************

----------January----------

Sunday Monday Tuesday Wednesday Thursday Friday Saturday

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28

29 30 31

----------February----------

Sunday Monday Tuesday Wednesday Thursday Friday Saturday

1 2 3 4

5 6 7 8 9 10 11

12 13 14 15 16 17 18

19 20 21 22 23 24 25

26 27 28 29

----------March----------

Sunday Monday Tuesday Wednesday Thursday Friday Saturday

1 2 3

4 5 6 7 8 9 10

11 12 13 14 15 16 17

18 19 20 21 22 23 24

25 26 27 28 29 30 31

……

小知識2：儒略曆和格里曆

在公元1582年10月15日之前，人們使用的曆法是源自古羅馬的儒略曆，儒略曆的置閏規則就是四年一閏，但是沒有計算每年多出來的0.0078天，這樣從公元前46年到公元1582年一共累積多出了10天，為此，當時的教皇格里十三世將1582年10月5日人為指定為10月15日，並開始啟用新的置閏規則，這就是後來沿用至今的格里曆。

小知識3：約化儒略日

由於儒略日數字位數太多，國際天文聯合會於1973年8月決定對其修正，採用約化儒略日（MJD）進行天文計算，定義MJD = JD – 2400000.5，MJD相應的起始點是1858年11月17日 0:00。

小知識4：1752年9月到底是怎麼回事兒

如果你用的操作系統是unix或linux，在控制台輸入以下命令：

#cal 9 1752

你會看到這樣一個奇怪的月曆輸出：

September 1752

Su Mo Tu We Th Fr Sa

1 2 14 15 16

17 18 19 20 21 22 23

24 25 26 27 28 29 30

1752年的9月缺了11天，到底怎麼回事兒？這其實還是因為從儒略曆到格里曆的轉換造成的。1582年10月5日，羅馬教皇格里十三世宣布啟用更為精確的格里曆，但是整個歐洲大陸並不是所有國家都立即採用格里曆，比如大英帝國就是直到1752年9月議會才批准採用格里曆，所以大英帝國及其所有殖民地的曆法一直到1752年9月才發生跳變，「跟上」了格里曆。德國和荷蘭到了1698年才採用格里曆，而俄羅斯則直到1918年革命才採用格里曆。Linux的cal指令起源與最初AT&T的UNIX，當然採用的是美國曆法，但是美國歷史太短，再往前就只能採用英國曆法，所以cal指令的結果就成了這樣。對於採用格里曆的國家來說，只要知道1582年10月發生了日期跳變就行了，可以不用關心1752年9月到底是怎麼回事兒。但是對於研究歷史和考古的人來說，就必需要了解這個歷史，搞清楚每個歐洲國家改用格里曆的年份，否則就可能在一些問題上出錯。在歐洲研究歷史，你會發現很多事件都是有多個時間版本的，比如大科學家牛頓的生日就有兩個時間版本，一個是按照儒略曆曆法的1642年12月25日，另一個是格里曆曆法的1643年1月4日，對於英國人來說，1752年之前都是按照儒略曆計算的，所以英國的史書可能會記載牛頓出生在聖誕節，這也沒什麼可奇怪的。