Главная страница «Первого сентября»Главная страница журнала «Информатика»Содержание №20/2008


В мир информатики
Семинар

Как узнать номер дня недели?

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

Занумеруем дни

Для этого просто присвоим какому-нибудь дню № 1, а дальше будем нумеровать дни по порядку: № 2, № 3
и т.д. Какой именно день взят за первый, все равно, пусть это, например, будет 1 января 1-го года. Тогда 2 января 1-го года получит № 2, 3 января 1-го года — № 3 и т.д.
31 января 1-го года станет днем № 31, 1 февраля — днем № 32, 1 марта — днем № 60 (в феврале 1-го года было 28 дней, потому что год не високосный). Всего в 1-м году было 365 дней, так что 1 января 2-го года будет днем № 366, 1 января 3-го года — днем № 731, 1 января
4-го года — днем № 1096, а 1 января 5-го года — днем
№ 1462 (4-й год содержал 366 дней). Таким образом, каждый день получит свой номер.

Как узнать день недели, зная номер дня?

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

 

Решим сначала простую задачу.

Задача. Дано целое число z (1 ? z ? 365). Рассмотрим z-й день года, в котором 1 января — понедельник. Определить номер дня недели (воскресенье — 0, понедельник — 1, вторник — 2, …, суббота — 6), на который приходится этот день года.

Решение

Если z = 1, то соответствующий день — понедельник, если z = 2 — вторник, …, если z = 6 — суббота, если z = 2 — воскресенье, … А как решить задачу в общем виде?

Можно рассуждать так. С начала года до z-го дня прошло какое-то количество полных недель и еще d дней. Например, при z = 100 — 14 полных недель и еще 2 дня. Количество прошедших полных недель нас не интересует — нам надо исследовать неполную неделю. Тот факт, что на неполной неделе прошло 2 дня, говорит о том, что 100-й день — вторник. На основе этих рассуждений можем сделать вывод о том, что искомый номер дня недели равен остатку от деления числа z на 7.

После этого вернемся к вопросу о “миллионном” дне. Возьмем, скажем, день № 100?000. Между ним и миллионным днем должно пройти 1?000?000 – 100?000 = 900?000 дней. Поделим 900?000 на 7 с остатком: 900?000 = 128?571 • 7 +
+ 3, т.е. между рассматриваемыми днями должно пройти целое число недель и еще три дня. Число недель для нас совершенно не важно, значение имеют только эти три дня. В частности, если 100 000-й день был понедельник, то 1 000 000-й день — четверг, если 100 000-й
день — вторник, то 1 000 000-й день — пятница и т.д. Теперь алгоритм действий ясен. Сначала определим номер какого-нибудь дня, для которого день недели нам известен. Эту работу можно проделать раз и навсегда. Затем мы определяем номер интересующего нас дня. Сравнивая два полученных номера, мы определяем день недели, отвечающий второй дате — как объяснялось выше.

Как найти номер дня?

Пусть нас интересует k-й день m-го месяца N-го года. Годы, как известно, бывают високосные и невисокосные. Невисокосные годы содержат 365 дней, високосные — 366 дней. Год является високосным, если его порядковый номер кратен 4, однако при этом годы, номера которых кратны 100, являются високосными только при условии, что их номера кратны 400. (Таким образом, 2000 год — високосный, а 1900-й — нет, в отличие, скажем, от 1904 года. Эта оговорка отличает “григорианский календарь”, или “новый стиль”, от “юлианского календаря”, или “старого стиля”. Подробнее о старом и новом стилях рассказано в статье “О старом и новом стиле” в этом выпуске.)

Вернемся к рассматриваемому дню. После дня № 1, т.е. 1 января 1-го года, прошло N – 1 лет, m – 1 месяцев и k – 1 день. Пусть среди этих N – 1 лет было N1 високосных и N2 невисокосных. Потом мы подумаем, чему равны N1 и N2, а пока запишем, что эти годы содержат 366N1 + 365N2 дней. Числа дней в 1-, 2-, …, 12-м месяце мы обозначим через а1, а2, …, а12. Вспомнив число дней в том или ином месяце, можем записать: а1 = а3 = а5 =
= а7 = а8 = а10 = а12, а4 = а6 = а9 = а11, а а2 = 28 или а2 = 29,
в зависимости от того, високосный или невисокосный N-й год. Итак, номер нашего дня равен:

366N1 + 365N2 + а1 + а2 + … + аm – 1 + k. (1)

Теперь найдем N1 и N2. Представим N – 1 в виде 100P + R, где 0 LesQ.gif (292 bytes) R LesQ.gif (292 bytes) 99 (если N – 1 — четырехзначное число, как это на практике обычно бывает, то Р
и R — двузначные числа, записываемые первыми двумя и последними двумя цифрами числа N – 1). Далее, поделим Р и R на 4 с остатком: Р = 4р + q, R = 4r + s (0 LesQ.gif (292 bytes) q LesQ.gif (292 bytes) 3, 0 LesQ.gif (292 bytes) s LesQ.gif (292 bytes)3).

