Sakamoto算法的正确性找到星期几

Question

我使用Sakamoto的算法来查找给定日期的星期几.谁能告诉我这个算法的正确性？我想从2000年到2099年.

维基百科的算法仅供参考.

int dow(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;
}

Answer 1

好吧,你可以通过查看它是正确的来判断......假设t[]阵列是正确的,你可以通过12次抽查来验证(每个月使用一天/每年一次).

这y -= m < 3是一个很好的技巧.它创建了一个"虚拟年",从3月1日开始,到2月28日(或29日)结束,将额外的一天(如果有的话)放在年底 ; 或者更确切地说,在去年年底.例如,2011年虚拟年度开始于3月1日,将于2月29日结束,而2012年虚拟年将于3月1日开始,并于次年2月28日结束.

通过在虚拟年度结束时添加闰年的日期,表达式的其余部分将大大简化.

让我们来看看总和:

(y + y/4 - y/100 + y/400 + t[m-1] + d) % 7

一年中有365天.那是52周加1天.因此,一般情况下,一周中的某一天每天都会改变一天.这就是该y术语的贡献; 它每年增加一个.

但每四年都是闰年.那些人每四年额外一天.由于使用虚拟年份,我们可以添加y/4总和来计算多y少年中发生的闰日.(注意,此公式假设整数除法向下舍入.)

但这不太对,因为每100年不是闰年.所以我们必须减去y/100.

除了每400年再次闰年.所以我们必须补充一下y/400.

最后,我们只是添加月份的日期d和表格的偏移量,该表格取决于月份(因为一年中的月份边界相当随意).

然后拿整个mod 7,因为这是一周多长.

(例如,如果周数为8天,那么这个公式会有什么变化？嗯,显然是mod 8.还y需要5*y,因为365%8 == 5.月表t[]也需要调整.而已.)

顺便提一下,维基百科声称日历"好到9999"是完全随意的.无论是10年,100年,1000年还是100万年,我们坚持使用公历,这个公式都是好的.

[编辑]

上述论点基本上是归纳的证据.也就是说,假设公式适用于特定的(y,m,d),则证明它适用于(y + 1,m,d)和(y,m,d + 1).(其中y是从3月1日开始的"虚拟年份".)因此关键问题是,当您从一年移动到下一年时,总和是否会改变正确的金额？有了闰年规则的知识,并且"虚拟年"在年末有额外的一天,这很简单.