C++ Tomohiko Sakamoto的算法-找出星期几

在这篇文章中，我们将讨论Tomohiko Sakamoto的算法是什么，并且如何使用这个算法来确定给定日期是星期几。有多种算法可以知道星期几，但这个算法是最强大的一个。这个算法以最少的时间和最少的空间复杂度找到日期所在的月份。

问题描述-我们以格里高利历给出一个日期，我们的任务是使用Tomohiko Sakamoto的算法找出给定日期是星期几。

示例

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

输出 - 给定日期是星期一

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

输出 - 给定日期是星期四

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

输出 - 给定日期是星期日

Tomohiko Sakamoto的算法

让我们现在来讨论Tomohiko Sakamoto的算法背后的灵感。

正如我们所知，根据格里高利历，公元1年1月1日是星期一。

情况1 忽略闰年

让我们先讨论忽略所有闰年的情况，也就是一年总共有365天。

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

由于二月有28天（闰年的情况除外），它本身是7的倍数，我们可以说3月1日与2月1日的那天是相同的，这意味着3月1日和一月1日之间相隔3天。

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

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

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

情况2 闰年

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

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

year / 4（每4年一次）

- 每100年（能被4整除但不是闰年的每一百年），我们将其从闰年中删除

+ 每400年（能被100整除但还是闰年的每四百年）

这个公式会给我们提供确切的闰年数量。然而，有一个例外情况。

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

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

为了解决闰年问题，我们可以通过减去1来对二月之后的每个月的arr[]值进行修改，填补这个空缺。这将解决闰年的问题。我们需要对算法进行以下更改，使其适用于闰年和非闰年。

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