坂本智彦的算法-寻找星期几

在本文中，我们将讨论什么是 Tomohiko Sakamoto 算法以及如何使用该算法来识别给定日期是一周中的哪一天。有多种算法可以知道星期几，但这种算法是最强大的一种。该算法以尽可能最小的时间和最小的空间复杂度找到该日期出现的月份中的哪一天。

问题陈述 - 我们根据格鲁吉亚历给出一个日期，我们的任务是使用 Tomohiko Sakamoto 的算法找出给定日期是一周中的哪一天。

示例

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

输出 - 给定日期是星期一

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

输出 - 给定日期是星期四

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

输出 - 给定日期是星期日

坂本智彦算法

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

众所周知，根据格鲁吉亚历，公元 1 月 1 日是星期一。

案例1忽略闰年

我们首先讨论忽略所有闰年的情况，即一年共有 365 天。

由于一月有 31 天，一周有 7 天，所以我们可以说一月有 7*4 + 3 天，这意味着二月的第一天总是在一月的第一天之后 3 天。 p>

由于二月有 28 天（闰年除外），它本身是 7 的倍数，我们可以说 3 月 1 日将与 2 月 1 日在同一天，这意味着 3 月 1 日也将是 3 1 月 1 日之后的几天。

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

我们现在将构建一个数组，其中 arr[i] 表示相对于 1 月 1 日这一天，第 i 个月发生后的额外天数。

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

案例 2 闰年

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

ChartGen

AI快速生成专业数据图表

下载

每四年，我们的计算中就会增加一天，但每百年则不增加一天。我们必须考虑到这些额外的日子。为此，我们将使用公式 -

年/ 4（每 4 年）

– 年 / 100（对于每 100 年，即 4 的倍数但仍然不是闰年，我们会将其从闰年中删除）

+ 年/ 400（每第 400 年，它是 100 的倍数，但仍然是一个循环年）

这个公式将为我们提供准确的闰年数。不过，有一个例外。

现在，我们知道 2 月 29 日被视为闰日，而不是 1 月 0 日。

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

为了解决闰年问题，我们可以将 2 月之后每个月的 arr[] 值减去 1，以填补空白。这样就解决了闰年的问题。我们需要对算法进行以下更改，以使其在闰年和平年都能发挥作用。

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

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

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

示例

此方法的代码是：

#include 
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)，因为我们没有使用任何额外的空间。

结论 - 在本文中，我们讨论了 Tomohiko Sakamoto 的算法以及该算法背后的直觉