Theppitak's blog

My personal blog.

12 กุมภาพันธ์ 2558

Pretty Feb Calendar Solution

ใน blog ที่แล้ว ผมได้ตั้งคำถามเกี่ยวกับปฏิทินที่ลงตัวของเดือนกุมภาพันธ์ว่ามีปีใดบ้าง ปรากฏว่ามีผู้ร่วมสนุกมาใน คอมเมนต์ โดยคิดแยกเป็นกรณีต่าง ๆ ของการเลื่อนวันในสัปดาห์ของวันที่เดิมของแต่ละปี

ก่อนอื่น เงื่อนไขของปีปฏิทินสวยก็คือ วันที่ 1 กุมภาพันธ์ของปีนั้นจะตรงกับวันอาทิตย์ และปีนั้นต้องเป็นปีปกติสุรทิน คือเดือนกุมภาพันธ์มี 28 วัน

คุณ Hisoft Manager ได้ตรวจสอบการเลื่อนวันในสัปดาห์ของวันที่ 1 กุมภาพันธ์ของแต่ละปีที่ติดกัน และแยกอธิบายเป็นกรณี ๆ ความคิดเริ่มแรกผมก็คิดด้วยวิธีคล้าย ๆ กันนี้ โดยคิดเป็นเศษเหลือจากการหารด้วย 7 โดยในปีปกติสุรทินซึ่งมี 365 วัน จะทำให้ 1 กุมภาพันธ์ของปีถัดไปเลื่อนวันในสัปดาห์ไป 1 วัน (365 หารด้วย 7 เหลือเศษ 1) และในปีอธิกสุรทินซึ่งมี 366 วัน จะทำให้ 1 กุมภาพันธ์ของปีถัดไปเลื่อนวันในสัปดาห์ไป 2 วัน (366 หารด้วย 7 เหลือเศษ 2) จากนั้นก็ใช้เงื่อนไขนี้ตรวจสอบรูปแบบการเลื่อนที่ทำให้ 1 กุมภาพันธ์เลื่อนกลับมาตรงกับวันอาทิตย์อีกครั้ง โดยมีเงื่อนไขเพิ่มเติมว่าปีนั้นต้องไม่เป็นปีอธิกสุรทินด้วย

ผลที่ได้คือ ปีปฏิทินสวยจะเป็นลำดับที่สมาชิกเพิ่มค่าเป็นรูปแบบ 6-11-11 คือปี 2009, 2015, 2026, 2037, 2043, 2054, 2065, ... คิดเป็นสูตรทั่วไปได้ว่า เป็น ค.ศ. ที่หารด้วย 28 แล้วเหลือเศษ 10, 21 หรือ 27 แต่ลำดับนี้จะเปลี่ยนรูปแบบเมื่อผ่านจุดที่เป็นข้อยกเว้น คือเมื่อ ค.ศ. หารด้วย 100 ลงตัว แต่หารด้วย 400 ไม่ลงตัว คำตอบจึงต้องแบ่งเป็นช่วง ๆ เช่น ระหว่าง ค.ศ. 1801-1899 จะเป็นปีที่หารด้วย 28 แล้วเหลือเศษ 9, 15, 26 เป็นต้น และจะต้องพิจารณาตรงช่วงรอยต่อระหว่างช่วงเป็นจุด ๆ ไป

ผมจึงพยายามหาสูตรทั่วไปที่ครอบคลุมทุกช่วง โดยเริ่มตั้งแต่ ค.ศ. 1753 ซึ่งเป็นปีแรกที่ปฏิทินนับเป็นปกติหลังจากที่ เริ่มใช้ปฏิทิน Gregorian แทนปฏิทิน Julian ตามที่คำสั่ง cal ของ GNU ได้ implement โดยตัดวันที่ 3-13 กันยายน 1752 ออกจากปฏิทิน:

$ cal 9 1752
    กันยายน 1752
อา จ. อ. พ. พฤ ศ. ส.
       1  2 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30



จุดเริ่มต้นของเราจึงเป็นวันที่ 1 กุมภาพันธ์ 1753 ซึ่งเป็นวันพฤหัสบดี:

