巧算星期几

基姆。拉尔森

基姆拥有计算机学科的博士学位。他对数据库，算法和数据结构有着浓厚的兴趣。他的联系地址是            （原文为丹麦文－－译者注） 31，DK－5270，Odense N,Denmark,或发 E-mail 至 :kslarsen@imada.ou.dk。

简介

布鲁斯 施耐尔

 

“四，六，九，十一，三十天就齐……”儿歌是这么唱的；或许你也曾经掰着手指头翻来覆去地数，让赶上单数的指头代表只有30天的短月吧？这样的口诀对我们是很管用的（我就是念叨着这首傻乎乎的儿歌长大的），可是电脑就没有这份“灵感”了。当然，我们可以用一大堆IF－THEN－ELSES的语句或几个CASE来编写计算程序，让它计算某个指定日期是星期几。

 

不过我更喜欢基姆拉尔森在本月的“算法小径”中为我们带来的新技巧，因为他的方法另辟蹊径，从一个全新的方向着手解决日期计算的问题。其实，并没有什么数学公式能算出某个指定日期是星期几，不过我们可以试着拼凑一个，如果我们的尝试成功了，你就能拥有一个易于编程的数学公式，并能用它自动计算哪天是星期几了。

 

顺便说一句，如果你已经设计出更巧妙的算法，或是在已有的方法上有了新突破的话，不妨告诉我，我一定洗耳恭听。我的联系方法是schneier@chinet.com，或者在DJJ编辑部给我留张便条就行。

 

你有没有疑惑过你的电脑怎么就知道今天是星期三呢？就算你的电脑关机了，你重启后设定了新日期，它也能立即知道这天是星期几。

 

在你还是个孩子的时候，你可能见过一种纪录记录着年，月，日的表格，只要加上几个数字，和它相连的另一张表格就会告诉你这个日期是星期几。当然，计算机硬盘的操作系统里也可以加入这样的计算表。不过有一种简单的方法可以轻松地算出某天是星期几；而且这个方法只占用很少的内存空间，而那些只能推算几百年的表格可就太占地方了。

 

如果目前你的电脑还不具备推算与日期对应的星期数的功能，现在就不妨在自己的程序中试试下面的公式。

 

 

创建公式

 

首先，我们要用变量D，M和Y来表示日期。比如，1994年3月1日就用“D＝1，M＝3，Y＝4”记录。我们的目标是让计算结果在0到6之间。0代表星期一，1代表星期二，2代表星期三，依此类推。

 

1994年3月1日是个星期二，那么“D mod 7(日期变量除以7的余数）)))”这个公式对于整个三月份都有效。比如3月18日是星期五，18 mod 7＝4；而4正代表星期五。别忘了，整数的除法和求模有着密切的关系。比方说，26除以7商3余5，这就是说，26除以7商数取整等于3，而26除以7求模（简写为26 mod 7）等于5。以上这些意味着19 mod 7=12 mod 7= 5 mod 7=5。在运算规则中，负数求模运算法相似，所以依此类推，-2 mod 7=5, -9 mod 7=5。

 

在更正式的表达法中，统一用任意整数n和k表达上述关系，那么这个过程可以表达为n=qk+r，这里的q和r的取值范围同样是整数和0。表1中列出了所有月份的变换数据（shift information此处试译为“档级数据”，还请进一步校对－－译者注）。为了尽可能地得出规律，二月被排在最后，同理，一月也是如此。

 

例1（a）中的公式是仿照表1中的变换数据栏所描述的模式而创建的。这个公式中的除法一律是商数取整。所以得数是最接近真正商数的整数。表2得出了此功能得出的有趣的数值。凭直觉，我们不难发现，当M(代表月份的变量)的值以1为单位递增时，2M就成倍增长，而3(M+1)/5就以3/5为增长倍数。

 

这正是我们仿制3,2,3,2,3这个重复格式所需要的（表中右边的弯括号表明了这一点）。请注意，我们在以7为除数求模，那么从6到2的求模结果就会逐个增加3（顺序是6,0,1,2）。

 

现在，我们发现了适用于逐月向下推算的校正方法，并希望把它加入刚才的尝试中，就是那个mod7公式。还以1994年3月1日为例，这个日期的M＝3。请注意，在例1（b）中，8 mod 7＝1，所以当整个公式合并时，必须减去1。在做以7为除数求模的运算时，减1和加6是一样的，因为-1 mod 7=6 mod 7=6。

 

这样，例1（c）中的公式就可以计算这一年中剩下的月份了。其实，既然我们把一月和二月排在表1的最后，那么只要我们把它们看成是十三月和十四月，就能接着推算1995年的前两个月了。这是因为，虽然它们并不是一个完整的3,2,3,2,3结构，但恰好可以是这个结构的开始，为了使这个公式更完善，我们还是最好把一月和二月看成是上一年的十三月和十四月。

 

 

加入年份

 

顺着年份向下找，我们观察到1995年3月1日是星期三。这说明，每增加一年，我们公式的计算结果就会增加1。这太简单了，我们只要简单地把年份加上去就行了。再提醒你一次，我们必须确保出发点是正确的。由于1994 mod 7=6，我们在把Y加入已有的公式时就必须减去6。由此改进的例2(a)就更完善了。

 

1996年是个闰年，这带来了我们的下一个问题。这一年的3月1日是星期五，而不是刚才的公式推算出的星期四。所以每当我们碰上闰年时还得多加上1。判断闰年的规则是，能被4整除，并能被100和400同时整除的年份就是闰年。就这样，我们在原有的基础上添加Y/4--Y/100+Y/400。再强调一下，我们必须从一开始就确保正确。既然(1994/4--1994/100+1994/400) mod 7=(498--19+4) mod 7=483 mod 7=0,所以就不用再做任何调整了。这样，例2(b)就是我们最终的成果了。这个公式能一直工作下去，除非改变现行的日历系统。作为示例，让我们试着推算一下2000年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，所以那一天是星期二。

 

这个公式还能推算过去的日期；然而计算范围有限，让我们看看1752年9月14号这个星期四吧，我们的公式最远只能推算到这里了。不过像“1963年11月22日你在哪里”这样的日常问题中提到的日期还是可以轻松应对的：(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是一个C语言程序，按照把这个公式自动推算给定日期是星期几。

 

 

 

表1：每月变换数据

月份         天数         变换

三月          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：仿制变换数据形式的功能。例1中建立的公式可以适用于1994年。例2把这个公式的功能扩展到可以应用在不同的年份进行推算。

 

例3：用C语言程序表达上述公式

/*计算指定日期是星期几。默认输入的*/

/*数字代表正确的日期*/

/* 推算给定日期是星期几，假定输入是正确的数据 */
#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]);
}

 

 

/*一月和二月被当作前一年的*/

/*十三月和十四月分别处理*/