Part 2 of Algorithms explained! Every few weeks I write about an algorithm and explain and implement it!
Is there an algorithm you always wanted to know about? Leave a comment!

오늘: 세계 종말의 규칙 또는: 1763년 11월 24일이 화요일인지 확인하기
존 콘웨이의 가장 유명한 작품은 콘웨이의 인생 게임이지만, 그는 더 많이 출판했다.그가 1970년경 개발한 특히 눈길을 끄는 알고리즘은 세계 종말의 규칙이다.
이 이름은 좀 이상하게 들릴 수도 있지만, 그 알고리즘은 신기하다. 머릿속에 주어진 날짜를 일주일 중 어느 날로 계산할 수 있게 해 준다.
이 글에서 나는 이 알고리즘이 어떻게 작동하는지 설명하고 PHP로 실제 예를 하나 만들 것이다.

세계 종말은 무엇입니까?

'종말 규칙'중의'종말'은 결코 세계 종말에 관한 것이 아니다.매년 이른바 세계 종말이 있다.세계의 종말은 일하는 날이 이미 알려진 날이다.매년 세계 종말은 같은 근무일이다.
예를 들어 11월 7일(세계 종말)이 토요일인 것을 알고 있다면 11월 21일은 어느 근무일입니까?너는 중간에 14일이 있다는 것을 알고 있고, 너는 일주일에 7일이 있다는 것을 알고 있기 때문에 이것은
14/7=2.014/7 = 2.014/7=2.0
꼬박 2주일.따라서 11월 21일도 토요일이어야 한다.
계산을 간소화하기 위해 매달 고정된 세계 종말이 있다.이 책상은 그것들을 기억하는 데 도움이 된다.예를 들어 나는 7-11시에 아침 9시부터 저녁 5시까지 일한다.
월 단위
세계 종말
기억 고리
일월
셋째(윤년 넷째)
3년 3분 4초.
이월
28위 (윤년 29위)
2월 마지막 날
삼월
0번 (예)
나누다
사월 사월
넷째
4/4
월, 오월
아홉째
"...9~5..."
유월
여섯째
6/6
칠월 칠월
열하나
'7시 11분'.
팔월
여덟째
8/8
구월 구월
다섯째
"...9~5..."
시월 시월
열 번째
10/10
십일월
일곱째
'7시 11분'.
십이월
열두 번째
12/12
달력을 살펴보자.

사실 이 모든 날짜는 같은 근무일이 있다.실제로 같은 근무일을 가진 모든 날짜는 세계의 종말로 볼 수 있다.

계산법

세계 종말 규칙은 달력의 패턴이 자주 반복되는 사실을 이용한다.다음은 알고리즘이 실제로 실행되는 기본 다이어그램입니다.

그것은 기본적으로 근무일의 범위를 좁혔다. 먼저 주어진 세기를 살펴보고, 그 다음에 연도를 보고, 그 다음에 월을 보고, 마지막으로 정확한 날짜를 확정한다.우리 한 걸음 한 걸음 봅시다.우리는 1763년 11월 24일의 근무일을 찾아내려고 시도할 것이다. (잠시 후에 나는 왜 이 특정 날짜를 선택했는지 설명할 것이다.)

세계 종말의 근무일을 계산하다

어느 해 세계 종말의 근무일(이른바'닻정일')을 계산하려면 먼저 이른바'세기닻정일'을 알아야 한다.이것은 특정 세기의 첫해의 정착일이다.이는 400년 동안 반복됩니다.
년
앵커 데이
1400
금요일
1500
수요일
1600
화요일.
1700
일요일 명사
1800
금요일
1900
수요일
2000
화요일.
2100
일요일 명사
2200
금요일
2300
수요일
2400
화요일.
만약 우리가 0년으로 돌아간다면, 우리는 화요일을 얻을 수 있을 것이다.우리는 그것으로 어떤 세기의 정착일을 계산할 수 있다.우선 일요일부터 근무일에 라벨을 붙여 봅시다.

$weekdays = [
    0 => 'Sunday',
    1 => 'Monday',
    2 => 'Tuesday',
    3 => 'Wednesday',
    4 => 'Thursday',
    5 => 'Friday',
    6 => 'Saturday',
];

