Bài toán chuyển ngày sang thứ
Đôi khi có những thuật toán chỉ khiến bạn thốt lên: “xuất sắc, thông minh vãi cả đxx” Bài toán: Cho ngày, tháng, năm bất kì theo lịch Gregorian (lịch hiện nay), cho biết hôm đó rơi vào thứ mấy, tương ứng 0 -> Chủ Nhật, 1 -> Thứ Hai … Tôi đang muốn nói tới phương pháp của Sakamoto được đề xuất năm 1992. (Code theo chuẩn K&R C).
dayofweek(y, m, d) {
static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
y -= m < 3;
return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}Quá đơn giản, quá thông minh. Nhưng hiểu được 3 dòng code này ta mới cảm nhận được tác giả “ranh” đến mức nào. Giả sử gọi ngày 1 tháng 1 trong 1 năm bất kì làm mốc, để biết được ngày 1 tháng tiếp theo rơi vào đâu, ta có 31 = 7*4+3. Tức là ngày 1 tháng 2 rơi sau 3 ngày so với 1⁄1 (Nếu ngày 1⁄1 là thứ Hai thì 1⁄2 sẽ là thứ 5). t[] chính là offset cho ngày đầu tiên của tháng so với ngày 1⁄1, như vậy ta có t[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5} (Hơi khác so với code). Chuyện tiếp theo là cộng offset đó với ngày (d-1) - khoảng cách từ ngày muốn tính đến đầu tháng , xong module cho 7 là ra được.
Tuy nhiên đây mới là trong 1 năm. Bởi vì 1 năm (ko nhuận) có 365 = 52*7+1. Tức là cứ mỗi năm trôi qua là có thêm 1 ngày dôi ra, vậy ta có năm y, ta phải cộng thêm y ngày dôi ra đó. Nhưng đây mới là tính những năm không nhuận.
Những năm nhuận, ta lại phải thêm cái ngày 29⁄2 vào trong, tức là nó sẽ thêm 1 ngày nữa, trong y năm? nếu có y năm nhuận thì sẽ có thêm x ngày được dồn vậy, $x = y/4 - y/100 + y/400$ (công thức tuy nhìn giống Inclusion-Exclusion Principle nhưng rốt cuộc ứ phải). Đơn giản là: những năm nhuận là năm (1) chia hết cho 4 nhưng không chia hết cho 100 hoặc (2) chia hết cho 400.
Nhưng vẫn còn vấn đề, cái ngày thêm vào của năm nhuận là ngày 29⁄2, tức là nếu năm đó là năm nhuận nhưng ngày và tháng thuộc tháng 1 hoặc 2 thì ta không được tính vào (ví dụ 10/1/2016). Tác giả giải quyết siêu đơn giản : y -= m < 3. Cứ hễ input tháng 1, 2 thì đẩy về năm trước đó. Và lúc đó thì năm nhuận sẽ hết nhuận.
Nhưng vẫn còn vấn đề, rốt cuộc toán tử đó áp dụng cho cả những năm không nhuận. Tức tháng 1, 2 năm nào cũng bị đẩy về trước đó 1 năm. Lúc này mảng t[] lại được dùng bằng cách bù cho tháng 1, 2, ta cộng 1 vào t[0] và t[1] và giữ nguyên các t[] còn lại Sau đó chuyển -1 trong d-1 vào offset, lúc đó ta sẽ được mảng t[] như trong code gốc.
Ta còn một vấn đề là xác định ngày ban đầu để làm mốc và độ lệch c của ngày gốc đó so với ngày Chủ Nhật với index = 0. Nhưng bằng kiểm chứng, người ta phát hiện ra c = 0. Wow. 😲
Một thuật toán hay và đẹp, không chỉ tận dụng khả năng của ngôn ngữ lập trình, mà mỗi câu lệnh thể hiện được sự thông minh và khéo léo của tác giả.
Bonus Problem: Chứng minh tính đúng của thuật toán bằng quy nạp.