Корректность алгоритма Сакамото для нахождения дня недели
Я использую алгоритм Сакамото, чтобы узнать день недели от указанной даты.
Может кто-нибудь сказать мне правильность этого алгоритма? Я просто хочу, чтобы это было с 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;
}
2 ответов:
Ну, вы можете сказать, просто глядя на него, что это правильно... Предполагая, что
t[]массив является правильным, который вы можете проверить с помощью всего 12 выборочных проверок (по одному для каждого месяца, используя любой день/год).The
y -= m < 3- это хороший трюк. Он создает "виртуальный год", который начинается 1 марта и заканчивается 28 февраля (или 29), помещая дополнительный день (если таковой имеется) в конец года; вернее, в концепомещая добавленный день для високосных лет в конце виртуального года, остальная часть выражения значительно упрощается.
давайте посмотрим на суммы:
(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 миллион годы.
[edit]
приведенный выше аргумент по существу является доказательством индукции. То есть, предполагая, что что формула работает для конкретного (y, m, d), вы доказать что он работает для (y+1,m,d) и (y,m, d+1). (Где y - "виртуальный год", начинающийся 1 марта.) Итак, ключевой вопрос заключается в том, изменяется ли сумма на правильную сумму при переходе от одного года к другому? Со знанием правил високосного года, и с "виртуальным годом" имея дополнительный день в конце года, это не тривиально.
недавно я написал сообщение в блоге об этом алгоритме здесь.
основная идея алгоритма заключается в том, чтобы в феврале и январе считать день недели с 31 декабря в прошлом году. Для всех остальных месяцев мы будем считать день недели от настоящее год 31 декабря. Мы делаем это в два сначала мы вычисляем день недели последнего дня месяца, предшествующего текущему месяцу
mпотом просто добавитьdдулю семь.31 Dec 1 BC-это воскресенье, которое кодируется как 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.более подробное объяснение вы можете найти в моем блоге.
Comments