WikiDer > Проект Эйлер

Project Euler
Проект Эйлер
Эйлер
Тип сайта
Веб-сайт для решения проблем
СозданКолин Хьюз
URLprojecteuler.net
КоммерческийНет
Постановка на учетСвободный
Запущен5 октября 2001 г.

Проект Эйлер (названный в честь Леонард Эйлер) - это веб-сайт, посвященный ряду вычислительных задач, предназначенных для решения с помощью компьютерных программ.[2][3] Проект привлекает взрослых и студентов, интересующихся математика и компьютерное программирование. С момента своего создания в 2001 году Колином Хьюзом проект Euler приобрел известность и популярность во всем мире.[4] Включает более 700 задач,[5] с добавлением нового каждые одну или две недели. Проблемы бывают разной сложности, но каждая из них может быть решена менее чем за минуту процессорного времени с использованием эффективного алгоритма на компьютере со скромной мощностью. По состоянию на 5 апреля 2020 г., Project Euler насчитывает более 1 000 000 пользователей со всего мира, которые решили хотя бы одну проблему.[6]

Особенности сайта

Форум, посвященный каждому вопросу, можно просмотреть после того, как пользователь правильно ответил на данный вопрос.[7] Проблемы можно сортировать по идентификатору, количеству решенных проблем и сложности. Участники могут отслеживать свой прогресс по уровням достижений в зависимости от количества решенных задач. Новый уровень достигается за каждые 25 решенных задач. Существуют специальные награды за решение особых комбинаций задач. Например, есть награда за решение пятидесяти задач с простыми номерами. Для отслеживания достижений существует специальный уровень «Эйлера», основанный на пятидесяти самых быстрых решениях недавних проблем, так что новые участники могут соревноваться, не решая старые проблемы.[8]

Пример проблемы и решения

Первая проблема проекта Эйлера:

Если мы перечислим все натуральные числа ниже 10, которые кратны 3 или 5, мы получим 3, 5, 6 и 9. Сумма этих кратных 23.

Найдите сумму всех кратных 3 или 5 ниже 1000.

Хотя эта проблема намного проще, чем типичная проблема, она служит для иллюстрации потенциальной разницы, которую создает эффективный алгоритм. В грубая сила алгоритм проверяет каждое натуральное число меньше 1000 и сохраняет текущую сумму тех, которые соответствуют критериям. Этот метод прост в реализации, как показано ниже. псевдокод:

Всего := 0для NUM от 1 до 999 делать    если NUM мод 3 = 0 или NUM мод 5 = 0 тогда        Всего := Всего + NUMвернуть Всего

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

Вот, обозначает сумму кратных ниже .В нотация большой O, алгоритм перебора О(п) и эффективный алгоритм О(1) (при условии арифметических операций с постоянным временем).

Смотрите также

использованная литература

  1. ^ "Обзор сайта Projecteuler.net". Alexa Интернет. Получено 22 октября 2018.
  2. ^ Сури, Манил (12.10.2015). «Важность развлекательной математики». Нью-Йорк Таймс. Получено 2018-06-05.
  3. ^ Фут, Стивен (2014). Обучение программированию. Учебные серии Аддисона-Уэсли. Pearson Education. п. 249. ISBN 9780789753397.
  4. ^ Джеймс Сомерс (июнь 2011 г.). «Как я потерпел неудачу, потерпел неудачу и, наконец, преуспел в обучении программированию - технологии». Атлантический океан. Получено 2013-12-14.
  5. ^ «Проект Эйлер (список проблем)». Получено 2020-05-05.
  6. ^ «Project Euler (Статистика) - требуется авторизация». Получено 2019-06-10.
  7. ^ «Проект Эйлер - О проекте». Получено 2008-04-04.
  8. ^ "Проект Эйлер (Архив новостей)". Получено 2015-03-31.

внешние ссылки