坂元友彦算法 - 查找星期几

---

在本文中，我们将讨论什么是坂元友彦算法以及如何使用该算法来确定给定日期是星期几。有多种算法可以知道星期几，但这种算法是最强大的算法之一。该算法在尽可能短的时间内和尽可能低的空间复杂度下找到日期所在的月份中的日期。

问题陈述 - 我们根据格里历给定一个日期，我们的任务是使用坂元友彦算法找出给定日期是星期几。

示例

输入 - 日期 = 30，月份 = 04，年份 = 2020

输出 - 给定日期是星期一

输入 - 日期 = 15，月份 = 03，年份 = 2012

输出 - 给定日期是星期四

输入 - 日期 = 24，月份 = 12，年份 = 2456

输出 - 给定日期是星期日

坂元友彦算法

现在让我们讨论坂元友彦算法背后的直觉。

众所周知，根据格里历，公元 1 年 1 月 1 日是星期一。

情况 1 忽略闰年

首先让我们讨论忽略所有闰年的情况，这意味着一年总共有 365 天。

由于 1 月有 31 天，一周有 7 天，所以我们可以说 1 月有 7*4 + 3 天，这意味着 2 月 1 日总是比 1 月 1 日晚 3 天。

由于 2 月有 28 天（除了闰年的情况），它本身是 7 的倍数，所以我们可以说 3 月 1 日与 2 月 1 日是同一天，这意味着 3 月 1 日也比 1 月 1 日晚 3 天。

现在对于 4 月，3 月有 31 天，即 7*4 +3，这意味着它将发生在 3 月 1 日之后的 3 天。因此，我们可以说 4 月 1 日将发生在 1 月 1 日的第一天之后的第 6 天。

我们现在将构造一个数组，其中 arr[i] 表示第 i 个月相对于 1 月 1 日的天数增加的数量。

我们有 arr[] = { 0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5 }。

情况 2 闰年

现在让我们讨论闰年的情况。

每四年，我们的计算中就会增加一天，但每百年除外。我们必须考虑这些额外的天数。为此，我们将使用以下公式 -

year/ 4（每 4 年）

- year / 100（每 100 年，它是 4 的倍数但仍然不是闰年，我们将从闰年中删除它）

+ year/ 400（每 400 年，它是 100 的倍数但仍然是闰年）

此公式将为我们提供确切的闰年数量。但是，这有一个例外。

现在，正如我们所知，2 月 29 日被认为是闰日，而不是 1 月 0 日。

这意味着我们不需要将年份的前两个月纳入我们的计算，因为闰日对其没有影响。因此，在 1 月或 2 月的情况下，我们将年份减 1 以进行补偿。因此，在这些月份，year/4 的值应基于前一年，而不是当前年份。

为了解决闰年问题，我们可以对 2 月之后的每个月的 arr[] 值进行修改，将其减 1，这将填补空白。这将解决闰年问题。我们需要在算法中实现以下更改以使其对闰年和非闰年都起作用。

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

如果当前月份是 1 月或 2 月，我们需要将年份减 1。

我们需要修改模数内的年度增量，使其变为 year + year/4 – year/100 + year/400 而不是 year。此更改对于考虑闰年中额外的一天并相应地调整计算是必要的。

示例

此方法的代码为

#include <bits/stdc++.h>
using namespace std;
// code to find out the day number of the given date
int Weekday(int year, int month, int day) {
   int arr[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 };
	
   if ( month < 3 )
      year -= 1;
   return ( ( year + year / 4 - year / 100 + year / 400 + arr[month - 1] + day) % 7 );
}

int main(void) {
   int day = 9, month = 9, year = 2020;
   int d = Weekday(year, month, day);
   string days[] = { "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday" };
   cout<< " The given date is on "; 
   cout << days[d];
   return 0;
}

输出

The given date is on Wednesday

复杂度

时间复杂度 - 此方法的时间复杂度为 O(1)

空间复杂度 - 此方法的空间复杂度为 O(1)，因为我们没有使用任何额外的空间。

结论 - 在本文中，我们讨论了坂元友彦算法以及算法背后的直觉