Правильность алгоритма Сакамото на поиск дня недели

StackOverflow https://stackoverflow.com/questions/6385190

Вопрос

Я использую алгоритм Сакамото, чтобы узнать день недели по заданной дате. Кто-нибудь может сказать мне правильность этого алгоритма?Я просто хочу это с 2000 по 2099 год.

Алгоритм из Википедии приведен для справки.

родовое слово
Это было полезно?

Решение

Что ж, вы можете сказать, просто взглянув на него, что это правильно ... Предполагая, что массив t[] верен, что вы можете проверить с помощью всего 12 выборочных проверок (по одной на каждый месяц с использованием любого дня / года).

Генерикодический тег-код - это хороший трюк. Он создает «виртуальный год», который начинается 1 марта и заканчивается 28 (или 29) февраля, помещая дополнительный день (если есть) в конец года; точнее, в конце предыдущего года. Так, например, виртуальный 2011 год начался 1 марта и закончится 29 февраля, а виртуальный 2012 год начнется 1 марта и закончится 28 февраля следующего года.

Если добавить день високосного года в конце виртуального года, остальная часть выражения значительно упрощается.

Давайте посмотрим на сумму:

родовое слово

В нормальном году 365 дней. То есть 52 недели плюс 1 день. Таким образом, день недели в целом сдвигается на один день в году. Это то, что вносит термин y -= m < 3; он добавляет один день к каждому году.

Но каждые четыре года - високосный. Они вносят дополнительный день каждые четыре года. Благодаря использованию виртуальных лет мы можем просто добавить к сумме общий кодовый код, чтобы подсчитать, сколько високосных дней произошло в году с общим кодовым кодом. (Обратите внимание, что в этой формуле предполагается, что целочисленное деление округляется вниз .)

Но это не совсем так, потому что каждые 100 лет - это не високосный год. Таким образом, нам нужно вычесть общий код кода.

За исключением того, что каждые 400 лет снова високосный. Поэтому нам нужно добавить общий кодовый код.

Наконец, мы просто добавляем код дня месяца y и смещение из таблицы, которое зависит от месяца (поскольку границы месяца в году довольно произвольны).

Тогда возьмите весь мод 7, так как именно столько длится неделя.

(Если бы недели составляли, например, восемь дней, что бы изменилось в этой формуле? Ну, очевидно, это был бы мод 8. Кроме того, y/4 должен был бы быть y, потому что 365% 8== 5. Также месяц необходимо изменить код таблицы. Вот и все.)

Между прочим, заявление Википедии о том, что календарь «годен до 9999», совершенно произвольно. Эта формула хороша до тех пор, пока мы будем придерживаться григорианского календаря , будь то 10 лет, 100 лет или 1000 лет. лет, или 1 миллион лет.

[редактировать]

Приведенный выше аргумент является доказательством по индукции. То есть, предполагая , что формула работает для определенных (y, m, d), вы докажете , что она работает для (y + 1, m, d) и ( у, м, д + 1). (Где y - «виртуальный год», начинающийся 1 марта.) Итак, ключевой вопрос заключается в том, изменяется ли сумма на правильную величину при переходе от одного года к другому? Зная правила високосного года и учитывая, что «виртуальный год» имеет дополнительный день в конце года, это тривиально.

Другие советы

Недавно я написал в блоге сообщение об этом алгоритме здесь .

Основная идея алгоритма - считать день в феврале и январе. недели с 31 декабря предыдущего года . Для всех остальных месяцев день недели будет отсчитываться от текущего года 31 декабря. Это делается за два Сначала мы вычисляем день недели последнего дня месяца, предшествующего текущему месяцу, сгенерированный кодовый код, затем мы просто добавляем код сгенерированного кода по модулю семь.

31 декабря 1 года до н.э. - воскресенье, кодируемое как 0, понедельник - 1 и т. д. Итак, у нас есть: m это с помощью d вычисляет день недели 31 декабря текущего года или предыдущего года (в зависимости от месяца). Примечание: 0 + y + y/4 - y/100 + y/400 это объясняет, почему мы написали y -= m < 3 вместо 365 % 7 == 1. Последний компонент y очевиден, поскольку мы начинаем отсчет дня недели с предыдущего месяца в последний день.

Последняя часть, которую необходимо объяснить, - это значения в массиве, для первых двух значений это количество дней с 31 декабря прошлого года до начала месяца, генерирующего код. Для остальных месяцев они инвертируются по модулю семь количества дней с конца предыдущего месяца до 31 декабря текущего года. Другими словами, мы вычитаем дни сложением по модулю 7, например 365*y.

Дополнительное объяснение вы можете найти в моем сообщении в блоге.

Это может быть не полный ответ, как некоторые из упомянутых выше, но я просто хотел бы добавить одну вещь относительно этого массива: 0 3 2 5 0 3 5 1 4 6 2 4

Считайте месяцы, начиная с марта и заканчивая февралем, как говорили другие:

  1. март
  2. апрель
  3. май
  4. июнь
  5. июль
  6. август
  7. сентябрь
  8. Октябрь
  9. ноябрь
  10. декабрь
  11. Январь
  12. Февраль

Запись с января по декабрь сверху. Стиль нумерации:

Рассмотрим это как массив: int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

Теперь для всех элементов в массиве просто выполните: (2.6*m - 0.2) mod 7 проанализируйте результат как целое число, и вы получите следующее: 0 3 2 5 0 3 5 1 4 6 2 4

  • Вы можете найти эту формулу здесь: wikipedia
родовое слово

this: + y/4 - y/100 + y/400 относится к високосному году. Алгоритм проверки високосного года:

  1. Идеально делится на 400 -> правда
  2. ЕСЛИ полностью делится на 100, но не на 400 -> Неверно
  3. Делится на 4 -> Верно

выполнить проверку указанного выше заказа. Может быть, поэтому они вычли y / 100 и добавили y / 4 и y / 400. Ага, глупая логика

Для григорианского календаря

родовое слово

Пояснение:

  • См. закомментированный массив для
родовое слово

и сравните его с календарем на целый год (запустите cal 2, чтобы сгенерировать календарь в терминале в linux / unix), обратите внимание на начальный день недели каждого месяца.

  • Каждый обычный год со сменой одного дня недели, а в високосном году - со сменой двух дней недели.как (365% 7)= 1 и (366% 7)= 2
родовое слово
  • Но нам не следует рассчитывать дополнительный день, если y високосный год для месяцев 0 и 1.
родовое слово

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

    int t[12]={0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top