巧算星期幾

基姆。拉爾森

基姆擁有計(jì)算機(jī)學(xué)科的博士學(xué)位。他對(duì)數(shù)據(jù)庫(kù)，算法和數(shù)據(jù)結(jié)構(gòu)有著濃厚的興趣。他的聯(lián)系地址是??????????? （原文為丹麥文－－譯者注） 31，DK－5270，Odense N,Denmark,或發(fā) E-mail 至 :kslarsen@imada.ou.dk。

簡(jiǎn)介

布魯斯 施耐爾

?

“四，六，九，十一，三十天就齊……”兒歌是這么唱的；或許你也曾經(jīng)掰著手指頭翻來(lái)覆去地?cái)?shù)，讓趕上單數(shù)的指頭代表只有30天的短月吧？這樣的口訣對(duì)我們是很管用的（我就是念叨著這首傻乎乎的兒歌長(zhǎng)大的），可是電腦就沒(méi)有這份“靈感”了。當(dāng)然，我們可以用一大堆IF－THEN－ELSES的語(yǔ)句或幾個(gè)CASE來(lái)編寫(xiě)計(jì)算程序，讓它計(jì)算某個(gè)指定日期是星期幾。

?

不過(guò)我更喜歡基姆拉爾森在本月的“算法小徑”中為我們帶來(lái)的新技巧，因?yàn)樗姆椒肀脔鑿剑瑥囊粋€(gè)全新的方向著手解決日期計(jì)算的問(wèn)題。其實(shí)，并沒(méi)有什么數(shù)學(xué)公式能算出某個(gè)指定日期是星期幾，不過(guò)我們可以試著拼湊一個(gè)，如果我們的嘗試成功了，你就能擁有一個(gè)易于編程的數(shù)學(xué)公式，并能用它自動(dòng)計(jì)算哪天是星期幾了。

?

順便說(shuō)一句，如果你已經(jīng)設(shè)計(jì)出更巧妙的算法，或是在已有的方法上有了新突破的話，不妨告訴我，我一定洗耳恭聽(tīng)。我的聯(lián)系方法是schneier@chinet.com，或者在DJJ編輯部給我留張便條就行。

?

你有沒(méi)有疑惑過(guò)你的電腦怎么就知道今天是星期三呢？就算你的電腦關(guān)機(jī)了，你重啟后設(shè)定了新日期，它也能立即知道這天是星期幾。

?

在你還是個(gè)孩子的時(shí)候，你可能見(jiàn)過(guò)一種紀(jì)錄記錄著年，月，日的表格，只要加上幾個(gè)數(shù)字，和它相連的另一張表格就會(huì)告訴你這個(gè)日期是星期幾。當(dāng)然，計(jì)算機(jī)硬盤(pán)的操作系統(tǒng)里也可以加入這樣的計(jì)算表。不過(guò)有一種簡(jiǎn)單的方法可以輕松地算出某天是星期幾；而且這個(gè)方法只占用很少的內(nèi)存空間，而那些只能推算幾百年的表格可就太占地方了。

?

如果目前你的電腦還不具備推算與日期對(duì)應(yīng)的星期數(shù)的功能，現(xiàn)在就不妨在自己的程序中試試下面的公式。

?

?

創(chuàng)建公式

?

首先，我們要用變量D，M和Y來(lái)表示日期。比如，1994年3月1日就用“D＝1，M＝3，Y＝4”記錄。我們的目標(biāo)是讓計(jì)算結(jié)果在0到6之間。0代表星期一，1代表星期二，2代表星期三，依此類推。

?

1994年3月1日是個(gè)星期二，那么“D mod 7(日期變量除以7的余數(shù)）)))”這個(gè)公式對(duì)于整個(gè)三月份都有效。比如3月18日是星期五，18 mod 7＝4；而4正代表星期五。別忘了，整數(shù)的除法和求模有著密切的關(guān)系。比方說(shuō)，26除以7商3余5，這就是說(shuō)，26除以7商數(shù)取整等于3，而26除以7求模（簡(jiǎn)寫(xiě)為26 mod 7）等于5。以上這些意味著19 mod 7=12 mod 7= 5 mod 7=5。在運(yùn)算規(guī)則中，負(fù)數(shù)求模運(yùn)算法相似，所以依此類推，-2 mod 7=5, -9 mod 7=5。

?

在更正式的表達(dá)法中，統(tǒng)一用任意整數(shù)n和k表達(dá)上述關(guān)系，那么這個(gè)過(guò)程可以表達(dá)為n=qk+r，這里的q和r的取值范圍同樣是整數(shù)和0。表1中列出了所有月份的變換數(shù)據(jù)（shift information此處試譯為“檔級(jí)數(shù)據(jù)”，還請(qǐng)進(jìn)一步校對(duì)－－譯者注）。為了盡可能地得出規(guī)律，二月被排在最后，同理，一月也是如此。

?

例1（a）中的公式是仿照表1中的變換數(shù)據(jù)欄所描述的模式而創(chuàng)建的。這個(gè)公式中的除法一律是商數(shù)取整。所以得數(shù)是最接近真正商數(shù)的整數(shù)。表2得出了此功能得出的有趣的數(shù)值。憑直覺(jué)，我們不難發(fā)現(xiàn)，當(dāng)M(代表月份的變量)的值以1為單位遞增時(shí)，2M就成倍增長(zhǎng)，而3(M+1)/5就以3/5為增長(zhǎng)倍數(shù)。

?

這正是我們仿制3,2,3,2,3這個(gè)重復(fù)格式所需要的（表中右邊的彎括號(hào)表明了這一點(diǎn)）。請(qǐng)注意，我們?cè)谝?為除數(shù)求模，那么從6到2的求模結(jié)果就會(huì)逐個(gè)增加3（順序是6,0,1,2）。

