63

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

4 回答 4

130

好吧，您可以通过查看它来判断它是正确的...假设该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 年不是闰年。所以我们必须减去 off y/100。

除了每400年又是一个闰年。所以我们必须添加y/400.

最后，我们只需添加月份中的日期d和依赖于月份的表的偏移量（因为一年中的月份边界是相当随意的）。

然后拿整个mod 7，因为那是一周的时间。

（例如，如果周是八天，那么这个公式会发生什么变化？嗯，很明显，它会是 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 日开始的“虚拟年份”。）所以关键问题是，当您从一年到下一年时，总和是否会发生正确的变化？有了闰年规则的知识，并且“虚拟年”在年底有额外的一天，它就微不足道了。

于 2011-06-17T12:46:50.133 回答
4

最近我在这里写了关于这个算法的博客文章。

算法背后的基本思想是从前一年的 12 月 31 日开始计算 2 月和 1 月的星期几。对于所有其他月份，我们将从当年12 月 31 日开始计算星期几。我们分两步执行此操作，首先我们计算当前月份前一个月的最后一天的星期几，m然后我们只添加d模 7。

BC 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 减去天数，例如(a-b)%7 = (a+(7-b%7))%7。

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

于 2016-06-18T17:38:39.427 回答
1

这可能不像上面提到的那样是一个完整的答案，但只想添加关于这个数组的一件事： 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*m - 0.2) mod 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 整除 ->真
  2. IF 完全可以被 100 整除但不能被 400 整除 -> False
  3. 能被 4 整除 ->真

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

我知道这可能不是答案，但这可能对那些难以记住/理解的人有所帮助，是的！并非我们所有人的智商水平都很高，可悲的是，我们中的一些人也记不住东西，哈哈。

于 2019-09-08T04:30:22.763 回答
0

对于公历

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};

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

  • 每个正常年份在一周中移动一天，闰年在一周中移动两天。如 (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};

于 2019-09-09T08:11:21.560 回答