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

Question

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

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

int dow(int y, int m, int d)
{
   static int t[] = {0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4};
   y -= m < 3;
   return (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
}

Answer 1

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

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

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

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

(y + y/4 - y/100 + y/400 + t[m-1] + d) % 7

В нормальном году 365 дней. Это 52 недели плюс 1 день. Таким образом, день недели смещается на один день в год в целом. Именно этому способствует термин y; это добавляет один к дню для каждого года.

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

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

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

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

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

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

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

[править]

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

Answer 2

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

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

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

Последняя часть, которую необходимо объяснить, это значения в массиве, для первых двух значений это количество дней с прошлого года с 31 декабря до начала месяца % 7. В остальные месяцы они являются отрицательными по модулю семь число дней с конца предыдущего месяца до 31 декабря текущего года. Другими словами, мы вычитаем дни путем сложения по модулю 7, например. (a-b)%7 = (a+(7-b%7))%7.

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