$ cal 2 1753
  กุมภาพันธ์ 1753
อา จ. อ. พ. พฤ ศ. ส.
             1  2  3
 4  5  6  7  8  9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28

ผมกำหนดให้เศษเหลือจากการหารด้วย 7 แทนวันต่าง ๆ ในสัปดาห์ โดย 0 แทนวันอาทิตย์, 1 แทนวันจันทร์, 2 แทนวันอังคาร, ... 6 แทนวันเสาร์ ดังนั้น เศษเหลือเริ่มต้นในปี 1753 ของเราจึงเป็น 4 คือวันพฤหัสบดี

สมมุติให้ y แทนปีที่ต้องการพิจารณา นับจากปี 1753 ถึงปี y ถ้าทุกปีมี 365 วัน วันในสัปดาห์จะเลื่อนไปข้างหน้าปีละ 1 วัน (365 หารด้วย 7 เหลือเศษ 1) นับได้ y - 1753 วัน หากนำมาบวกวันเริ่มต้นคือวันพฤหัสบดี (เศษ 4) แล้วหารด้วย 7 เพื่อดูเศษเหลือ ก็จะรู้วันในปฏิทินของปีนั้นว่าเป็นวันอะไร แต่นี่คือกรณีที่ทุกปีมี 365 วัน โดยยังไม่คิดปีอธิกสุรทิน:

วันในสัปดาห์ของ 1 ก.พ. ปี y = (4 + (y - 1753)) mod 7 ถ้าทุกปีเป็นปกติสุรทิน

ปีอธิกสุรทินที่เกิดแต่ละครั้งจะทำให้วันในปฏิทินเลื่อนเพิ่มอีก 1 วัน หากรู้จำนวนปีอธิกสุรทินตั้งแต่ปี 1753 ถึงปี (y - 1) ก็จะนำมาบวกเพิ่มเข้ากับการเลื่อนวันในสูตรข้างต้นนี้ก่อนหารด้วย 7 เอาเศษ

จำนวนปีอธิกสุรทินตั้งแต่ปี 1753 ถึงปี (y - 1) คำนวณได้จากจำนวนปีอธิกสุรทินตั้งแต่ปี 1 ถึงปี (y - 1) ลบด้วยจำนวนปีอธิกสุรทินตั้งแต่ปี 1 ถึงปี 1753

จำนวนปีอธิกสุรทินตั้งแต่ปี 1 ถึงปี (y - 1) = floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400)

จำนวนปีอธิกสุรทินตั้งแต่ปี 1 ถึงปี 1753 = floor(1753/4) - floor(1753/100) + floor(1753/400) = 438 - 17 + 4 = 425

จำนวนปีอธิกสุรทินตั้งแต่ปี 1753 ถึงปี (y - 1) = floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400) - 425

ดังนั้นจึงได้ว่า วันที่ 1 ก.พ. ปี y จะตรงกับวัน: (4 + (y - 1753) + floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400) - 425) mod 7

หักลบตัวเลขแล้วจะได้เป็น (y - 2174 + floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400)) mod 7

และในเมื่อ 2174 mod 7 = 4 จึงแทน 2174 ด้วย 4 ใน modulo ได้ ได้เป็น:

วันในสัปดาห์ของ 1 ก.พ. ปี y = (y - 4 + floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400)) mod 7

และได้ว่า ปีปฏิทินสวย คือปีที่เป็นปกติสุรทิน และวันในสัปดาห์ของ 1 ก.พ. เป็น 0 ซึ่งเขียนเป็นนิพจน์เงื่อนไขภาษา C ได้เป็น:

  ((y % 4 != 0) || (y % 100 == 0 && y % 400 != 0)) &&
  (y - 4 + floor((y-1)/4) - floor((y-1)/100) + floor((y-1)/400)) % 7 == 0

QED.

ป้ายกำกับ: ,

1 ความเห็น:

แสดงความเห็น (มีการกลั่นกรองสำหรับ blog ที่เก่ากว่า 14 วัน)

<< กลับหน้าแรก

hacker emblem