...

пятница, 3 июля 2015 г.

[Из песочницы] Формула подсчёта количества дней в месяце

Примечание: данный пост является переводом статьи http://ift.tt/1yTV54k (Часть I), а также авторским к нему дополнением (Часть II). Не следует относиться к материалу серьёзно, а скорее как к разминке для ума, требующей не более чем школьных знаний арифметики и не имеющей практического применения. Всем приятного чтения!

Вступление


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

ФормализуяДругими словами, необходимо найти функцию f, такую, что значение f(x) для каждого месяца x, представленного числом от 1 до 12, равняется количеству дней в этом месяце. Таблица значений аргумента и функции1:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 31 28 31 30 31 30 31 31 30 31 30 31

Если у вас возникло желание попробовать самому до прочтения моего решения, то сейчас самое время. Если же вы предпочитаете немедленно увидеть готовый ответ, то посмотрите под спойлер.
Ответ

Ниже следуют мои шаги по нахождению решения.

Математический аппарат


Сначала бегло освежим в памяти два жизненно необходимых в решении этой задачи оператора: целочисленное деление и остаток от деления.

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


Остаток от деления это оператор, находящий остаток от деления. Во многих языках программирования применяется символ %, я же буду использовать конструкции вида , например:

Замечу, что остаток от деления имеет равный с делением приоритет.

Основы


Итак, применим наш математический аппарат для получения базовой формулы.2 В обычном месяце 30 или 31 день, так что мы можем использовать для получения поочерёдно 1 или 0, а затем просто прибавить к этому числу константу:

Получаем таблицу, полужирным выделены корректные значения:
x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 31 30 31 30 31 30 31 30 31 30 31 30

Неплохое начало! Уже есть правильные значения для января и для месяцев с марта по июль включительно. Февраль — особый случай, и с ним мы разберёмся чуть позже. После июля для оставшихся месяцев порядок получения 0 и 1 должен быть изменён на обратный.
Для этого мы может прибавить к делимому 1:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 30 31 30 31 30 31 30 31 30 31 30 31

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

Наложение маски


Для этого необходима кусочно-заданная функция, но — так как мне это показалось скучным — я задумался о другом пути решения, использующем одну часть функции на одном интервале, другую — на другом.
Полагаю, что проще всего будет найти выражение, равное 1 в одной области применения и 0 — в остальной. Метод, в котором умножая аргумент на выражение мы исключаем его из формулы вне области его применения, я назвал «наложением маски», потому такое поведение подобно некой битовой маске.
Для применения этого метода в последней части нашей функции необходимо найти выражение, равное 1 при , и — так как значения аргумента всегда меньше 16 — для этого прекрасно подходит целочисленное деление на 8.
x 1 2 3 4 5 6 7 8 9 10 11 12
x8 0 0 0 0 0 0 0 1 1 1 1 1

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

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 31 30 31 30 31 30 31 31 30 31 30 31

Эврика! Всё правильно, кроме февраля. Сюрприз-сюрприз.

Февраль


В любом месяце 30 или 31 день, кроме февраля с его 28 (високосный год выходит за рамки этой задачи).3 На текущий момент по нашей формуле в нём 30 дней, поэтому неплохо бы вычесть выражение, равное 2 при .
Лучшее что мне удалось придумать это , что накладывает маску на все месяцы после февраля:
x 1 2 3 4 5 6 7 8 9 10 11 12
2 mod x 0 0 2 2 2 2 2 2 2 2 2 2

Изменив базовую константу на 28 с добавлением 2 к остальным месяцам получим формулу:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 29 28 31 30 31 30 31 31 30 31 30 31

К сожалению, январь теперь короче на 2 дня. Но, к счастью, получить выражение, которое будет применяться только для первого месяца очень легко: это округлённое вниз обратное к число. Умножив его на 2 получаем окончательную формулу:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x) 31 28 31 30 31 30 31 31 30 31 30 31

Послесловие


Вот она — формула для получения количества дней в любом месяце года, использующая простейшую арифметику. В следующий раз когда вы будете вспоминать сколько же дней в сентябре, просто выполните с помощью этой однострочной функции на JavaScript:
function f(x) { return 28 + (x + Math.floor(x/8)) % 2 + 2 % x + 2 * Math.floor(1/x); }

Вступление


