Kiểm tra một ngày là thứ mấy trong tuần với thuật toán Sakamoto
"fantastic, wonderful, significant, magnificent, outstanding,…" - là những mỹ từ mà Trấn Thành sẽ phải thốt lên khi nhìn vào sự vi diệu của thuật toán Sakamoto 🤣, trong bài viết này mình sẽ giới thiệu về thuật toán Sakamoto để giải quyết bài toán chuyển đổi một ngày bất kỳ sang thứ chỉ bằng một vài dòng code. Gét gô!
Giới thiệu bài toán
Bài toán "đơn giản" đặt ra như sau:
Cho một ngày bất kỳ cho trước theo lịch Gregorian (lịch hiện nay), nhiệm vụ là trả về thứ tương ứng của ngày đó (Quy ước: 0 - Chủ Nhật, 1 - Thứ Hai, 2 - Thứ Ba, v.v.).
Ví dụ:
Input : 15-03-1996
Output : 5 - Thứ Sáu
Input : 26-10-2002
Output : 6 - Thứ Bảy
Input : 01-01-2345
Output : 1 - Thứ HaiMặc dù có rất nhiều phương pháp để giải quyết bài toán này nhưng một trong những phương pháp ít được biết đến nhất và mạnh mẽ nhất đó là Thuật toán của Tomohiko Sakamoto, mình sẽ trình bày nó bằng Typescript như sau: (bạn có thể google để lấy code của những ngôn ngữ khác nhé)
// TypeScript program to implement
// the Tomohiko Sakamoto Algorithm
// function to implement tomohiko sakamoto algorithm
function dayOfTheWeek(y: number, m: number, d: number): number {
// array with leading number of days values
let t: number[] = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4]
// if month is less than 3 reduce year by 1
if (m < 3) y -= 1
return (y + y / 4 - y / 100 + y / 400 + t[m - 1] + d) % 7
}
// Driver code
let day: number = 26,
month: number = 10,
year: number = 2002
console.log(Math.round(dayOfTheWeek(year, month, day)))Rất đơn giản, nhưng để hiểu được 3 dòng code này thì không đơn giản tí nào 😂 Cùng đi vào từng dòng code để thấm nhuần tư tưởng của tác giả nhé 😂
Case 1: Bỏ qua năm nhuận
Ngày 1 tháng 1 sau công nguyên là ngày Thứ Hai theo lịch Gregorian.
Giả sử như nếu chúng ta không có năm nhuận, thì tổng số ngày trong 1 năm là 365. Lấy ngày 1 tháng 1 làm mốc để tính toán xem là ngày 1 tháng tiếp theo rơi vào đâu, vì tháng 1 có 31 ngày tức là 7 * 4 + 3 ngày nên ngày 1 tháng 2 sẽ sau 3 ngày so với ngày 1 tháng 1 (Nếu ngày 1 tháng 1 rơi vào Thứ Hai thì ngày 1 tháng 2 sẽ rơi vào Thứ Năm). Tháng 2 có 28 ngày (không bao gồm năm nhuận), là bội số chính xác của 7 (7 * 4 = 28). Do đó, ngày 1 tháng 3 trùng ngày với ngày 1 tháng 2 và nó cũng sẽ sau 3 ngày so với tháng 1.
Theo quy luật trên, chúng ta sẽ xây dựng được một mảng biểu thị số ngày bổ sung của ngày đẩu tiên mỗi tháng so với ngày 1 tháng 1 như sau:
t = [0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5]
Nếu muốn tính sự chênh lệch của ngày d bất kỳ trong tháng m so với ngày 1 tháng 1, chúng ta sẽ cộng t[m - 1] với ngày d - 1 (là khoảng cách từ ngày d đến ngày 1 của tháng), sau đó lấy phần dư khi chia cho 7 là được (phép tính module)
Tuy nhiên đấy mới là trong 1 năm, 1 năm không nhuận có 365 = 52 * 7 + 1, tức là mỗi 1 năm trôi qua thì lại có 1 ngày dôi ra. Ví dụ ngày 14 tháng 7 năm 2014 là Thứ Hai thì ngày 14 tháng 7 năm 2015 sẽ là Thứ Ba.
Vậy nếu có y năm trôi qua thì số ngày cần cộng thêm sẽ là y ngày, giả sử không có năm nhuận thì hàm tính toán của chúng ta sẽ như sau:
function dayOfTheWeek(y: number, m: number, d: number): number {
let t: number[] = [0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5]
return (y + t[m - 1] + d + c) % 7
}Với c là hằng số quy định độ lệch của ngày làm mốc (ngày gốc) so với ngày Chủ Nhật.
Case 2: Tính năm nhuận
Thực tế là cứ 4 năm sẽ có 1 năm nhuận, nên là mỗi 4 năm thì sẽ phải cộng thêm 1 ngày ? Nếu có y năm thì sẽ bao nhiêu ngày được cộng thêm ?
Những năm nhuận là năm chia hết cho 4 ngoại trừ những năm chia hết cho 100 mà không chia hết cho 400 (ví dụ năm 2004 là năm nhuận, năm 2000 là năm nhuận nhưng năm 2100, 2200,... không phải là năm nhuận).
Giả sử x là số ngày được cộng thêm thì chúng ta sẽ sử dụng công thức.
+ year / 4(cho năm chia hết cho 4)– year / 100(trừ đi năm chia hết cho 100)+ year / 400(cộng thêm năm chia hết cho 400)
Ta được công thức cuối cùng như sau:
x = y + y/4 - y/100 + y/400
Thế nhưng vẫn còn vấn đề, Nếu một năm là năm nhuận thì ngày nhuận là ngày 29 tháng 2 chứ không phải là ngày 0 tháng 1 bởi vậy nếu chúng ta cần tính toán cho ngày trong tháng 3 trở đi thì sẽ phải cộng thêm 1 ngày, còn 2 tháng đầu tiên (Tháng 1 và tháng 2) thì không cần đưa vào tính toán vì ngày nhuận không ảnh hưởng gì đến nó, mà sẽ phải đẩy lùi về năm trước đó. Tức là chúng ta sẽ có công thức:
y -= m < 3 - Nếu tháng nhỏ hơn 3 (Tháng 1 và Tháng 2) thì lùi năm hiện tại về năm trước đó, khi đó năm nhuận sẽ hết nhuận.
Tuy nhiên công thức trên áp dụng cho cả những năm không phải năm nhuận, vì thế lúc này mảng t[] cần phải bù cho tháng 1 và tháng 2, ta trừ 1 vào các phần tử còn lại của mảng t[] ngoại từ t[0] và t[1]
Vậy mảng t = [0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5] sẽ trở thành t = [0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4], giống như mảng của code gốc, vi diệu chưa ?
Lưu ý là ở ví dụ 1 mình có đề cập thêm hằng số c, nhưng thật tình cờ và thật bất ngờ, người ta chứng minh được c = 0 🤔
Như vậy chúng ta đã giải quyết được bài toán trên chỉ bằng vài đường múa cơ bản =)), nhưng mà phải công nhận nghĩ được ra thuật toán này quả thật là có một tư duy thực sự đỉnh cao, + 1 respect cho tác giả Tomohiko Sakamoto 👌👌👌
Link tham khảo
https://www.geeksforgeeks.org/tomohiko-sakamotos-algorithm-finding-day-week
https://stackoverflow.com/questions/6385190/correctness-of-sakamotos-algorithm-to-find-the-day-of-week
https://www.tutorialspoint.com/tomohiko-sakamoto-rsquo-s-algorithm-finding-the-day-of-the-week