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

Question

我正在使用坂本算法来找出给定日期的星期几。 谁能告诉我这个算法的正确性吗？我只想从 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 以及与月份相关的表的偏移量（因为一年中的月份边界相当任意）。

然后取整个 mod 7，因为这就是一周的长度。

（例如，如果周是八天，这个公式会发生什么变化？显然，它会是 mod 8。此外，y 需要是 5*y，因为 365 % 8 == 5。月份表 t[] 也需要调整。）

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

[编辑]

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

Answer 2

最近，我在此处撰写了有关此算法的博客文章。

算法背后的基本思想是对二月和一月进行计数
自上一年 12 月 31 日起的一周。对于所有其他月份，我们将从当前年份 12 月 31 日开始计算星期几。我们分两次计算
步骤 首先，我们计算当月 m 之前一个月的最后一天是星期几，然后我们只需添加 d 模 7。

BC 1 12 月 31 日是星期日，编码为 0，星期一为 1，依此类推。
所以我们有： 0 + y + y/4 - y/100 + y/400 其中 y -= m 3 计算
今年或上一年 12 月 31 日的星期几（取决于月份）。注意：365 % 7 == 1 这解释了为什么我们写 y 而不是 365*y。最后一个组件 d 很明显，因为我们从上个月的最后一天开始计算星期几。

需要解释的最后一部分是数组中的值，前两个值是自去年 12 月 31 日到月初 %7 的天数。对于其余月份，它们对从上个月月底到当年 12 月 31 日的天数取模 7 取反。换句话说，我们通过加法模 7 来减去天数，例如 (ab)%7 = (a+(7-b%7))%7。

您可以在我的博客文章中找到更多解释。

Answer 3

这可能不是像上面提到的一些完整的答案，但只是想添加有关此数组的一件事： 0 3 2 5 0 3 5 1 4 6 2 4

考虑从三月开始到结束的月份在二月就像其他人所说的那样：

1. 三月
2. 四月
3. 五月
4. 六月
5. 七月
6. 八月
7. 九月
8. 十月
9. 十一月
10. 十二月
11. 一月
12. 二月

从上面的编号样式写一月到十二月：

所以将其视为一个数组：
int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

现在对于数组中的所有元素只需执行以下操作：(2.6*米 - 0.2) 模 7
将结果解析为整数，您将得到：
0 3 2 5 0 3 5 1 4 6 2 4

• 您可以在这里找到这个公式：维基百科

int dayOfWeek(int d, int m, int y){
  // Months Array
  int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

  // Convert months array
  for (int i = 0; i < 12; i++){
    int ans = t[i] * 2.6 - 0.2;
    t[i] = ans % 7;
  }

  // Continue Algo
  if(m<3)
    y -= 1;

  int day = (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
  return day;
}

这个：+ y/4 - y/100 + y/400 与闰年有关。检查闰年的算法是：

1. 能被 400 整除 -> true
2. 如果能被 100 整除但不能被 400 -> False
3. 能被 4 整除 -> True

对上述订单执行检查。也许这就是为什么他们减去 y/100 并添加 y/4 和 y/4 的原因。 y/400。是的，愚蠢的逻辑

Answer 4

对于公历

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

说明：

• 请参阅注释数组

 t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5};

并将其与全年日历进行比较（在 linux/unix 中运行 cal 2 在终端中生成日历）注意该周的开始日期每个月的一天。

• 每个正常年份每周都会移动一天，而闰年则每周会移动两天。如 (365%7)=1 和 (366%7)=2

 i= y+y/4-y/100+y/400

• 但如果 y 是闰年 0 月和 1 月，我们不应该计算额外的一天

y-=m<3

• 但通过这种方式，我们也删除了额外的一天也来自非闰年。因此，我们将在 2 月之后每月减去 1 天来填补空白。

  int t[12]={0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};