Algoritma Tomohiko Sakamoto - mencari hari dalam seminggu

Dalam artikel ini, kita akan membincangkan apakah algoritma Tomohiko Sakamoto dan cara menggunakannya untuk mengenal pasti hari dalam minggu tarikh tertentu. Terdapat beberapa algoritma untuk mengetahui hari dalam seminggu, tetapi algoritma ini adalah yang paling berkuasa. Algoritma ini mencari hari dalam bulan di mana tarikh ini berlaku dalam masa sekecil mungkin dan dengan kerumitan ruang terkecil.

Pernyataan Masalah - Kami diberi tarikh berdasarkan kalendar Georgia dan tugas kami adalah untuk mengetahui hari dalam minggu tarikh yang diberikan menggunakan algoritma Tomohiko Sakamoto.

Contoh

Masukkan - Tarikh = 30, Bulan = 04, Tahun = 2020

Output - Tarikh yang diberikan ialah Isnin

Masukkan - Tarikh = 15, Bulan = 03, Tahun = 2012

Output - Tarikh yang diberikan ialah Khamis

Masukkan - tarikh = 24, bulan = 12, tahun = 2456

Output - Tarikh yang diberikan ialah Ahad

Algoritma Sakamoto Tomohiko

Sekarang mari kita bincangkan gerak hati di sebalik algoritma Tomohiko Sakamoto.

Seperti yang kita sedia maklum, mengikut kalendar Georgia, 1 Januari Masihi jatuh pada hari Isnin.

Kes 1 abaikan tahun lompat

Kami mula-mula membincangkan kes di mana semua tahun lompat diabaikan, iaitu terdapat 365 hari dalam setahun.

Memandangkan Januari ada 31 hari dan seminggu ada 7 hari, kita boleh katakan Januari ada 7*4 + 3 hari, bermakna hari pertama bulan Februari sentiasa 3 hari selepas hari pertama langit Januari. p>

Memandangkan Februari mempunyai 28 hari (kecuali tahun lompat), yang merupakan gandaan 7, kita boleh mengatakan bahawa 1 Mac adalah pada hari yang sama dengan 1 Februari, yang bermaksud bahawa 1 Mac juga akan menjadi 3 Hari selepas 1 Januari.

Kini, untuk April, Mac mempunyai 31 hari, iaitu 7*4 +3, bermakna ia akan berlaku 3 hari selepas 1 Mac. Oleh itu, kita boleh mengatakan bahawa 1 April akan berlaku 6 hari selepas 1 Januari.

Kami kini akan membina tatasusunan dengan arr[i] mewakili bilangan hari tambahan selepas bulan i berlaku berbanding 1 Januari.

Kami ada arr[] = {0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5}.

Kes 2 Tahun Lompat

Sekarang mari kita bincangkan situasi tahun lompat.

Setiap empat tahun, satu hari ditambah kepada pengiraan kami, tetapi bukan setiap seratus tahun. Kita perlu mengambil kira hari-hari tambahan ini. Untuk ini kami akan menggunakan formula -

Tahun/4 (Setiap 4 tahun)

– Tahun / 100 (untuk setiap 100 tahun iaitu gandaan 4 tetapi masih bukan tahun lompat, kami mengeluarkannya daripada tahun lompat)

+ tahun / 400 (setiap tahun ke-400, ia adalah gandaan 100, tetapi masih tahun berulang)

Formula ini akan memberikan kita bilangan tahun lompat yang tepat. Walau bagaimanapun, terdapat satu pengecualian.

Kini, kita tahu bahawa 29 Februari dianggap sebagai hari lompat, bukan 0 Januari.

Ini bermakna kita tidak perlu memasukkan dua bulan pertama dalam tahun dalam pengiraan kerana hari lompat tidak mempunyai kesan ke atasnya. Jadi jika Januari atau Februari, kita akan tolak 1 daripada tahun itu untuk membayar pampasan. Oleh itu, dalam bulan-bulan ini, nilai tahun/4 hendaklah berdasarkan tahun sebelumnya dan bukannya tahun semasa.

Untuk menyelesaikan masalah tahun lompat, kita boleh menolak 1 daripada nilai arr[] setiap bulan selepas Februari untuk mengisi kekosongan. Ini menyelesaikan masalah tahun lompat. Kita perlu membuat perubahan berikut pada algoritma supaya ia berfungsi dalam tahun lompat dan tahun rata.

arr[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 }

Jika bulan semasa ialah Januari atau Februari, kita perlu menolak 1 daripada tahun tersebut.

Kita perlu mengubah suai kenaikan tahun dalam modulus kepada tahun +tahun/4 –tahun/100 +tahun/400 dan bukannya tahun. Perubahan ini perlu untuk mengambil kira hari tambahan dalam tahun lompat dan melaraskan pengiraan dengan sewajarnya.

Contoh

Kod untuk kaedah ini ialah:

#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;
}

Output

The given date is on Wednesday

kerumitan

Kerumitan Masa - Kerumitan masa kaedah ini ialah O(1)

Kerumitan Ruang - Kerumitan ruang kaedah ini ialah O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Kesimpulan - Dalam artikel ini, kami membincangkan algoritma Tomohiko Sakamoto dan intuisi di belakangnya

Atas ialah kandungan terperinci Algoritma Tomohiko Sakamoto - mencari hari dalam seminggu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!