C语言 坂本算法求星期几的正确性

Correctness of Sakamoto's algorithm to find the day of week

提问by Harikrishnan

I am using Sakamoto's algorithm to find out the day of week from a given date. Can anybody tell me the correctness of this algorithm? I just want this from 2000 to 2099.

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

The algorithm from Wikipediais given for reference.

维基百科的算法供参考。

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

回答by Nemo

Well, you can tell just by looking at it that it is correct... Assuming that the t[]array is correct, which you can verify with just 12 spot checks (one for each month using any day/year).

好吧，您可以通过查看它来判断它是正确的...假设t[]数组是正确的，您只需进行 12 次抽查即可验证（每个月使用任何日期/年份进行一次）。

The y -= m < 3is a nice trick. It creates a "virtual year" that starts on March 1 and ends on February 28 (or 29), putting the extra day (if any) at the endof the year; or rather, at the end of the previousyear. So for example, virtual year 2011 began on Mar 1 and will end on February 29, while virtual year 2012 will begin on March 1 and end on the following February 28.

这y -= m < 3是一个很好的技巧。它创建了一个从 3 月 1 日开始到 2 月 28 日（或 29 日）结束的“虚拟年”，将额外的一天（如果有）放在年底；或者更确切地说，在上一年年底。例如，虚拟 2011 年从 3 月 1 日开始，并将于 2 月 29 日结束，而 2012 虚拟年将从 3 月 1 日开始，并在接下来的 2 月 28 日结束。

By putting the added day for leap years at the end of the virtual year, the rest of the expression is massively simplified.

通过将闰年的添加日期放在虚拟年份的末尾，表达式的其余部分得到了极大的简化。

Let's look at the sum:

让我们看看总和：

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

There are 365 days in a normal year. That is 52 weeks plus 1 day. So the day of the week shifts by one day per year, in general. That is what the yterm is contributing; it adds one to the day for each year.

正常的一年有 365 天。即 52 周加 1 天。因此，一周中的某一天通常每年会移动一天。这就是该y术语的贡献；它每年增加一天。

But every four years is a leap year. Those contribute an extra day every four years. Thanks to the use of virtual years, we can just add y/4to the sum to count how many leap days happen in yyears. (Note that this formula assumes integer division rounds down.)

但每四年是一个闰年。这些人每四年多贡献一天。由于使用了虚拟年份，我们可以将y/4总和相加来计算y年份中有多少闰日。（请注意，此公式假定整数除法向下舍入。）

But that is not quite right, because every 100 years is not a leap year. So we have to subtract off y/100.

但这并不完全正确，因为每 100 年都不是闰年。所以我们必须减去 off y/100。

Except that every 400 years is a leap year again. So we have to add y/400.

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

Finally we just add the day of the month dand an offset from a table that depends on the month (because the month boundaries within the year are fairly arbitrary).

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

Then take the whole thing mod 7 since that is how long a week is.

然后把整个东西 mod 7 因为那是一周的时间。

(If weeks were eight days, for example, what would change in this formula? Well, it would be mod 8, obviously. Also the ywould need to be 5*y, because 365 % 8 == 5. Also the month table t[]would need adjusting. That's it.)

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

Incidentally, Wikipedia's statement that the calendar is "good until 9999" is totally arbitrary. This formula is good for however long we stick with the Gregorian calendar, whether that is 10 years, 100 years, 1000 years, or 1 million years.

顺便说一下，维基百科关于日历“一直到 9999 年都很好”的说法完全是武断的。这个公式适用于我们坚持公历的时间长短，无论是 10 年、100 年、1000 年还是 100 万年。

[edit]

[编辑]

The above argument is essentially a proof by induction. That is, assumingthat the formula works for a particular (y,m,d), you provethat it works for (y+1,m,d) and (y,m,d+1). (Where y is a "virtual year" starting March 1.) So the key question is, does the sum change by the correct amount as you move from one year to the next? With knowledge of the leap year rules, and with the "virtual year" having the extra day at year end, it trivially does.

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

回答by csharpfolk

Recently I wrote blog post about this algorithm here.

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

The basic idea behind algorithm is to for February and January to count day of week from 31 Dec of the previous year. For all other months we will be counting day of week from currentyear 31 Dec. We do this in two steps first we compute day of week of last day of month preceding current month mthen we just add dmodulo seven.

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

31 Dec 1 BC is Sunday that is encoded as 0, Monday is 1 etc. So we have: 0 + y + y/4 - y/100 + y/400this with y -= m < 3computes day of week of 31 Dec of current year or previous year (depending on month). Note: 365 % 7 == 1this explains why we wrote yinstead of 365*y. The last component dis obvious since we start counting day of week from previous month last day.

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

The last part that need to be explained are values in array, for first two values these are number of days since last year 31 Dec to start of the month % 7. For rest of the months they are negated modulo sevennumber of days from end of prev month to 31 Dec of the current year. In other words we are subtracting days by addition modulo 7 e.g. (a-b)%7 = (a+(7-b%7))%7.

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

More explanation you may find in my blog post.

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

回答by krupesh Anadkat

This might not be a complete answer like some mentioned above, But just would like to add one thing regarding this array : 0 3 2 5 0 3 5 1 4 6 2 4

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

Consider months beginning from March and ending at February just like others said:

考虑一下从 3 月开始到 2 月结束的月份，就像其他人所说的那样：

1. March
2. April
3. May
4. June
5. July
6. August
7. September
8. October
9. November
10. December
11. January
12. February

1. 行进
2. 四月
3. 可能
4. 六月
5. 七月
6. 八月
7. 九月
8. 十月
9. 十一月
10. 十二月
11. 一月
12. 二月

Writing January to December from above numbering style :

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

So consider this as an array : int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

所以把它当作一个数组： int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

Now for all elements in array just do : (2.6*m - 0.2) mod 7parse the result as integer and you will get this: 0 3 2 5 0 3 5 1 4 6 2 4

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

• You can find this formula here : wikipedia

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

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

this : + y/4 - y/100 + y/400is related to leap year. The algo to check for leap year is :

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

1. Perfectly Divisible by 400 -> true
2. IF perfectly divisible by 100 but not by 400 -> False
3. Divisible by 4 -> True

1. 完全可以被 400 整除 ->真
2. IF 可以被 100 整除但不能被 400 整除 -> False
3. 可被 4 整除 ->真

perform checks on above order. Maybe that is why they subtracted y/100 and added y/4 & y/400. Yeah silly logic

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

I know this might not be the answer, But this might help to those who find it difficult to remember/understand stuff, yeah! not all of us have high IQ levels of understanding stuff and sadly some of us can't remember stuff too, lol.

我知道这可能不是答案，但这可能对那些难以记住/理解内容的人有所帮助，是的！并非我们所有人都有很高的智商水平来理解事物，遗憾的是我们中的一些人也无法记住事物，哈哈。

回答by princebillyGK

For Gregorian Calendar

对于公历

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

Explanation:

解释：

• See the commented array for

• 请参阅注释数组

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

and compare it with a calendar of a whole year (run cal 2to generate calendar in terminal in linux/unix) notice the starting day of the week of the day for each month.

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

• Every normal year shifting one day of the week and leap year shifting two days of the week. as (365%7)=1 and (366%7)=2

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

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

• But we are should not calculate the extra day if y is a leap year for month 0 and 1

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

y-=m<3

• but by this way we are also removing the extra day from non-leap years too. so we will fill up the gap by subtracting 1 day for every month after February.

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

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

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