坂本智彥的演算法-尋找星期幾

在本文中，我們將討論什麼是 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 閏年

現在讓我們來討論閏年的情況。

每四年，我們的計算中就會增加一天，但每百年則不增加一天。我們必須考慮到這些額外的日子。為此，我們將使用公式 -

年/ 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 <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)，因為我們沒有使用任何額外的空間。

結論 - 在本文中，我們討論了 Tomohiko Sakamoto 的演算法以及該演算法背後的直覺

以上是坂本智彥的演算法-尋找星期幾的詳細內容。更多資訊請關注PHP中文網其他相關文章！