Project Euler (answers)

Проект Эйлера: Ответ и решение 19 задачи (Считаем воскресенья)

Проект Эйлера (19 задача) потребует лишь понимания, что такое “високосный год” и вычисляется практически мгновенно.

Узнать больше в телеграм-канале: ProjectEuler++

Условия задачи

Дана следующая информация (однако, вы можете проверить ее самостоятельно):
1 января 1900 года – понедельник.
В апреле, июне, сентябре и ноябре 30 дней.
В феврале 28 дней, в високосный год – 29.
В остальных месяцах по 31 дню.
Високосный год – любой год, делящийся нацело на 4, однако последний год века (ХХ00) является високосным в том и только том случае, если делится на 400.
Сколько воскресений выпадает на первое число месяца в двадцатом веке (с 1 января 1901 года до 31 декабря 2000 года)?

Содержание статьи

Решение задачи

Измеряем время работы программы
Ответ и скорость работы программы

Решение (проект Эйлера - 19 задача)

Суть алгоритма проста.

Примем понедельник некой даты за первый день и начнем считать последующие дни. Сколько бы дней ни прошло – каждый седьмой будет воскресеньем.

Поскольку 1 января 1901 года – это вторник, потому начнем считать сразу со второго дня.

Количество дней в месяцах сохраним в массиве:

int month_days[] = {31, 28, 31… 30, 31};

Перебирая годы и месяцы в году, будем к исходному количеству прибавлять количество дней в месяце.

day += month_days[month];

Каждый февраль високосного года (смотрите задание) будем добавлять еще один день:

if (month == 1 && year % 4 == 0)
- day++;

Если после прибавления дней в месяце количество дней делится на семь, то найдено еще одно воскресенье первого числа месяца.

Измеряем время работы программы

Для измерения времени работы программы подключаем библиотеку time.h:

#include <time.h>

С помощью функции clock() измеряем время начала (begin) и окончания (end) работы программы. В итоге время работы будем находить как разность между ними.

* Примечания:

clock_t

clock_t это тип данных, определенный через typedef. По сути это обычный целочисленный long

(double)

(double) приводит число (в данном случае – результат вычислений end – begin) к вещественному типу данных double (числа с точкой)

CLOCKS_PER_SEC

CLOCKS_PER_SEC – это константа, сохраненная в библиотеке и зависящая от типа устройства, на котором запускается программа. В данном случае – это просто 1000

Ответ и скорость работы программы (проект Эйлера - 19 задача)

В итоге ответ на 19 задачу проекта Эйлера составил 171, программа считает ответ мгновенно.

По традиции хотелось бы выразить глубочайшую признательность Сергею Балакиреву за его титанический труд по созданию бесплатных курсов и в частности, за “Язык программирования C/C++ для начинающих“.

Есть вопросы, господа? Отвечаем спокойно, четко и только по делу))

Есть вопросы, господа?

Политика конфиденциальности

Конфиденциальность