그리고 세기를 예로 들면 (본질적으로 이렇다)
층(연도/100)층(연도/100)층(연도/100)
)
mod4mod 4mod4
(4세기에 접어든 주기) 그리고 2를 곱한다.다음에 우리는 그 중에서 4세기의 주기수(즉.
2−(세기2-(세기4)*22−(세기)
) 일반적으로 부정적인 결과가 발생하기 때문에 우리는 9(화요일+1주)로 대체하고 결과를 얻는다
mod7mod 7mod7
그 일주일을 벗어나기 위해서
(겸사겸사 한마디 하자면: 우리 오늘 많이 써야 돼%이것이 유효한지 살펴보겠습니다.
세기.
대상 앵커 일
mod 4
* 2
9 -
% 7
0
화요일
0
0
9
2
1
태양
1
2
7
0
2
금요일
2
4
5
5
셋
수요일
셋
6
셋
셋
4
화요일
0
0
9
2
5
태양
1
2
7
0
6
금요일
2
4
5
5
7
수요일
셋
6
셋
셋
8
화요일
0
2
9
2
9
태양
1
4
7
0
4세기의 주기가 효과가 있는 이유는 400년마다 역법이 기본적으로 한 번씩 반복되기 때문이다.한 세기의 해마다 세계 종말의 근무일은 그가 처한 세기에서 계산할 수 있다.
우리는 그것을 인코딩할 것이다.

/**
 * Determines the anchor day a century.
 *
 * @param int $yyyy Year, 1-4 digits
 * @return int Anchor day number
 */
function getCenturyAnchorday(int $yyyy): int {
    return (9 - (floor($yyyy / 100) % 4) * 2) % 7;
}

1763년 11월 24일의 세기 아나운서의 날은(9 - (floor(1763 / 100) % 4) * 2) % 7, 즉0이기 때문에Sunday.

한 해 또 한 해

세기의 정착일이 있으면 우리는 1년의 정착일을 계산할 수 있다.우리는 우선 연도의 마지막 두 자릿수가 필요하다. $year % 100일 년 중 근무일의 정착일이 기본적으로 증가하기 때문에 화요일, 수요일, 목요일, 금요일, 토요일, 일요일, 월요일, 화요일을 제외하고 윤년에는 하루를 건너뛴다(아직 하루가 남았기 때문이다).
17세기(1600년 이후)의 첫 몇 년을 예로 들자.
년
앵커 데이
1600(윤)
화요일.
1601
수요일
1602
목요일
1603
금요일
1604년(비약)
일요일 명사
1605
월요일
1606
화요일.
1607
수요일
1608년(비약)
금요일
1609
토요일
1610
일요일 명사
1611
월요일
1612(비약)
수요일
1613
목요일
1614
금요일
1615
토요일
이 결과는 연도를 계산하고 세기가 시작된 윤년수(즉 추가로 계산된 일수)와 세기의 정착일을 더해 실현할 수 있다.이 결과mod7은 그해 아나운서의 날이었다.이것이 바로 코드의 모습이다.

/**
 * Determines the year's anchor day.
 *
 * @param int $yyyy Year, 1-4 digits
 * @return int Year anchor day
 */
function getYearAnchorDay(int $yyyy): int {
    $centuryAnchorday = getCenturyAnchorday($yyyy);
    $yy = $yyyy % 100; // Year, 1-2 digits

    return ($yy + floor($yy / 4) + $centuryAnchorday) % 7;
}

1763년 11월 24일의 세기 닻날이 0인 것을 알기 때문에 우리는 1년 닻날을 계산할 수 있다. (63 + floor(63 / 4) + 0) % 7, 즉1이기 때문에Monday.
불가사의하다!우리는 지금 정해진 연도의 세계 종말의 근무일을 확정할 수 있다.다음 단계는 다음 최고의 세계 종말을 찾아 실제 하루를 정하는 것이다.위의 세계 종말표를 통해 우리는 이를 간단한 시사점으로 삼을 수 있다.

/**
 * Determines if a given year is a leap year.
 *
 * @param int $year
 * @return bool
 */
function isLeapYear(int $year): bool {
    return $year % 4 === 0 && ($year % 100 !== 0 || $year % 400 === 0);
}

/**
 * Determines the Doomsday of a given month.
 *
 * @param int $yyyy Year, 1-4 digits
 * @param int $m Month, 1-2 digits
 * @return int
 */
function getNearestDoomsday(int $yyyy, int $m): int {
    $isLeapYear = isLeapYear($yyyy);
    return [
        1 => !$isLeapYear ? 3 : 4,
        2 => !$isLeapYear ? 28 : 29,
        3 => 0,
        4 => 4,
        5 => 9,
        6 => 6,
        7 => 11,
        8 => 8,
        9 => 5,
        10 => 10,
        11 => 7,
        12 => 12,
    ][$m];
}

1763년은 윤년이 아니었고 11월을 지켜보고 있었기 때문에 다음 가장 좋은 세계 종말은November 7th이었다.
거의 다 왔어!
현재 우리는 실제 날짜부터 다음 최고의 아나운서의 날까지의 일수를 계산해야 한다.우리는 최근의 세계 종말과 우리가 찾고 있는 날짜 사이의 차이를 계산하고, 연도의 닻을 내린 날과 35 (
7∗57*57∗5
마이너스를 피하기 위해mod 7로 결과를 가져옵니다.이것은 우리에게 마지막 근무일 번호를 주었다.
예를 들어 다음 가장 좋은 세계 종말이 11월 7일이고 우리가 11월 24일을 찾고 있다면 계산 결과는 다음과 같다.우리는 1년 아나운서의 날이 월요일이라는 것을 알고 있기 때문에 1.우리도 최근의 세계 종말이 11월 7일이라는 것을 안다.
무슨
가치관
결실
일자
24
24
- 종말
- 7
17
+ 새해 앵커데이
+ 1
18
상쇄
+ 35
53
근무일 계산
% 7
4
코드에서 다음을 수행합니다.

/**
 * Determines the weekday of a given date.
 *
 * @param int $yyyy Year, 1-4 digits
 * @param int $m Month, 1-2 digits
 * @param int $d Day, 1-2 digits
 * @return int Number of the weekday, 0 = Sun, 6 = Sat
 */
function getWeekday(int $yyyy, int $m, int $d): int {
    $doomsday = getNearestDoomsday($yyyy, $m);
    $yearAnchorDay = getYearAnchorDay($yyyy);

    return ($yearAnchorDay + ($d - $doomsday) + 35) % 7;
}

이제 1763년 11월 24일의 근무일을 계산할 수 있습니다.

$weekdays[getWeekday(1763, 11, 24)]; // "Thursday"

그래서 1763년 11월 24일은 사실 화요일이 아니라 목요일입니다.이를 위한 테스트를 작성해 보겠습니다.

$result = true;
for ($i = 0; $i < 1000; $i++) {
    $yyyy = mt_rand(100, 9999); // PHP's mktime will make a wraparound with any smaller years.
    $m = mt_rand(1, 12);
    $d = mt_rand(1, 27);

    $result = $result && $weekdays[getWeekday($yyyy, $m, $d)] === date('l', mktime(0, 0, 0, $m, $d, $yyyy));
}

var_dump($result); // true

따라서 PHP가 내놓은 결과는 우리가 이룬 세계 종말의 규칙과 같다.Here's a PHPSandbox with the entire code!

배달 생각

내가 세계 종말의 규칙을 처음 들었을 때, 나는 곤혹스러웠다.나는 그것을 이해하는 데 상당히 오랜 시간이 걸렸지만, 일단 그것을 얻게 되면, 나는 그것의 총명함에 놀라움을 느낀다.이 알고리즘도 대수만 사용하기 때문에 그리 비싸지 않다.
더 많은 기억 갈고리 (특히 몇 년 동안 세계의 종말과 닻을 내린 날을 기억하는 것) 가 생기면, 너는 머릿속에서 어떤 근무일도 계산해 낼 수 있다.사실 이것은 괜찮은 파티 수법이라고 할 수 있다. "나에게 어떤 데이트를 주든지, 나는 너에게 그의 근무일을 알려줄 것이다."
읊다, 읊조리다
나는 여가 시간에 과학 기술 문장을 쓴다.만약 당신이 이 문장을 읽는 것을 좋아한다면 buying me a coffee!