Задача
Дана следующая информация (однако, вы можете проверить ее самостоятельно):
- 1 января 1900 года - понедельник.
- В апреле, июне, сентябре и ноябре 30 дней.
В феврале 28 дней, в високосный год - 29.
В остальных месяцах по 31 дню. - Високосный год - любой год, делящийся нацело на 4, однако последний год века (ХХ00) является високосным в том и только том случае, если делится на 400.
Сколько воскресений выпадает на первое число месяца в двадцатом веке (с 1 января 1901 года до 31 декабря 2000 года)?
Решение
Всего дней в указанном периоде примерно 365 * 100, т.е. 36500. Можно запросто пробежать в цикле по каждому числу каждого месяца и одновременно считать дни недели, так что никакой проблемы здесь нет.
Всё, задача решена! :)
Но поищем более умное решение.
Дата 1 января 1900 удобна тем, что стартует с первого числа и понедельника. Чтобы узнать количество воскресений в любом сроке после этой даты, надо количество прошедших дней разделить на 7.
Но интересует не количество воскресений, а остаток от деления на 7. Это сколько дней прошло с начала недели: 0 это понедельник, 1 это вторник, 2 это среда, ... 6 это воскресенье. То есть если сегодня 1-е число месяца и остаток от деления прошедших с 01.01.1900 дней равен 6, то воскресенье выпадает на 1-е число месяца.
Так как мы начинаем цикл с 01.01.1901, то уже прошёл год и поэтому сразу зададим счётчик прошедших дней, равный 365.
Далее будем перебирать годы, а в годах перебирать месяцы. В каждом месяце нужна только одна проверка на остаток. Затем количество дней в месяце прибавляется к количеству прошедших дней, и переходим на 1-е число следующего месяца.
Справочник количества дней в месяцах и функция определения високосного года:
Расчёт:
Ссылка на онлайн-компилятор языка C с текстом программы
Подборка всех задач: