Tomohiko Sakamoto의 알고리즘 - 요일 찾기

이 기사에서는 Tomohiko Sakamoto 알고리즘이 무엇인지, 그리고 이를 사용하여 주어진 날짜가 어느 요일인지 식별하는 방법에 대해 설명합니다. 요일을 아는 알고리즘은 여러 가지가 있지만 이 알고리즘이 가장 강력합니다. 이 알고리즘은 가능한 가장 짧은 시간과 가장 작은 공간 복잡도로 이 날짜가 발생하는 달의 날짜를 찾습니다.

문제 설명 - 조지아 달력을 기반으로 한 날짜가 주어졌으며 우리의 임무는 Tomohiko Sakamoto의 알고리즘을 사용하여 주어진 날짜가 어느 요일인지 알아내는 것입니다.

예

Enter - 날짜 = 30, 월 = 04, 연도 = 2020

Output - 주어진 날짜는 월요일입니다

Enter - 날짜 = 15, 월 = 03, 연도 = 2012

Output - 주어진 날짜는 목요일입니다

Input - 날짜 = 24, 월 = 12, 연도 = 2456

Output - 주어진 날짜는 일요일입니다

사카모토 토모히코 알고리즘

이제 Tomohiko Sakamoto 알고리즘의 직관에 대해 논의해 보겠습니다.

우리 모두 알고 있듯이 조지아 달력에 따르면 서기 1월 1일은 월요일입니다.

사례 1 윤년 무시

먼저 윤년을 모두 무시하는 경우, 즉 1년이 365일인 경우에 대해 논의합니다.

1월은 31일, 일주일은 7일이므로 1월은 7*4 + 3일이라고 할 수 있습니다. 즉, 2월의 첫날은 항상 1월의 첫날로부터 3일 후라는 뜻입니다. p>

2월은 28일(윤년 제외)이 있고 그 자체가 7의 배수이므로 3월 1일은 2월 1일과 같은 날이라고 말할 수 있습니다. 이는 며칠 뒤 3월 1일도 1월 1일 3일이 된다는 의미입니다. 날짜 이후.

이제 4월은 3월이 31일이므로 7*4 +3이므로 3월 1일로부터 3일 후에 발생합니다. 따라서 4월 1일은 1월 1일로부터 6일 후에 발생한다고 말할 수 있습니다.

이제 arr[i]가 1월 1일을 기준으로 i월이 발생한 이후 추가된 일 수를 나타내는 배열을 구성하겠습니다.

arr[] = { 0, 3, 3, 6, 1, 4, 6, 2, 5, 0, 3, 5 }가 있습니다.

사례 2 윤년

이제 윤년 상황에 대해 논의해 보겠습니다.

4년마다 하루가 계산에 추가되지만 100년마다는 아닙니다. 우리는 이러한 추가 일수를 고려해야 합니다. 이를 위해 공식을 사용합니다 -

Year/4(4년마다)

– 연도/100(4의 배수이지만 윤년이 아닌 100년마다 윤년에서 제외됩니다.)

+ 연도 / 400(400년마다 100의 배수이지만 여전히 반복되는 연도)

이 공식을 통해 정확한 윤년 수를 알 수 있습니다. 그러나 한 가지 예외가 있습니다.

이제 우리는 1월 0일이 아닌 2월 29일이 윤일로 간주된다는 것을 알고 있습니다.

즉, 윤일은 영향을 주지 않으므로 계산에 연도의 처음 두 달을 포함할 필요가 없다는 의미입니다. 따라서 1월이나 2월이면 해당 연도에서 1을 빼서 보상합니다. 따라서 이 달의 year/4 값은 현재 연도가 아닌 전년도를 기준으로 해야 합니다.

윤년 문제를 설명하기 위해 2월 이후 각 달의 arr[] 값에서 1을 빼서 공백을 메울 수 있습니다. 이로써 윤년 문제가 해결됩니다. 윤년과 평년에도 작동하려면 알고리즘을 다음과 같이 변경해야 합니다.

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

현재 달이 1월이나 2월이면 연도에서 1을 빼야 합니다.

연도 대신 연도 증가분을 연도 +연도/4 –연도/100 +연도/400으로 수정해야 합니다. 윤년의 추가 일수를 고려하고 이에 따라 계산을 조정하려면 이러한 변경이 필요합니다.

예

이 방법의 코드는 다음과 같습니다.

으아아아

출력

으아아아

복잡성

시간 복잡도 - 이 방법의 시간 복잡도는 O(1)

입니다.

공간 복잡도 - 추가 공간을 사용하지 않으므로 이 접근 방식의 공간 복잡도는 O(1)입니다.

결론 - 이 기사에서는 Tomohiko Sakamoto의 알고리즘과 그 뒤에 숨겨진 직관에 대해 논의했습니다

위 내용은 Tomohiko Sakamoto의 알고리즘 - 요일 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!