Правильность алгоритма Сакамото, чтобы найти день недели

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

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

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;
}

Ответ 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 и смещение от таблицы, которая зависит от месяца (поскольку границы месяца в течение года являются довольно произвольными).

Затем возьмите всю вещь mod 7, так как это то, как долго проходит неделя.

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

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

[править]

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

Ответ 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.

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

Ответ 3

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

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

марта
апреляМожет
июня
июля
августа
сентября
октябряноябрь
декабря
января

февраляНаписание с января по декабрь сверху нумерация:

Итак, рассмотрим это как массив: 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

Вы можете найти эту формулу здесь: Википедия

int dayOfWeek(int d, int m, int y){
  // Months Array
  int t[] = {11,12,1,2,3,4,5,6,7,8,9,10};

  // Convert months array
  for (int i = 0; i < 12; i++){
    int ans = t[i] * 2.6 - 0.2;
    t[i] = ans % 7;
  }

  // Continue Algo
  if(m<3)
    y -= 1;

  int day = (y + y/4 - y/100 + y/400 + t[m-1] + d) % 7;
  return day;
}

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

Идеально делится на 400 → верно
ЕСЛИ отлично делится на 100, но не на 400 → Неверно
Делится на 4 → Верно

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

Я знаю, что это может быть не ответ, но это может помочь тем, кому трудно запомнить/понять что-то, да! не все из нас имеют высокий уровень IQ понимания вещей, и, к сожалению, некоторые из нас тоже не могут вспомнить вещи, смеется.

Ответ 4

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

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

Объяснение:

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

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

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

Каждый обычный год смещается на один день недели, а високосный год - на два дня недели. как (365% 7) = 1 и (366% 7) = 2

 i= y+y/4-y/100+y/400

Но мы не должны рассчитывать дополнительный день, если у високосный год для 0 и 1 месяца

y-=m<3

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

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