В первой части была получена короткая и даже немного изящная формула, основными достоинствами которой являются простота математического аппарата, отсутствие ветвлений и условных выражений, лаконичность. К недостаткам — кроме того, что вы не будете применять её в вашем проекте — можно отнести отсутствие проверки на вискокосный и не високосный год.
Поэтому я поставил перед собой задачу создать функцию f, такую, что значение f(x, y) для каждого месяца x, представленного числом от 1 до 12 и года y, большего 0, равняется количеству дней в месяце x в году y.
Для нетерпеливых под спойлером находится готовый ответ, остальных же прошу следовать за мной.
Ответ

Остаток от деления: mod и ⌊⌋


Для визуальной наглядности договоримся, что в некоторых формулах оператор деления с остатком заменён нижними скобками, там где это показалось мне необходимым:

Високосный год


В високосный год вводится дополнительный день календаря: 29 февраля. Как известно, високосным является год, кратный 4 и не кратный 100, либо кратный 400. Запишем тождественное этому высказыванию выражение:

Математическим аналогом будет следующая функция g(y), значением которой будет 0, если год високосный, или число, большее 0 в обратном случае:


y 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004
g(y) 960 1446 0 486 976 1470 0 494 992 1494 0 2 8 18 0

Полужирным выделены високосные года.

Неплохо, но недостаточно. Следующим шагом необходимо к функции g(y) применить инъекцию вида:


Что позволит изменить значение функции на 1 для високосных лет и 0 для не високосных, чтобы использовать её в формуле определения количества дней в месяце:

В качестве функции g' можно использовать 1 минус остаток от деления для :
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
g'(x) Infinity 1 0 0 0 0 0 0 0 0 0 0 0 0 0

Легко заметить, что увеличив делимое и делитель на 1 мы получим правильную формулу при :
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
g'(x) 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Соответственно, применив функцию g' к значению функции g получаем формулу:

y 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004
g(y) 960 1446 0 486 976 1470 0 494 992 1494 0 2 8 18 0
g'(g(y)) 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1

Напоминаю, что в рамках принятой договорённости оператор получения остатка от деления может быть изображен как mod, так и ⌊⌋.

Наложение маски


В формуле часть является поправкой, прибавляющей 2 дня к январю. Если убрать множитель 2 и в числителе заменить 1 на 2, тогда эта формула будет прибавлять 2 дня к январю и 1 день к февралю, что даёт нам ключ к добавлению дня в високосном году. Для наглядности используем в формуле промежуточное значение g'(y) и в качестве y используем 2000 (високосный) и 2001 (не високосный) годы:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x, 2000) 31 29 31 30 31 30 31 31 30 31 30 31
f(x, 2001) 30 28 31 30 31 30 31 31 30 31 30 30

Значения для всех месяцев, кроме января не високосного года верны.

Для исправления этого досадного недоразумения добавим к январю 1 день уже известной нам формулой :


x 1 2 3 4 5 6 7 8 9 10 11 12
f(x, 2000) 32 29 31 30 31 30 31 31 30 31 30 31
f(x, 2001) 31 28 31 30 31 30 31 31 30 31 30 30

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

Так как , тогда формула итоговая формула примет вид:



Или:

x 1 2 3 4 5 6 7 8 9 10 11 12
f(x, 2000) 31 29 31 30 31 30 31 31 30 31 30 31
f(x, 2001) 31 28 31 30 31 30 31 31 30 31 30 30

Заключение


В результате получена уже значительно более громоздкая, но более универсальная формула, которую также можно использовать для получения количества дней в месяце определённого года:
function f(x,y) { return 28 + (x + Math.floor(x / 8)) % 2 + 2 % x + Math.floor((2 - ((y % 4) * ((y % 100) + (y % 400)) + 2) % ((y % 4) * ((y % 100) + (y % 400)) + 1)) / x) + Math.floor(1/x) - Math.floor((1 - ((y % 4) * ((y % 100) + (y % 400)) + 2) % ((y % 4) * ((y % 100) + (y % 400)) + 1))/x); }

Пример на C# ideone.com/dnmv7A.


1. Я не умею пользоваться подобной мнемоникой, поэтому подсмотрел табличку в интернете.
2. «Основы», или «Правило С Многими Исключениями», как и большинство правил.
3. Изначально в римском календаре февраль был последним месяцем года, поэтому есть логика в том, что он короче всех остальных. Также есть логика в добавлении или удалении дня именно в конце года, поэтому его длина является переменной.

This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.

Комментариев нет:

Отправить комментарий