坂元友彥演算法 - 查詢星期幾

---

在本文中，我們將討論什麼是坂元友彥演算法以及如何使用該演算法來確定給定日期是星期幾。有多種演算法可以知道星期幾，但這種演算法是最強大的演算法之一。該演算法在儘可能短的時間內和儘可能低的空間複雜度下找到日期所在的月份中的日期。

問題陳述 - 我們根據格里曆給定一個日期，我們的任務是使用坂元友彥演算法找出給定日期是星期幾。

示例

輸入 - 日期 = 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)，因為我們沒有使用任何額外的空間。

結論 - 在本文中，我們討論了坂元友彥演算法以及演算法背後的直覺