?

現(xiàn)在，我們發(fā)現(xiàn)了適用于逐月向下推算的校正方法，并希望把它加入剛才的嘗試中，就是那個(gè)mod7公式。還以1994年3月1日為例，這個(gè)日期的M＝3。請(qǐng)注意，在例1（b）中，8 mod 7＝1，所以當(dāng)整個(gè)公式合并時(shí)，必須減去1。在做以7為除數(shù)求模的運(yùn)算時(shí)，減1和加6是一樣的，因?yàn)?1 mod 7=6 mod 7=6。

?

這樣，例1（c）中的公式就可以計(jì)算這一年中剩下的月份了。其實(shí)，既然我們把一月和二月排在表1的最后，那么只要我們把它們看成是十三月和十四月，就能接著推算1995年的前兩個(gè)月了。這是因?yàn)?，雖然它們并不是一個(gè)完整的3,2,3,2,3結(jié)構(gòu)，但恰好可以是這個(gè)結(jié)構(gòu)的開(kāi)始，為了使這個(gè)公式更完善，我們還是最好把一月和二月看成是上一年的十三月和十四月。

?

?

加入年份

?

順著年份向下找，我們觀察到1995年3月1日是星期三。這說(shuō)明，每增加一年，我們公式的計(jì)算結(jié)果就會(huì)增加1。這太簡(jiǎn)單了，我們只要簡(jiǎn)單地把年份加上去就行了。再提醒你一次，我們必須確保出發(fā)點(diǎn)是正確的。由于1994 mod 7=6，我們?cè)诎裏加入已有的公式時(shí)就必須減去6。由此改進(jìn)的例2(a)就更完善了。

?

1996年是個(gè)閏年，這帶來(lái)了我們的下一個(gè)問(wèn)題。這一年的3月1日是星期五，而不是剛才的公式推算出的星期四。所以每當(dāng)我們碰上閏年時(shí)還得多加上1。判斷閏年的規(guī)則是，能被4整除，并能被100和400同時(shí)整除的年份就是閏年。就這樣，我們?cè)谠械幕A(chǔ)上添加Y/4--Y/100+Y/400。再?gòu)?qiáng)調(diào)一下，我們必須從一開(kāi)始就確保正確。既然(1994/4--1994/100+1994/400) mod 7=(498--19+4) mod 7=483 mod 7=0,所以就不用再做任何調(diào)整了。這樣，例2(b)就是我們最終的成果了。這個(gè)公式能一直工作下去，除非改變現(xiàn)行的日歷系統(tǒng)。作為示例，讓我們?cè)囍扑阋幌?000年7月4日：(4+2*3+(7+1)/5+2000+2000/4--2000/100+2000/400) mod 7= (4+14+2000+500--20+5) mod 7=2507 mod 7=1，所以那一天是星期二。

?

這個(gè)公式還能推算過(guò)去的日期；然而計(jì)算范圍有限，讓我們看看1752年9月14號(hào)這個(gè)星期四吧，我們的公式最遠(yuǎn)只能推算到這里了。不過(guò)像“1963年11月22日你在哪里”這樣的日常問(wèn)題中提到的日期還是可以輕松應(yīng)對(duì)的：(22+2*11+3(11+1)/5+1963+1963/4--1963/100+1963/400) mod 7=(22+22+7+1963+490--19+4) mod 7=2489 mod 7=4。那天就是星期五。

?

例3例子3是一個(gè)C語(yǔ)言程序，按照把這個(gè)公式自動(dòng)推算給定日期是星期幾。

?

?

?

表1：每月變換數(shù)據(jù)

月份???????? 天數(shù)???????? 變換

三月????????? 31??????????? 3

四月????????? 30??????????? 2

五月????????? 31??????????? 3

六月????????? 30??????????? 2

七月????????? 31??????????? 3

八月????????? 31??????????? 3

九月????????? 30??????????? 2

十月????????? 31??????????? 3

十一月??????? 30??????????? 2

十二月??????? 31??????????? 3

一月????????? 31??????????? 3

二月????????? 28??????????? 3

?

?

?

表2：仿制變換數(shù)據(jù)形式的功能。例1中建立的公式可以適用于1994年。例2把這個(gè)公式的功能擴(kuò)展到可以應(yīng)用在不同的年份進(jìn)行推算。

?

例3：用C語(yǔ)言程序表達(dá)上述公式

/*計(jì)算指定日期是星期幾。默認(rèn)輸入的*/

/*數(shù)字代表正確的日期*/

/* 推算給定日期是星期幾，假定輸入是正確的數(shù)據(jù) */
#include
char *name[] = { "Monday",
???????????????? "Tuesday",
???????????????? "Wednesday",
??????????????? "Thursday",
??????????????? "Friday",
??????????????? "Saturday",
??????????????? "Sunday"
?????????????? };
void main(){
? int D,M,Y,A;
? printf("Day: "); fflush(stdout);
? scanf("%d",&D);
? printf("Month: "); fflush(stdout);
? scanf("%d",&M);
? printf("Year: "); fflush(stdout);
? scanf("%d",&Y);
/* January and February are treated as month 13 and 14, */
/* respectively, from the year before.????????????????? */
? if ((M == 1) || (M == 2)){
??? M += 12;
??? Y--;
? }
? A = (D + 2*M + 3*(M+1)/5 + Y + Y/4 - Y/100 + Y/400) % 7;
? printf("It's a %s.\n",name[A]);
}

?

?

/*一月和二月被當(dāng)作前一年的*/

/*十三月和十四月分別處理*/

?

?
?
?