Нашему году предшествовало Р полных столетий. В каждом было 99 лет, номера которых не делятся на 100, из них 24 года високосных и 75 лет невисокосных. Из Р лет с номерами, делящимися на 100, високосных было р, а невисокосных Р – р = 3p + q. Наконец, из R последних лет было r високосных и R – r = 3r + s невисокосных. Итак,

N1 = 24P + p + r = 97p + 24q + r,

N2 = 75P + 3p + q + 3r + s = 303p + 76q + 3r + s.

Подставив эти значения в (1), получим окончательную формулу для номера нашего дня:

366(97p + 24q + r) + 365(303p + 76q + 3r + s) + а1 +
+ а2 + … + аm – 1 + k = 146?097p + 36?524q + 1461r + 365s +
+ а1 + а2 + … + аm – 1 + k. (2)

Например, пусть интересующая нас дата 1 марта 1994 года. Для этого дня Р = 19, R = 94, р = 4, q = 3, r = 23, s = 1, m = 3, а1 = 31, а2 = 28, k = 1, и его номер 727 988.

Нам нужен только остаток от деления на 7!

Номер дня, как показано выше, интересует нас лишь с точностью до любого числа, делящегося на 7 (ибо день нас интересует лишь с точностью до целого числа недель). Поэтому уместно заметить, что 146 097 = 20 871 • 7 делится на 7, так что первое слагаемое в сумме (2) можно просто отбросить. Далее, 36 524 = 5217 • 74 + 5, так что вместо коэффициента 36 524 можно взять 5; точно так же вместо 1461 и 365 можно взять 5 и 1. Наша огромная сумма в (2) превратится в

5(q + r) + s + а1 + а2 + … + аm – 1 + k, (3)

к тому же и для а1…а12 значения 28, 29, 30, 31 можно безболезненно заменить их остатками от деления на 7, т.е. значениями 0, 1, 2, 3 соответственно. Тогда для
1 марта 1994 года наш номер заменится числом

5(3 + 23) + 1 + 31+ 28 + 1 = 191,

которое заведомо имеет такой же остаток от деления на 7, как номер нашего дня — 728 353 (действительно, проверка показывает, что у обоих чисел этот остаток равен 2).

39-0.gif (17632 bytes)

Расчет по формуле (3)

Наиболее трудоемкая часть вычисления по формуле (3) — это нахождение суммы а1 + а2 + … + аm – 1, или, вернее, остатка от деления этой суммы на 7. Этот остаток зависит от номера месяца m и от того, является ли год високосным. Например, сумма, отвечающая августу високосного года, есть 31 + 29 + 31 + 30 + 31 + 30 + 31, ее остаток от деления на 7 совпадет с остатком числа
3 + 1 + 3 + 2 + 3 + 2 + 3 = 17, т.е. равен 3.

Имеет смысл вычислить такие остатки раз и навсегда и записать результаты в таблицу (верху справа):

Номер дня равен остатку

Если провести расчеты по формуле (3), например, для 17 декабря 2008 года, то окажется, что остаток равен 2. Теперь посмотрите в календарь и убедитесь, что этот день — вторник. Значит, если остаток от деления номера дня на 7 равен 6, то день — вторник. Соответственно, если остаток равен 1, 3, 4, 5, 6, то день — понедельник, среда, …, пятница, суббота, если 0 — воскресенье (проверьте для разных дней!). Как видим, нам немножко повезло: остаток от деления получившегося числа на 7 просто равен номеру дня недели (при нумерации с нуля, начиная с воскресенья):

1 — понедельник;

2 — вторник;

3 — среда;

4 — четверг;

5 — пятница;

6 — суббота;

0 — воскресенье.

(Везение состоит в том, что наугад взятый нами первый день — 1 января 1-го года — оказался понедельником. Если бы не это, нам пришлось бы внести в формулу (3) крохотную поправку.) Теперь мы можем написать окончательную формулу.

Окончательная формула

Рассмотрим k-й день m-го месяца N-го года. Обозначим через R двузначное число, составленное из двух последних цифр числа N – 1, и через Р — число, составленное из остальных цифр числа N – 1. Далее, поделим числа Р и R с остатком на 4: Р = 4р + q, R = 4r + s. Затем найдем число

D = 5(q + r) + s + b + k,

где b зависит от месяца и “високоcноcти” N-го года и находится из таблицы остатков, приведенной выше.

Остаток от деления числа D на 7 — это и есть искомый номер дня недели.

Пример. Великая Отечественная война началась 22 июня 1941 года. Какой это был день недели?

Вычисляем: Р = 19 = 4 • 4 + 3, R = 40 = 4 • 10 + 0, b = 4 (июнь невисокосного года), D = 5(3 + 10) + 0 + 4 + 22 =
= 91. Остаток от деления числа D на 7 равен 0. Значит, это было воскресенье.

Литература

1. Журнал “Квант”, 1988, № 12.

TopList