坂本算法查找星期几的正确性

Question

我正在使用 Sakamoto 算法从给定日期找出星期几。谁能告诉我这个算法的正确性？我只想要从 2000 年到 2099 年的这个。

算法来自Wikipedia供引用。

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以及取决于月份的表的偏移量(因为一年中的月份边界是相当任意的)。

然后把整件事都取模 7，因为那是一周的长度。

(例如，如果一周是八天，这个公式会发生什么变化？嗯，显然是 mod 8。而且 y 需要是 5*y ，因为 365 % 8 == 5 . 月表 t[] 也需要调整。就是这样。)

顺便说一句，维基百科关于日历“直到 9999 都有效”的说法完全是武断的。无论我们坚持使用 Gregorian calendar 多久，这个公式都是有用的，无论是 10 年、100 年、1000 年还是 100 万年。

[编辑]

上述论证本质上是归纳证明。也就是说，假设该公式适用于特定的 (y,m,d)，您证明它适用于 (y+1,m,d) 和 ( y,m,d+1)。 (其中 y 是从 3 月 1 日开始的“虚拟年”。)所以关键问题是，当您从一年移到下一年时，总和的变化量是否正确？了解闰年规则，并且“虚拟年”在年底有额外的一天，这很容易做到。