Изучаем календарь

  • Tutorial
Эта статья получилась из вопроса, который я сам себе задал вчера.
«Существует ли год, в котором ни один месяц не начинается в понедельник?»
На первый взгляд — да. Год может начинаться с любого дня недели, месяцы тоже каждый раз начинаются в разные дни недели. Вариантов множество, скорее всего, найдётся и не один такой год.

Так я подумал в первую минуту после того, как задался вопросом. Это следовало бы доказать. Перебрать все года, например. Простой и быстрый способ, но не интересный. Доказать математически было намного более заманчивой идеей, но как к этому подступиться я совершенно не понимал. Поэтому просто начал выписывать продолжительность каждого месяца на бумагу.

Тут стоит оговорить, что речь дальше пойдёт про григорианский календарь, по которому мы живём с 1918 года. Однако часть рассуждений будет верна и для юлианского.

На самом деле такого года не существует. Давайте разбираться почему.

Часть 1. Месяцы


Сначала вспомним, сколько дней в каждом месяце:
Янв Фев Март Апр Май Июнь Июль Авг Сен Окт Нояб Дек
31 28 / 29 31 30 31 30 31 31 30 31 30 31
Теперь посмотрим, на сколько дней в каждом месяце больше, чем в четырёх неделях.
Янв Фев Март Апр Май Июнь Июль Авг Сен Окт Нояб Дек
3 0 / 1 3 2 3 2 3 3 2 3 2 3
В этом месте возникает следующая идея. Если к дате прибавить 7 дней, то день недели не изменится. Работает модульная арифметика. Отсюда легко понять, что если дней в месяце на два больше, чем в четырёх неделях, то первое число следующего месяца сдвинется на два дня недели относительно первого числа текущего месяца. Да и вообще,
если в месяце (28 + N) дней, то первое число следующего месяца сдвинется на N дней относительно дня недели первого числа текущего месяца.
Например, в этом году январь начался во вторник, поэтому февраль начался в пятницу. Вт + 3 = Пт.

Насколько же сдвинут день недели первого числа некоторого месяца? Чтобы найти это, надо просуммировать «излишки» дней над четырьмя неделями во всех предыдущих месяцах. В таблице представлены сдвиги относительно дня недели на первое января. Первая строка для невисокосного года, вторая для високосного.
Янв Фев Март Апр Май Июнь Июль Авг Сен Окт Нояб Дек
0 3 3 6 8 11 13 16 19 21 24 26
0 3 4 7 9 12 14 17 20 22 25 27
Но это выглядит не очень показательно, да и мы знаем, что сдвиг на семь дней не меняет день недели. Поэтому запишем теперь в таблицу остатки от деления суммарных сдвигов на 7.
Янв Фев Март Апр Май Июнь Июль Авг Сен Окт Нояб Дек
0 3 3 6 1 4 6 2 5 0 3 5
0 3 4 0 2 5 0 3 6 1 4 6
Вот теперь другое дело! Ясно видно, как определить день недели на первое число любого месяца, если известен день недели на первое января. Надо просто прибавить сдвиг для интересующего месяца. Закономерность февраль-март-ноябрь я знаю ещё со школы, а другие не замечал.

Мы получили ответ на вопрос в начале статьи.
Так как для обоих вариантов года в таблице присутствуют все сдвиги от 0 до 6, то в любом году есть месяц, который начинается в какой-то определённый день недели.
Но теперь можно задавать другие вопросы. Например, «в каких годах такой месяц только один?» или «в какие года таких месяцев максимально много?». Для этого надо уметь определять день недели на первое января любого года.

Часть 2. Годы


Когда я учился программировать, а это было в 10 классе школы на PascalABC, одним из первых серьёзных заданий было реализовать процедуру, распечатывающую календарь на год, который передавался как аргумент. У нас были подсказки, какие функции для этого надо реализовать. В целом всё сводилось к подсчёту дней между двумя датами: эталонной и текущей, чтобы определить день недели на первое января нужного года.

