В прошлый раз мы разбирали красивую математическую задачу о сумме нечётных квадратов. Помните, как мы перешли от простого цикла к элегантной формуле S₂н(n) = [n(4n² - 1)]/3?
Именно этот момент — переход от «как заставить компьютер считать» к «как найти математическую закономерность» — и есть суть Project Euler.
Переходим к первой задачке на проекте:
Если мы выпишем все натуральные числа кратные 3 или 5 не превосходящие 10, то получим 3, 5, 6 и 9. Сумма этих чисел 23.
Найдите сумму всех чисел кратных 3 или 5 меньших 1000.
Важный момент Project Euler: Здесь не просто нужно получить ответ. Нужно получить его эффективно. Да, для 1000 простой цикл сработает мгновенно. Но дух проекта в том, чтобы находить решения, которые справятся и с 10^15. Это учит нас думать на шаг вперёд.
Часть 1: Суммируем на Python
Нормальный первый шаг — написать цикл. Проверяем каждое число — если оно кратно 3 или 5, то прибавляем к финальному ответу. Такой метод грубой силы (brute force) вполне адекватен на первых шагах, чтобы убедится в понимании задачи и проверить решение на малых входных данных.
Таким образом ответ: 233168
Плюс: Код простой и наглядный.
Минус: Для гигантских входных данных(миллиарды) такой перебор будет очень медленным. Сложность O(n).
Часть 2: Второе решение — аналитическое (Математика в помощь)
Давайте рассмотрим немного другую задачу:
Найти сумму всех чисел кратных 3 не превосходящих n.
Посмотрим, какие числа делятся на 3: 3, 6, 9, 12, ....
Мы получаем очень простую последовательность — арифметическую прогрессию с шагом 3, и именно ее сумму необходимо вычислить.
Таких чисел k = (n - 1 )// 3, и по формуле суммы арифметической прогрессии получаем S(k) = 3 * (k + 1) * k // 2
Такая же формула применима для прогрессии с любым шагом m поэтому можем написать S(m, k) = m * (k + 1) * k // 2,
где m - шаг прогрессии, k - количество ее элементов от 1 до n.
Вернемся к исходной задаче, сумма чисел, кратных 3, — это сумма арифметической прогрессии. Для 5 ситуация аналогичная. Но числа, кратные 15, мы посчитаем дважды (и в сумму троек, и в сумму пятёрок). Это принцип включений-исключений в простейшем виде.
Ну чтож, можно писать код, пишем формулу для суммы прогрессии в общем виде:
euler_1_prog(3, n) + euler_1_prog(5, n) - euler_1_prog(15, n)
Вызываем функцию следующим образом, где n это длина рассматриваемого интервала натурального ряда - и получаем успешные результаты!
Неоспоримые плюсы:
- добились вычислительной сложности O(1).
- лучше поняли задачу - связь с комбинаторикой, прогрессиями.
- готовы делать обобщения! - расширить на 3, 4, 5 делителей —просто добавим больше слагаемых по принципу включений-исключений.
Заключение:
Что дальше? Часто правильное решение лежит не в области оптимизации циклов, а в области поиска математической закономерности.
Эта первая задача — отличный пример: казалось бы, простой перебор, но за ним скрывается изящная формула, которая делает решение мгновенным для любого n.
P.S. В следующих постах разберём, как подступиться к задачам на числа Фибоначчи и простые числа — классике Project Euler. Подписывайтесь, чтобы не пропустить!
#ProjectEuler #Программирование #Математика #Алгоритмы #Python #Обучение #арифметическаяпрогрессия
👉 Подписаться на Telegram-канал