星期数计算算法(一) - Sakamoto算法

内容同步于我的博客：https://blog.bigrats.net/archives/sakamoto-algorithm.html

算法代码

int dayofweek(int y, int m, int d)
{
    static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
    y -= m < 3;
    return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}

原理及推导

首先，1年1月1日为星期w0，由于365 = 527 + 1，366 = 527+2，因此每过一个平年，对应日期的星期数便加1，每过一个闰年，3月前对应日期的星期号递增1，3月开始对应日期的星期号递增2。

一、假设我们计算y年1月1日的星期数

（1）我们首先计算一共有多少个闰年：因为每四年有一个闰年，同时考虑到能被100整除但不能被400整除的年份不是闰年，因此从1年到y年一共有y/4 - y/100 + y/400个闰年

（2）因此我们可以得到y年1月1日的星期数计算方法：（其中H为一个修正常数）

if(isLeap(y)){
    w = (y + y/4 - y/100 + y/400 - 1 + H) % 7;
    // 因为1月1日在3月前，因此当y为闰年时，计算的天数增值多了1，我们把它减去
else {
    w = (y + y/4 - y/100 + y/400 + H) % 7;
}

二、接下来我们来计算y年m月d日的星期数

（1）由于我们已经得到了y年1月1日的星期数，我们只需算出m月d日相对于1月1日的天数增值即可计算的y年m月d日的星期数。

对于平年：deltaDays_noleap[12] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}

对于闰年：deltaDays_leap[12] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335}

模7取余数后为：

deltaWofMonth_noleap[12] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};
deltaWofMonth_leap[12] = {0, 3, 4, 0, 2, 5, 7, 3, 6, 1, 4, 6};

（2）从而我们得到了y年m月d日的星期数计算方法：

if(isLeap(y)){
    w = (y + y/4 - y/100 + y/400 - 1 + deltaWofMonth_leap[m - 1] + d + H) % 7;
else {
    w = (y + y/4 - y/100 + y/400 + deltaWofMonth_noleap[m - 1] + d + H) % 7;
}

（3）我们发现，在3月以后，实际有：deltaWofMonth_noleap[i] % 7 == (deltaWofMonth_leap[i] - 1) % 7

因此我们可以仅采用平年的deltaWofMonth_noleap，得到计算方法如下：

if(isLeap(y)){
    if(m < 3){
        w = (y + y/4 - y/100 + y/400 - 1 + deltaWofMonth_noleap[m - 1] + d + H) % 7;
    } else {
        w = (y + y/4 - y/100 + y/400  + deltaWofMonth_noleap[m - 1] + d + H) % 7;
    }
else {
    w = (y + y/4 - y/100 + y/400 + deltaWofMonth_noleap[m - 1] + d + H) % 7;
}

可以合并简化为：

if(m < 3 && isLeap(y)) {
    w = (y + y/4 - y/100 + y/400 - 1 + deltaWofMonth_noleap[m - 1] + d + H) % 7;
}else {
    w = (y + y/4 - y/100 + y/400  + deltaWofMonth_noleap[m - 1] + d + H) % 7;
}

（4）现在来进一步简化算法，当m < 3时，令y = y – 1，则有：当y为闰年时，y + y/4 - y/100 + y/400减少了2，当y为平年时，y + y/4 - y/100 + y/400减少了1。因此，算法可以简化为：

if(m < 3) {
    y--;
    w = (y + y/4 - y/100 + y/400 + 1 + deltaWofMonth_noleap[m - 1] + d + H) % 7;
} else {
    w = (y + y/4 - y/100 + y/400 + deltaWofMonth_noleap[m - 1] + d + H) % 7;
}

修改deltaWofMonth，其中，1月和2月不变，将3月之后的所有月的数值减1后模7，得到：

deltaW = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};

从而代码简化为：

y -= (m < 3);
w = (y + y/4 - y/100 + y/400 + deltaW[m - 1] + d + H + 1) % 7;

（5）经过调试，得到修正常数H = 6，因此得到算法如下：

int dayofweek(int y, int m, int d)
{
    static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
    y -= m < 3;
    return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}

三、一些说明

由于目前使用的历法并不是从1年1月1日开始使用的，而是从1582年年底才开始使用的格利戈里历，并且在1582年不存在10月5日到10月14日这10天，因此此算法只能准确计算1582年10月15日开始之后的星期数。