Разница между двумя датами с использованием математики - PullRequest
0 голосов
/ 19 января 2019

Я прочитал формулу, чтобы определить разницу между двумя датами, используя математику с O (1) сложностью времени

365*year + year/4 - year/100 + year/400 + (153*month - 457)/5 + day - 306

с учетом

если номер месяца меньше 3, год- = 1 и месяц + = 12

по следующей ссылке показан весь код, который я цитирую

https://codeforces.com/contest/304/submission/3715756

Так, если кто-то может объяснить это, пожалуйста?

Ответы [ 3 ]

0 голосов
/ 19 января 2019

Это не полный ответ, но это какое-то объяснение.

Прежде всего

, если номер месяца меньше 3, год- = 1 и месяц + = 12

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

Удар 365*year + year/4 - year/100 просто обрабатывает високосные годы.

Часть day также ясна.

Теперь давайте удалим биты, которые не имеют значения, когда мы вычитаемдва значения и получить это значение для month

30*month + (3*month - 2)/5

Я не знаю логики, как это было получено (у меня есть только предположение в конце), но я могу сказать, почему это работает.Бит 30*month очевиден.И теперь, когда мы переместили февраль на его последнюю позицию, весь месяц в середине года имеет либо 30, либо 31 день.Запишем их:

  • Март - 31 - + 1
  • Апр - 30 - + 0
  • Май - 31 - + 1
  • Июнь - 30 - + 0
  • июль - 31 - + 1
  • август - 31 - + 1
  • сентябрь - 30 - + 0
  • октябрь -31 - + 1
  • ноя - 30 - + 0
  • декабрь - 31 - + 1
  • янв - 31 - + 1

Мыне волнует февраль, так как после него нет месяцев (мы заботились об этом раньше).Мы заботимся только об этом +1 дне, начиная со следующего месяца после этого!

Так что теперь нам нужна некоторая формула, которая бы соответствовала этому распределению +1 и +0.И похоже, что значение

(3*month - 2)/5

с целочисленным делением делает именно это.Вы можете легко проверить это вручную.

Вероятно, чтобы придумать эту идею, было бы заметить, что год (кроме февраля) следует за следующим 5-месячным циклом

+ 1+0 +1 +0 + 1

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

0 голосов
/ 19 января 2019

Единственная «забавная» часть заключается в том, что если вы вычислите (153*m-457)/5 для значений от 3 до 15, вы получите

0, 31, 61, 92, 122, 153, 184, 214, 245, 275, 306, 337

, где вычитая каждый элемент из предыдущего, начиная со второго, мы получаем

31, 30, 31, 30, 31, 31, 30, 31, 30, 31, 31

- это количество дней в каждом месяце, если мы начинаем с марта

Итак, идея такова: перевернитесь, чтобы "странный" февральский месяц стал последним, подсчитайтегоды, високосные дни и дни прошедших месяцев с использованием «магической» формулы, чтобы получить чистое число, увеличивающееся на единицу для каждого дня.

Вычитание двух из этих чисел дает разницу в дате.

PS: обратите внимание, что даже "обычное" вычисление будет O (1)

0 голосов
/ 19 января 2019

Давайте попробуем написать это формально:

f(y,m,d) = 365*y+ y/4 - y/100 + y/400 + (153*m- 457)/5 + d - 306
date_diff(y1,m1,d1,y2,m2,d2) = f(y1,m1,d1) - f(y2,m2,d2)

Упрощение:

date_diff = (y1-y2)*(365+1/4-1/100+1/400) + (m1-m2)*30.6 + (d1-d2)

И это имеет смысл, потому что:

  1. У нас високосный годкаждые 4 года, если только год не делится на 100, а не на 400.
  2. Среднее количество дней в месяце составляет ~ 30,6
  3. Все странные магические числа (306 и 457) идутпрочь
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...