Algorithms
Mathematics
March 2014 28

Вычисление дня недели в уме

Tutorial
imageСуществует множество способов прокачать мозг. Задачи «n-back» или мобильные приложения для тренировки навыка быстрого счета в уме. Но эти задачи оторваны от текущей реальности, а хотелось бы прокачать мозг практичным навыком.

Зачем? Ведь можно быстро посчитать на гаджете. Увы, совсем не быстро, т.к. потребуется время на поиски и активацию гаджета, поиск приложения, ввод даты, осознание полученного результата. А еще можно друзей/подруг порадовать своими внезапно появившимися экстраординарными способностями. Кстати, друзья быстро осознают удобство использования вечного календаря с голосовым интерфейсом.

Разве это возможно? Как-то раньше обходились без компьютеров. В одной из тв-передач «ищем таланты» показывали натренированного трехлетнего ребенка, который может вычислять произведение трехзначных чисел (пощадите своих детей). Впрочем, взрослые уже не дети и их мозг частично кристаллизован, в смысле слабо обучаем. Значит нужно запоминать как можно меньше и максимально задействовать имеющиеся навыки.

В алгоритмике часто объемы вычислений могут быть скомпенсированы объемами памяти. Т.е. чем больше оперативки доступно, тем меньше потребуется вычислений. Аналогично работает мозг – чем больше мы запомнили, тем быстрее ищем решение. Запомнили несколько формул для сборки кубика Рубика – соберете за пару минут (после длительной тренировки). Запомнили полторы сотни формул – соберете за пару десятков секунд. Мировой рекорд 2013 года – 8.18 сек. Еще раз: чем больше помним – тем быстрее решение.

Алгоритм

Нужно взять смещение (день недели) первого дня года (y) и смещение месяца (m). Затем вычислить сумму y+m+d, где d – день месяца, и найти остаток от деления на 7. Получим номер дня недели.

Что нужно запомнить

Размышления
В целом, достаточно запомнить все дни недели всех 28 лет (периодичность пропорциональна произведению периодов високосных лет и дней недели). Последовательность в 10k. Это довольно много.

Если добавить одну операцию сложения, то будет достаточно запомнить лишь пару рядов чисел:

m(month) = { 6 2 2 5 0 3 5 1 4 6 2 4 }, с января по декабрь

y(year) = { 6 0 1 2 4 5 6 0 2 3 4 5 0 1 2 3 5 6 0 1 3 4 5 6 1 2 3 4 }, с 1988 по 2015

Например: 13 сентября 2013 = (13 + 4 + 2) % 7 = 5 (пятница)

Смещения для месяца берутся из календаря некоторого года. Смещение месяца равно количеству серых квадратов в начале месяца. Например, не високосный 2006 год. Смещение для этого года будет 0.

image

Все же запомнить смещения для всех лет и затем выполнять быстрый поиск по индексу довольно сложная когнитивная задача. Есть альтернативный путь – вычислить. Нужно взять две последние цифры года (+100 для XXI века) — Y. Далее найти ближайший прошлый високосный Yв. Взять dY = Y – Yв. Тогда смещение года можно вычислить

y(Y) = (50 – Yв/2 + dY)

Недостаток формулы в том, что для 2004 и далее смещение будет отрицательным, а для начала и середины XX века двузначными, что слегка затрудняет вычисления в уме. Можно использовать разные формулы для каждого века, в которых учитываются только две младшие цифры года. Например, 12 для 2012г и 1912г.

XX: (50 – Yв/2 + dY) % 7 или (8 – Yв/2 % 7 + dY)
XXI: (7 – Yв/2 % 7 + dY)

В итоге может оказаться проще запомнить таблицу смещений в таком виде:

image

Смещение для года можно вычислить через сумму смещения ближайшего меньшего високосного года и его разницы с искомым годом. Семь цифр запомнить проще чем 28. К тому же, цифры расположены в убывающем порядке с шагом 2. (Да, да, (0 – 2) будет 5, помним про остаток от деления на 7). Можно запомнить цифры (6, 4, 2, 0, -2, -4, -6), что при вычислениях даст аналогичный результат. Года кратные 20 располагаются в косом квадрате 3х3 по схеме «ход конем» c 2000 годом в центре. Значения смещений месяцев и лет согласованы так, чтобы на 2000 год приходилось смещение 0. А шаг между соседними рядами 28 лет.

Например, для 2014 смещение будет y(2014) = y(2012) + 2 = 1 + 2 = 3. А день программиста 13 сентября 2014 года будет (y(2014) + m(сен) + 13) = (3 + 4 + 13) = 20 => 20 % 7 = 6, т.е. суббота.

Структурируем ряд смещений для месяцев. Значения удобно запоминать по сезонам: весна, лето, осень, зима.

image

Обратите внимание, что вдруг (?), в порядке сверху вниз и слева направо, цифры выстроились в возрастающий ряд (первая цветная таблица). Можно запоминать только остатки от деления на 7 (вторая цветная таблица) или для восстановления всей таблицы запомнить только разности (последняя таблица). Прибавляя 1 к 1, получим для марта 2, для июня 2+1=3, для сентября 3+1=4 и т.д. Одинаковые значения раскрашены в одинаковые цвета. Для быстрого поиска нам поможет вторая цветная таблица. Помним, что строки — это сезоны, начиная с весны. Это крайне непривычно. Но в древнем Риме год начинался именно с марта. Это отражено в названиях месяцев латинскими цифрами: September/October/November/December – 7/8/9/10, т.е. февраль был последним 12м месяцем года, к которому добавляли високосный день.

image

12 апреля 1961 года: (6 + 1 + 5 + 12) = (0 + 5 + 12) => 17 % 7 = 3 – среда.

Важно!!! У программистов вечная проблема с потерянной единицей. В нашей задачке без этого не обошлось. Для января и февраля високосного года нужно вычитать единицу.

14 февраля 2012 = (y(2012)+m(фев)+14) — 1 = (1 + 2 +14) — 1 => 16 % 7 = 2, т.е. вторник.

Еще нужно помнить, что не все года что делятся на 4 будут високосными (исключения — 2100, 1900, 1800, ….). Соответственно, необходимо учесть смещение для века. Впрочем, даже если не учитывать последнее исключение можно безошибочно оперировать днями недели за XX и XXI века, что достаточно для большинства житейских случаев.

Немного оптимизации.

Вычисления можно производить в потоковом режиме. Обычно дату рождения (или любую другую дату) сообщают начиная с дня месяца, например, 23 декабря 1913 года. Т.е. в процессе сообщения даты можно частично вычислить искомую сумму 23 + m(дек) = 27 или даже 23 % 7 + m(дек) = 2 + 4 = 6 и затем уже задуматься y(1913) = y(1912) + 1 = 3. В итоге сообщить 30 % 7 = (6 + 3) % 7 = 2, вторник.

Часто приходится оперировать датами текущего года. Т.е. смещение года вы всегда будете помнить, т.к. от частого использования значение «закэшируется». Например, для 2014 смещение равно 3.

Что мы получили. Правила заполнения таблиц простые и вы скорее всего их запомнили и сможете воспроизвести себе шпаргалку в любом месте в любое время. Но для быстрого счета таблицы проще заучить целиком. Ведь мы не восстанавливаем таблицы сложения и умножения для расчета сдачи перед кассой. Эти таблицы «прошиты» еще в начальной школе. Для запоминания таблиц легче всего воспользоваться тренажером Week Brain Calc (Windows Phone).

После непродолжительной тренировки можно порадовать любимых своими уникальными способностями.

+42
74.5k 382
Comments 20