Artikel ini keluar dari pertanyaan yang saya tanyakan pada diri sendiri kemarin.
"Apakah ada tahun di mana tidak satu bulan pun dimulai pada hari Senin?"
Sekilas, ya. Satu tahun dapat dimulai dari hari apa saja dalam seminggu, berbulan-bulan juga setiap kali dimulai pada hari yang berbeda dalam seminggu. Ada banyak pilihan, kemungkinan besar, akan ada lebih dari satu tahun seperti itu.
Jadi saya berpikir pada menit pertama setelah saya bertanya-tanya. Ini harus dibuktikan. Lewati semua tahun, misalnya. Cara yang sederhana dan cepat, tetapi tidak menarik. Membuktikan secara matematis adalah ide yang jauh lebih menggoda, tetapi saya sama sekali tidak mengerti bagaimana cara mendekati ini. Karena itu, saya baru mulai menuliskan durasi setiap bulan di atas kertas.
Di sini perlu disebutkan bahwa kita akan berbicara lebih banyak tentang
kalender Gregorian , yang menurutnya kita telah hidup sejak 1918. Namun, sebagian alasannya akan berlaku untuk
Julian .
Faktanya, tahun seperti itu tidak ada. Mari kita cari tahu alasannya.
Bagian 1. Bulan
Pertama, ingat berapa hari dalam setiap bulan:
Sekarang mari kita lihat berapa hari dalam setiap bulan lebih dari empat minggu.
Pada titik ini, ide berikut muncul. Jika Anda menambahkan 7 hari ke tanggal, hari dalam seminggu tidak akan berubah. Aritmatika modular bekerja. Dari sini mudah dipahami bahwa jika ada dua hari lagi dalam sebulan daripada dalam empat minggu, maka hari pertama bulan berikutnya akan bergeser dua hari dalam seminggu relatif terhadap hari pertama bulan berjalan. Bagaimanapun,
jika ada (28 + N) hari dalam sebulan, maka hari pertama bulan berikutnya akan bergeser N hari relatif ke hari dalam seminggu pada hari pertama bulan berjalan.
Misalnya, tahun ini Januari dimulai pada hari Selasa, jadi Februari dimulai pada hari Jumat. Sel + 3 = Jum
Berapa hari dalam seminggu pada hari pertama bulan tertentu? Untuk menemukan ini, Anda perlu menjumlahkan hari "surplus" selama empat minggu di semua bulan sebelumnya. Tabel menunjukkan pergeseran relatif terhadap hari dalam seminggu pada tanggal 1 Januari. Baris pertama adalah untuk tahun non-kabisat, yang kedua adalah untuk tahun kabisat.
Tapi ini tidak terlihat sangat terbuka, dan kita tahu bahwa pergantian tujuh hari tidak mengubah hari dalam seminggu. Oleh karena itu, sekarang kita menulis dalam tabel sisa dari membagi total pergeseran oleh 7.
Sekarang satu hal lagi! Terlihat jelas bagaimana menentukan hari dalam seminggu pada hari pertama bulan apa saja jika hari minggu pada tanggal 1 Januari diketahui. Anda hanya perlu menambahkan shift untuk bulan yang diinginkan. Saya sudah tahu pola Februari-Maret-November sejak sekolah menengah, tetapi saya tidak memperhatikan yang lain.
Kami mendapat jawaban untuk pertanyaan di awal artikel.
Karena untuk kedua varian tahun dalam tabel terdapat semua pergeseran dari 0 hingga 6, maka pada tahun apa pun ada bulan yang dimulai pada hari tertentu dalam seminggu.
Tetapi sekarang Anda dapat mengajukan pertanyaan lain. Misalnya, "dalam tahun berapa hanya ada satu bulan seperti itu?" atau "pada tahun-tahun apa di bulan-bulan seperti itu adalah jumlah maksimum bulan-bulan seperti itu?" Untuk melakukan ini, Anda harus dapat menentukan hari dalam seminggu pada tanggal 1 Januari setiap tahun.
Bagian 2. Tahun
Ketika saya belajar memprogram, dan ini berada di kelas 10 sekolah di PascalABC, salah satu tugas serius pertama adalah menerapkan prosedur yang mencetak kalender untuk tahun itu, yang dinyatakan sebagai argumen. Kami memiliki kiat tentang fungsi apa yang harus diterapkan. Secara umum, ia menghitung hari antara dua tanggal: referensi dan saat ini, untuk menentukan hari dalam seminggu pada 1 Januari dari tahun yang diinginkan.
Pendekatan ini berhasil, tetapi kecepatan tergantung pada seberapa dekat tahun yang dibutuhkan dengan referensi. Itu membuat saya kesal, tapi saya tidak bisa menemukan sesuatu yang lebih baik. Sekarang, saat yang tepat telah sepenuhnya memahami hal ini.
Tahun kabisat dalam kalender Gregorian ditetapkan sebagai berikut:
- tahun dengan jumlah kelipatan 400 adalah tahun kabisat
- tahun-tahun yang tersisa, jumlah yang merupakan kelipatan 100, tidak lompatan
- tahun yang tersisa, jumlah yang merupakan kelipatan dari 4, adalah tahun kabisat
- sisa tahun-tahun itu tidak melompat
Deskripsi ini menunjukkan bahwa siklus lompatan memiliki periode 400 tahun. Tetapi tidak jelas apakah siklus empat ratus tahun itu akan dimulai pada hari yang sama dalam seminggu.
Perhatikan bahwa Januari pertama dari tahun ke tahun digeser satu atau dua hari dalam seminggu, dan tulis
beberapa kode.bool is_leap_year(int year) { if ((year % 400) == 0) return true; if ((year % 100) == 0) return false; if ((year % 4) == 0) return true; return false; } void first_weekdays_table() { ofstream file("weekdays.txt", ios_base::out); int weekday = 3; for (int i = 1801; i <= 3000; ++i) { file << weekday; if ((i % 100) != 0) { file << " "; } else { file << endl; } weekday += is_leap_year(i) ? 2 : 1; weekday %= 7; } file.close(); }
Hari-hari dalam seminggu ditampilkan pada tanggal 1 Januari setiap tahun, dari 1801 hingga 3000. Senin ditetapkan sebagai "0", Selasa sebagai "1", dll. Kami akan menyajikan segala sesuatu dalam bentuk tabel yang terdiri dari dua siklus lengkap empat ratus tahun dan dua bagian. Berabad-abad berjalan secara horizontal, vertikal tahun ini di abad-abad ini. Di sel-sel di persimpangan abad dan tahun, hari minggu di mana tahun ini dimulai ditulis. Misalnya, hari pada minggu 1997 dimulai adalah di persimpangan kolom "1900" dan baris "97". Ini hari Rabu. Versi lengkap dari tabel:
bagian 1 ,
bagian 2 .
Dalam tabel, Anda dapat segera melihat dua hal: siklus empat ratus tahun benar-benar dimulai pada hari yang sama dalam seminggu (2001, 2401 dan 2801; Senin), dan alih-alih tahun 2000 ada "seribu sembilan ratus." Yang terakhir dilakukan dengan sengaja, untuk kenyamanan lebih lanjut. Fakta pertama memungkinkan kita untuk maju tanpa hambatan.
Dalam kalender Gregorian, semua siklus empat ratus tahun dimulai pada hari Senin.
Namun yang paling menarik terletak pada versi lengkap tabel. Anda mungkin menemukan bahwa setiap abad dalam siklus empat ratus tahun terdiri dari siklus dua puluh delapan tahun yang berulang:
Abad pertama dimulai dengan pergeseran dalam siklus yang sama dengan 0, yang kedua dengan pergeseran dari 4, yang ketiga dengan pergeseran dari 8 dan yang keempat dengan perubahan dari 12. Untuk ini, tabel disajikan dalam bentuk di mana ada "seratus" dari satu abad dan tidak ada nol. Perlu dikatakan bahwa secara total ada 14 opsi berbeda untuk tahun ini. Dalam siklus dua puluh delapan tahun, sekali untuk setiap hari dalam seminggu, awal tahun kabisat jatuh dan tiga kali awal tahun kabisat.
Sekarang kita dapat menentukan hari dalam seminggu untuk tanggal apa pun tanpa menggunakan tanggal referensi. Untuk melakukan ini, kita perlu memahami di abad mana, dalam siklus empat ratus tahun, adalah tahun, dan apa akunnya di abad ini. Menurut tabel kami menentukan hari dalam seminggu pada tanggal 1 Januari tahun itu, dan dengan bantuan bagian pertama artikel - hari dalam seminggu pada hari tertentu pada bulan yang diinginkan. Alih-alih seribu kata
kami akan menulis beberapa kode lagi. int get_weekday(int year, int month, int day) { int weekdays[] = {0, 1, 2, 3, 5, 6, 0, 1, 3, 4, 5, 6, 1, 2, 3, 4, 6, 0, 1, 2, 4, 5, 6, 0, 2, 3, 4, 5}; int shift_not_leap[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}; int shift_leap[] = {0, 3, 4, 0, 2, 5, 0, 3, 6, 1, 4, 6}; bool is_leap = is_leap_year(year); year -= 1; year %= 400; int century = year / 100; year %= 100; int index = (year + (4 * century)) % 28; int weekday = weekdays[index]; weekday += is_leap ? shift_leap[month - 1] : shift_not_leap[month - 1]; weekday += (day - 1); weekday %= 7; return weekday; }
Pembaruan dari 07/03/2019
Jika kita menyajikan siklus dua puluh delapan tahun dalam bentuk tabel,
0, 1, 2, 3, 5, 6, 0, 1, 3, 4, 5, 6, 1, 2, 3, 4, 6, 0, 1, 2, 4, 5, 6, 0, 2, 3, 4, 5
menjadi jelas bagaimana Anda dapat menghitung pergeseran hari dalam seminggu hingga 1 Januari:
weekday = (index + (index / 4)) % 7;
Mengingat hal ini, dan juga fakta bahwa offset selama berbulan-bulan dalam tahun kabisat dapat dihitung melalui offset pada tahun yang tidak kabisat, kami menulis
fungsi selanjutnya int get_weekday_c(int year, int month, int day) { int shifts[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}; int shift = shifts[month - 1]; if (is_leap_year(year) and (month > 2)) { shift += 1; }; year = (year - 1) % 400; int century = year / 100; int index = ((4 * century) + (year % 100)) % 28; int weekday = (index + (index / 4)) + shift + (day - 1); return (weekday % 7); }
Dengan demikian, Anda dapat menghitung hari dalam seminggu untuk tanggal berapa pun, hanya mengetahui 12 angka: pergeseran hari dalam seminggu ke hari pertama setiap bulan.
Bagian 3. Ringkasan
Dengan hanya dua tabel, Anda dapat menentukan hari dalam seminggu untuk tanggal apa pun tanpa menggunakan tanggal referensi.
Urutan hari dalam seminggu pada tanggal 1 Januari dalam siklus dua puluh delapan tahun:
Dan tabel offset hari kerja pada hari pertama setiap bulan selama tahun non-kabisat:
Pada saat menulis artikel, saya menemukan di Habré dua topik serupa:
satu dan
dua . Penulis yang pertama, menggunakan tabel khusus, menunjukkan bagaimana menemukan dalam pikiran hari dalam seminggu untuk tanggal di abad XX dan XXI. Tabel yang disajikannya berisi 56 angka. Algoritme yang diusulkan dalam artikel menggunakan tabel hari dalam seminggu dan dua tabel offset yang mengandung (28 + 2 * 12) = 52 angka yang perlu Anda ingat. Semua kode sumber ada di
GitHub .
Fakta yang menarik: dari 1 hingga 13 Februari 1918, tidak ada satu orang pun yang lahir di Rusia Soviet.
Ajukan pertanyaan pada diri sendiri di pagi hari pada hari Minggu =)