Такой подход работал, но скорость зависела от того, насколько близко необходимый год к эталонному. Меня это расстраивало, но придумать что-то лучше я тогда не смог. Теперь же настал идеальный момент, чтобы до конца разобраться в этом.

Високосные года в григорианском календаре назначаются следующим образом:
  • год, номер которого кратен 400, — високосный
  • остальные года, номер которых кратен 100, — невисокосные
  • остальные года, номер которых кратен 4, — високосные
  • остальные года — невисокосные
Из этого описания видно, что цикл високосности имеет период в 400 лет. Но не ясно, будут ли такие четырёхсотлетние циклы начинаться в один и тот же день недели.

Заметим, что первое января от года к году смещается на один или два дня недели, и напишем
немного кода.
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();
}


Выводятся дни недели на первое января каждого года, с 1801 до 3000. Понедельник обозначается как «0», вторник как «1», и т. д. Представим всё в виде таблицы из двух полных четырёхсотлетних циклов и двух половинок. По горизонтали идут столетия, по вертикали года в этих столетиях. В ячейки на пересечении столетия и года написан день недели, в который этот год начался. Например, день недели, в который начался 1997 год, стоит на пересечении столбца «1900» и строки «97». Это среда. Полная версия таблицы: часть 1, часть 2.



В таблице сразу можно заметить две вещи: четырёхсотлетние циклы действительно начинаются в один день недели (2001, 2401 и 2801 года; понедельник), а вместо 2000 года есть «тысяча девятьсот сотый». Последнее сделано нарочно, для дальнейшего удобства. Первый же факт позволяет нам без препятствий двигаться дальше.
В григорианском календаре все четырёхсотлетние циклы начинаются в понедельник.
Но самое интересное кроется в полной версии таблицы. Можно обнаружить, что каждое столетие внутри четырёхсотлетнего цикла состоит из повторяющегося двадцативосьмилетнего цикла:
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

Первое столетие начинается со смещением по циклу, равным 0, второе со смещением 4, третье со смещением 8 и четвёртое со смещением 12. Именно для этого таблица представлена в виде, где в столетии есть «сотые» года и нет нулевых. Стоит сказать, что всего существует 14 различных вариантов года. В двадцативосьмилетнем цикле по одному разу на каждый день недели приходится начало високосного года и по три раза начало не високосного.

Теперь мы можем определить день недели для любой даты, не используя опорных дат. Для этого нам надо понять, в каком столетии внутри четырёхсотлетнего цикла находится год и какой он по счёту в этом столетии. По таблице определим день недели на первое января года, а с помощью первой части статьи — день недели в конкретное число нужного месяца. Вместо тысячи слов
напишем ещё немного кода.
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;
}


Обновление от 03.07.2019


Если представить двадцативосьмилетний цикл в виде таблицы,

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

то становится понятно, как можно вычислить смещение дня недели на первое января:

weekday = (index + (index / 4)) % 7;

С учётом этого, а также того, что смещения для месяцев в високосном году можно вычислить через смещения в невисокосном, напишем
следующую функцию
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);
}


Таким образом, можно вычислить день недели для любой даты, зная всего лишь 12 чисел: смещения дней недели на первое число каждого месяца.

Часть 3. Итоги


С помощью всего двух таблиц можно определить день недели для любой даты, не используя при этом опорных дат.

Последовательность дней недели на первое января в двадцативосьмилетнем цикле:
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

И таблица смещений дней недели на первое число каждого месяца для невисокосного и високосного годов:
Янв Фев Март Апр Май Июнь Июль Авг Сен Окт Нояб Дек
0 3 3 6 1 4 6 2 5 0 3 5
0 3 4 0 2 5 0 3 6 1 4 6
Во время написания статьи, я нашёл на Хабре две схожие по тематике: раз и два. Автор первой с помощью специальной таблицы показывает, как найти в уме день недели для дат в XX и XXI веках. Представленная им таблица содержит 56 чисел. Предложенный в статье алгоритм использует таблицу дней недели и две таблицы смещений, содержащие (28 + 2*12) = 52 числа, которые необходимо запомнить. Весь исходный код лежит на GitHub'е.

Интересный факт: с 1 по 13 февраля 1918 года в Советской России не родился ни один человек.

