一尘不染

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

algorithm

我正在使用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;
}

阅读 200

收藏
2020-07-28

共1个答案

一尘不染

好吧,您可以通过查看它来判断它是正确的…假设t[]阵列是正确的,那么您只需进行12次抽查即可验证(每个月使用任何一天/每年一次)。

y -= m < 3是一个很好的技巧。它创建了一个“虚拟年”,从3月1日开始,到2月28日(或29)结束,并将多余的一天(如果有的话)放在 年底
。或者更确切地说,是在 上一
年末。因此,例如,虚拟年2011从3月1日开始,并将在2月29日结束,而虚拟年2012将在3月1日开始,并在随后的2月28日结束。

通过将添加的day年的日子放在虚拟年份的末尾,可以大大简化其余的表达式。

让我们看一下总和:

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

正常一年中有365天。那是52周加1天。因此,通常情况下,一周的日期每年每年偏移一天。这就是该y术语所起的作用;每年增加一天。

但是每四年是a年。这些人每四年增加一天的收入。由于使用了虚拟年份,我们可以将y/4总和加起来以计算y几年中发生了多少days日。(请注意,此公式假定整数除法轮
向下 )。

但这并不完全正确,因为每隔100年不是a年。所以我们必须减去y/100

除了每400年又是a年。因此,我们必须添加y/400

最后,我们只添加一个月中的某天d以及一个与该月相关的表的偏移量(因为一年中的月边界是相当任意的)。

然后把整个事情修改为7,因为那是一周的时间。

(例如,如果周是八天,那么此公式将发生什么变化?嗯,显然它将是mod8。另外,该值y也必须是5*y,因为365%8
==5。另外,月表t[]也需要调整。而已。)

顺便说一句,维基百科关于日历“直到9999才有效”的说法完全是任意的。无论我们坚持公历
10年,100年,1000年还是1百万年,此公式都适用。

[编辑]

以上论点实质上是归纳证明。也就是说, 假设 该公式适用于特定的(y,m,d),则 证明 该公式适用于(y + 1,m,d)和(y,m,d +
1)。(y是从3月1日开始的“虚拟年份”。)所以关键的问题是,当您从一年移到下一年时,金额是否会以正确的金额变化?有了year年规则的知识,并且“虚拟年”在年底有额外的一天,它就变得微不足道了。

2020-07-28