Задавайте себе вопросы с утра по воскресеньям =)
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 45

    +3
    У меня только один вопрос: в какой час ночи тебе пришла в голову эта задача?
      0
      Утром в воскресенье
      +1
      Мне кажется, визуально, мы можем представить задачу вот такой таблицей.
      Табличка
      Мысленно двигаем нашу ленту дат туда-сюда, смотрим на оранжевый столбец.
      Надо убедиться, можем ли мы сдвигать начало года в рамках недели так, чтобы не было единиц в первом столбце. Т.е. проверит надо не все года, а все дни начала года. Которых может быть 7. С учетом високоснх годов получаем 14 вариантов.

      В рамках каждого варианта надо проверить 12 дней — 12 первых чисел.
      Является ли число понедельником, можно посчитать как
      ((«порядковый номер дня в году»+«смещение первого января относительно понедельника») mod 7) != 1
        –1
        Ваша картинка не отображается. Поправьте её, пока есть время для редактирования комментария.
          +1
          Да, если говорить про перебор, то такой способ сработает. Спасибо за интерес!
          +1

          Можно добавить ещё 1 вопрос: что интересного в числе 20871?

            +1
            В советское время куча народу носила таблички "вечных календарей" в кошельке.
              0
              Да, я читал про такие календари. Проблема в том, что они либо очень объёмные, либо не очень вечные.
              • НЛО прилетело и опубликовало эту надпись здесь
              0
              Получается, по Григорианскому календарю 1 января 0 года был понедельник?
                0
                Нет, 1 января 0 года было бы субботой. Это был високосный год. Так же 1 января 0 года было субботой и по юлианскому календарю.

                А вот 1 января 1 года было бы, как раз, понедельником.
                  +1
                  А меня вот убеждают, что 0-го года не случилось

                  PS: Спасибо за статью.
                    +1
                    0 года действительно не было. В первом предложении я это постарался подчеркнуть частицей «бы». А в третьем я опечатался. Имел ввиду, что субботой было 1 января 1 года по юлианскому календарю.

                    P. S. Пожалуйста, я рад, что вам понравилось!
                      0
                      Я вас еще более запутаю, сообщив что год рождения Иисуса Христа точно не установлен, существуют версии от -12 до 4 года от «рождества Христова». Дионисий Малый в 6 веке немного ошибся при вычислении даты этого основополагающего события, так в релиз и ушло. Исправление внедрять сложно, так и поддерживают легаси.
                      0
                      Нулевой год — первый год до нашей эры. Хотя, понятное дело, тогда действовали совсем другие календари.
                    +2

                    Не было в григорианском календаре 1 января нулевого года. Нулевого года в нем вообще никогда не было. Был первый до р.х. и первый после р.х. Нулевая точка — около рассчитанной даты р.х., и это не год, а переход от одного года к другому.

                      0
                      Очень просто понять понятие года (первый, второй, двухтысячный) на примере времени — пять минут пятого, десять минут третьего…
                    +1
                    Небольшой оффтоп. Сейчас будет печальная история про необходимость общего разностороннего развития…
                    В далеком 1998/99 году мне попалась похожая задачка на олимпиаде. Ее решение давало мне очень хороший шанс поступления в понравившийся мне ВУЗ без экзаменов. Задача не сложная — всего-то делов, определить день недели по дате, зная, например, что 1 января 1800 года был понедельник и это был високосный год. Но вот беда: я забыл, что количество дней в месяцах не всегда чередуется, а в июле-августе повторяется. Календарей в поле зрения не было, смартфоны еще не появились, как итог — неверное решение и пролет с поступлением… Тоска, печаль…
                      0
                      1 января 1800 года было средой, а сам год невисокосный =)

                      На самом деле, мне тоже пришлось насильно вспоминать, сколько дней в каком месяце, когда сел писать статью. Есть метод счёта по костяшкам пальцев и впадинам между ними. Костяшка — 31 день, впадина — 28 / 29 / 30 дней. Если костяшка мизинца это январь, то костяшка указательного пальца — июль. А август снова начинается с костяшки.
                        0
                        Это я знаю. Но уже слишком поздно. :-(
                          0
                          Не знаю только, почему все с этими костяшками носятся. Мне лично гораздо проще запомнить несколько исторических фактов.

                          1. Юлианский календарь — он, собственно, почему Юлианский? потому что его Гай Юлий Цезарь ввёл.
                          2. Кто пришёл ему на смену? Известно кто — Октавиан Август. Которому суждено было всю жизнь бороться с призраком своего великого предка. И чтобы ему польстить один из месяцев (секстилий) переименовали в месяц Август.
                          3. Есть даже красивая легенда, что, собственно, Август и оторвал ещё один день от Февраля и прицепил к «своему» месяцу. Хотя вроде бы и неверная.

                          В любом случае всё это помнить совершенно необязательно — достаточно помнить два имени: Гай Юлий Цезарь и Октавиан Август… оба известные и знаменитые, оба «падающие» на свои два месяца… главное что и календарь-то Юлианский, а Император Июнь — точно в природе отсуствует…
                          • НЛО прилетело и опубликовало эту надпись здесь
                              +2

                              И как это поможет определить количество дней в ноябре?

                                +1
                                Реперная точка: декабрь — 31, откатываемся от него назад, чередуя 31/30 до Июля/Августа
                                  0
                                  Можно и от января идти… хотя и дольше… главное помнить что два «длинных» месяца бок-о-бок — это июль-август. Ну ещё декабрь/январь, но тут, почему-то, ни у кого сложностей не возникает…
                                  0
                                  Да, конечно. Ноябрь идёт после августа — значит нужно идти от декабря взад.
                                  0
                                  В «Что-Где-Когда» был вопрос (лет 30 назад): «Что восьмой отнял у второго, чтобы стать не хуже седьмого?».
                              0
                              Есть одна прикольная штука, как система непрерывного счёта времени, которая используется для астрономических расчётов. Зовётся эра Скалигера, или юлианские дни. А ещё есть забавные закономерности при пересчёте юлианских дней в григорианский календарь.
                              Посмотрите, там нумерология весьма забавная.
                                0
                                Спасибо, посмотрю. А закономерности вполне себе понятные, просто со временем увеличивается разрыв между одинаковыми датами из-за разного определения високосных годов.
                                0

                                Было бы интересно посмотреть на решение на Прологе.

                                  +6
                                  Как всё сложно…

                                  В году два неизменных интервала — до 28/29 февраля и после. Интервал «после» длиннее, в нём 10 месяцев, на них и будем смотреть. Длина каждого месяца постоянна из года в год, значит и смещение дня недели (относительно остальных девяти месяцев) постоянно. Итого, если первые числа этих десяти месяцев выпадают на разные дни, т.е. покрывают все семь дней недели, то не существует года, в котором бы ни один месяц не начинался бы в понедельник.

                                  Открываем календарь за текущий (подойдёт любой) год и смотрим:
                                  1 марта — 5
                                  1 апреля — 1
                                  1 мая — 3
                                  1 июня — 6
                                  1 июля — 1
                                  1 августа — 4
                                  1 сентября — 7
                                  1 октября — 2

                                  Всё, покрыты все дни недели. Дальше считать не надо. Нет года, в котором ни один месяц не начинается в понедельник. Между мартом и октябрём (включительно) один месяц (а иногда и два) обязательно начнётся в понедельник.
                                    0
                                    Спасибо, замечательное решение!
                                      +1
                                      Я именно так и стал решать (сначала прочитал до ката и решил решить сам)… Надо только добавить к этому еще вариант с високосным годом… Хотя да… Ваш вариант не зависит от февраля…
                                      +1
                                      Но не ясно, будут ли такие четырёхсотлетние циклы начинаться в один и тот же день недели.


                                      Ну почему же? 400 лет по 365 дней, плюс (100-3) дополнительных високосных дня дают 146097 дней цикла — число, делящееся на 7 нацело, без привлечения всяких сложных таблиц…
                                        0
                                        Безусловно так и есть! Таблица лишь визуализирует это и помогает найти двадцативосьмилетний цикл.
                                        +1
                                        Помню в 5 классе, когда узнал как можно математический записывать деление с остатком / взятие остатка, вывел свою точную формулу вычисления дня недели для любой даты григорианского календаря. Да и цикл в 28 лет эмпирический нашел. А когда еще прочитал пару книжек про историю календаря — все стало на свои места. Но, блин, сколько бы я потом не спорил, из примерно 100 окружающих я не смог убедить ни одного человека в том что 2000 год это XX век :(
                                          0
                                          Да, есть такие странные убеждения и они широко распространены. Из таблицы видно, что если век начинается не с первого года, то закономерности рушатся. И, конечно, это всё следует из структуры календаря.

                                          Есть ещё большие споры про десятилетия. Какие года правильно называть шестидесятыми, семидесятыми, и т. д. На Википедии было пару лет назад огромное обсуждение на эту тему с хорошими аргументами.
                                            0
                                            Можно провести следующую аналогию:
                                            Ящик пива заканчивается двадцатой бутылкой. Новый начинается с двадцать первой.
                                              0
                                              Можно проводить любые аналогии, но для людей «не умеющих в математику и гордящихся этим» (а таких, вне Хабра, большинство — да и на Хабре их много) это всё неважно. 2000 — дата круглая, красивая… а 2001 — это что?
                                                0

                                                Правильные люди праздновали линолеум как минимум четырежды.
                                                И пофиг, что правильных только два.

                                            0
                                            а если просто перебрать календари за 28 лет?
                                              +1
                                              Интересный факт: с 1 по 13 февраля 1918 года в Советской России не родился ни один человек.
                                              Это накрыло демографической волной с 4-15 октября 1582г?
                                                0
                                                Когда она, наконец, дошла из Европы =)
                                                +1
                                                Тогда вы готовы решить следующую олимпиадную задачу по информатике: доказать, что 13 число чаще выпадает на пятницу, чем на другие дни недели.
                                                Особый шик — решить с карандашиком, без компа.
                                                  0
                                                  Замечательная задача!

                                                  Для начала вспомним, что в григорианском календаре возможно 14 различных годов. Первое января может приходиться на любой из семи дней недели, да ещё каждый год может быть високосным или невисокосным.

                                                  Посмотрим на таблицу сдвигов дней недели на 13 число каждого месяца от дня недели на первое января:
                                                      Янв Фев Март Апр Май Июнь Июль Авг Сен Окт Нояб Дек
                                                  Н:    5   1    1   4   6    2    4   0   3   5    1   3
                                                  В:    5   1    2   5   0    3    5   1   4   6    2   4
                                                  

                                                  Назовём «невисокосной неделей» семь невискосных годов, начинающихся на каждый день недели. Тогда «високосная неделя» — это семь таких високосных годов.

                                                  По таблицам сдвигов можно посчитать, что если полностью проходит високосная или невисокосная «недели», то 13 число будет одинаковое количество раз (по 12) приходиться на каждый день недели.

                                                  Двадцативосьмилетний цикл состоит из одной високосной недели и трёх невисокосных. Отсюда легко понять, что чтобы доказать утверждение надо рассмотреть неполные двадцативосьмилетние циклы. Их шесть: три приходятся на начало 2, 3 и 4 столетий, три приходятся на конец 1, 2 и 3 столетий в четырёхсотлетнем цикле.

                                                  Подсчитаем в этих неполных циклах количество всех типов годов и найдём НЕПОЛНЫЕ невисокосные и високосные «недели». Посмотрим, сколько в них годов с учётом високосности:
                                                      Пн Вт Ср Чт Пт Сб Вс
                                                  Н:      1     1
                                                  В:      1  1     2     2
                                                  

                                                  Для этих годов подсчитаем количество раз, которое 13 число приходится на каждый день недели:
                                                  Пн Вт Ср Чт Пт Сб Вс
                                                  13 13 15 12 16 12 15
                                                  

                                                  Видно, что 13 число действительно чаще выпадает на пятницу, чем на другие дни недели. ЧТД.

                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                Самое читаемое