Project Euler — решайте алгоритмические задачи и смотрите как это делали другие 30к участников на огромном количестве языков.

    Пару-тройку месяцев назад наткнулся на замечательный ресурс Project Euler.

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

    Для участия в проекте надо пройти быструю регистрацию, после чего можно смело штурмовать алгоритмы.
    подробно — внутри
    Изюминка ресурса в том, что вы можете решить задачу на любом удобном для вас языке, надо только вписать в форму правильный ответ.
    После того как будет дан ответ вы сможете войти в ветку форума по данной задаче и увидеть какими методами данную задачу решили остальные участники, которых за время проекта набралось огромное количество (So far 29276 users have submitted 537919 correct solutions; that is an average of 18 problems per user).

    Вы можете посмотреть как данную задачу решили на почти всех живых языках программирования, увидеть красивые решения и грубый брутофорс)

    По мере прохождения сложность задач увеличивается.

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

    Выдержки из статистики:
    язык количество участников
    C/C++ 3726
    python 2900
    Java 1782
    C# 917
    Assembler 37
    F# 97
    Haskell 945
    Fortran 32
    Nemerle 8
    Ada 16
    R 7
    Prolog 2
    Boo 6
    PHP 425
    Pencil/Paper 291
    Ruby 804



    Вот так, к примеру, выглядит самая первая задача из 200штук:
    Add all the natural numbers below one thousand that are multiples of 3 or 5.

    Вот так 50-я
    Which prime, below one-million, can be written as the sum of the most consecutive primes?

    100я
    Investigate the optimum polynomial function to model the first k terms of a given sequence.
    Удачного погружения
    Поделиться публикацией

    Комментарии 48

      +2
      А паскаль забыли(
        +3
        есть он там, я просто его не привел.
        +6
        очень познавательно
        выскажу пару идей после ознакомления:
        — можно измерять «быстроту»/«красивость» различных языков
        — данный ресурс показывает что умение программировать — это умение составить алгоритм, а не умение написать реализацию
        — первая проблема датированна 2001 годом projecteuler.net/index.php? section=problems&id=1
        • НЛО прилетело и опубликовало эту надпись здесь
            0
            Просто на этом ресурсе, на самом деле, задачи по математике, а не по программированию.
            0
            Нудновато немного. Начиная с определенных, задачи становятся «на знание», такие, которые не решишь, не зная матаппарата, который лежит под задачей.
              0
              кроме этого ещё и перевести нужно правильно, иначе понять даже суть задачи будет нельзя.
                0
                На всех соревнованиях по програмированию (кроме олимпиад для школьников) задачи даются по-английски. Никого это не смущает.
                0
                Я бы не сказал, что задачи там «на знание». Точнее, просто знания необходимого мат. аппарата там просто недостаточно. Над многими из задач, даже зная всю необходимую теорию, приходится подумать. Я решил там почти все задачи и лишь в двух или трёх «упирался» в необходимость искать какую-нибудь формулу, которую я до этого не знал и не мог придумать сам.
                +2
                Если кто не знает, вот еще задачки: acm.uva.es/problemset/
                Тут уже количество языков поменьше, но проверяют не только правильность решения, но и скорость, и сожратую память.
                  0
                  Ага. Это самый старый из подобных сайтов. Я там зарегистрировался больше 10-и лет назад.

                  Ещё всем могу рекомендовать spoj.pl там большой выбор языков программирования и много интересных задач.
                  0
                  Ресурс для прокачки матан-скилла :)
                    +1
                    Матан там не совсем при делах ;) В основном дискретная математика, теория чисел и остальные «компьютерные» разделы математики.
                      0
                      ну тогда на дискран, теорвер, статы и опты :)
                        +1
                        Забыл алгебру и теорию чисел.
                    0
                    Кстати, кто-нить прошел в on-site rounds в google code jam?
                      0
                      У меня трое знакомых прошли. Я, к сожалению, не был в городе во время второго онлайн-раунда и пропустил его =(
                        0
                        я прошел, жду с нетерпением оглашения места проведения :)
                          0
                          В офисах Гугла они будут. В Москве и в Питере.
                            0
                            Ну вот меня и интересует — в Москву или Питер меня отправят. :)
                        0
                        Иногда решаю задачки с www.spoj.pl/. В отличие от описанного сайта, там можно самому выбрать понравившуюся задачу. Для каждой задачи есть ограничение по времени исполнения и/или размеру исходников.
                        Рейтинг считается в основном по скорости исполнения, иногда по размеру исходника. Можно смотреть рейтинги по отдельному языку…
                        Вот :)
                          0
                          У Эйлера тоже можно самому выбирать задачу :) там нет такого ограничения, что нужно проходить все подряд, просто чем дальше, тем обычно сложнее задания.
                          Но никто не мешает выполнить первые десять, потом промотать и порешать за пятьдесят и за сотню задания, как я делал.
                            0
                            Всё же сайт мне не нравится. Туда нужно отправлять не исходники а ответы. Это исключает такие пузомерки как скорость выполнения, занимаемая память и размер кода. Ну и статистика тоже соответственно не очень интересная.
                              0
                              Все дело в разной направленности сайтов :)
                              Проект Эйлера и не создан для любителей пузомерок, там смысл в том, чтобы сначала испытать себя, сможешь ли ты вообще задачу решить, а затем — почитать решения других и понять, как это можно было сделать эффективнее или просто иначе. В общем, не столько конкурс, сколько ресурс для самообразования.
                          0
                          я, конечно, английский, неплохо знаю, но не до такого уровня.
                          там нет русского интерфейса?
                            0
                            Я вот знаю английский плохо, но этого вполне достаточно чтобы понимать вопросы (вкупе с Яндекс-словарями если уж совсем непонятно).
                              0
                              0
                              На главной странице в разделе ЧаВО понравился вопрос о возможности пожертвований =)
                              Красиво и ненвязчиво.
                                +2
                                Клевый сайт, уже 3 дня спасает меня от скучной работы. До первого левелапа осталось пара задач. Решаю на языке tcl, стараюсь писать так, что бы прога работала на PDA Aser n311 не более минуты, пока в это ограничение не вписалось два решения. Так как там форум заморожен, а померяться письками охото, было бы круто создать здесь блог — Project Euler, где каждый пост посвящен решению одой задачи на конкретном языке, например, пост с именем 010-Haskell (теги project_euler_010, project_euler_haskell, haskell), где в комментариях проиходит треп по теме, автор приводит время работы своей программы и ссылку на исходный код, пояснения работы алгоритма в личном блоге. При такой структуре можно будет быстро сравивать свои результаты с результатами других и продолжать думать не зная эффективного алгоритма.

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

                                Предлагаю пообсуждать идею пока в комментах, написать манифест (правила, подобные правилам выше) и создать блог.
                                  0
                                  В принципе поддерживаю вашу идею(с интересом бы следил)… Только вот именно сайт Project Euler немного какой-то не такой =), хотя и поразвлекал вчера. А есть ещё такого типа проекты, кроме уже приведенных в комментах?.. Кажется TopCoder был, если не ошибаюсь… Хочется вот такое как Project Euler ток с большей статистикой, что-ли…
                                    +2
                                    www.topcoder.com/tc, acm.timus.ru, icpcres.ecs.baylor.edu/onlinejudge/
                                    вообщем-то похожие проекты. Еще проходил Google Code Jam.
                                  +1
                                  Интересно, раньше с этим проектом не сталкивался, хотя алгоритмическими задачками интересуюсь. Спасибо, посмотрим.
                                    0
                                    Там задачки скорее математические, чем алгоритмические.
                                      0
                                      Обычно интересные алгоритмы — это как раз связанные с какими-либо математическими вещами, так что это не плохо.
                                    0
                                    Давно решаю задачки с этого сайта. Правда последние полгода времени нет. А так решено 132 из 202 задач.
                                      0
                                      Забавно посмотреть как у одних решение занимает страницу, а у других полстроки.
                                        0
                                        мне кажется, с выключенным кешом и при помощи их каптчи их можно заDDOS'ить.
                                        случайно так вышло, аж 429 запросов на картинку.
                                          0
                                          Интересный проект, спасибо :)
                                          Хотел поделиться своим решением второй задачи, а там не разрешают его запостить, пишут Thread Locked (Archived).
                                            0
                                            Ну решение второй задачи такое же как у меня я нашёл ещё у двоих и успокоился :) (разве что у меня оно заняло одну строку, а не 5-10, но логика та же). А вот что касается решения первой задачи — аналога своему я не увидел, хотя с программистами кишущими на «K» мой PHP тягаться не может. Если Вы считаете решение интересным — поделитесь, т.к. в их форум запостить уже нельзя.
                                              +2
                                              Первая задача решается без кода. Достаточно найти суммы арифметических прогрессий A = 3 + 6 +… + 999 (числа, делящиеся на 3), B = 5 + 10 +… + 995 (числа, делящиеся на 5), C = 15 + 30 +… + 990 (числа, делящиеся на 15) и вычислить выражение A+B-C. :)

                                              А во второй можно найти несколько интересных рекуррентных соотношений. Сначала для удобства допишем к последовательности Фибоначчи слева единицу: тогда четные члены будут иметь номера, делящиеся на 3. Обозначим последовательность Фибоначчи за a[n], а за b[n] подпоследовательность четных членов: b[n] = a[3 * n]. Тогда нам нужно для некоторого N найти сумму S[N] = b[1] + b[2] + b[3] +… + b[N]. Можно заметить и доказать соотношение b[n+2] = b[n] + 4 * b[n+1]. На этом, в принципе, можно остановиться — просто просуммировать b[n] в цикле. Но также можно заметить, что S[n] = (b[n] + b[n+1] — 2) / 4, и тогда можно вычислять последовательность b[n], ничего не суммируя по ходу. Короче, решение на языке калькулятора bc:

                                              a = 0
                                              b = 2

                                              while (b < 4000000)
                                              {
                                              c = a + 4 * b
                                              a = b
                                              b = c
                                              }

                                              print (a + b — 2) / 4
                                              quit

                                                0
                                                Ну и я тогда тоже приведу решение — в данном случае брут первой задачи. Вместо того чтобы вычитать то, что кратно 15, я воспользовался хеш-массивом в PHP, используя числа в качестве ключа и единицу в качестве значения. Кажется, никто не повторил этот трюк.

                                                <?php
                                                	$arr = array();
                                                	$result = 0;
                                                
                                                	for ($i = 3; $i < 1000; $i += 3) $arr[$i] = 1;
                                                	for ($i = 5; $i < 1000; $i += 5) $arr[$i] = 1;
                                                	foreach ($arr as $a => $b) $result += $a;
                                                
                                                	echo $result;
                                                ?>
                                                
                                                  0
                                                  Первая задача решается за константное O(1) время, а не линейное, как у вас.

                                                  <? php= 3*int(999/3)*(1+int(999/3))/2 + 5*int(999/5)*(1+int(999/5))/2 — 15*int(999/15)*(1+int(999/15))/2) ?>
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                              0
                                              Еду в отпуск, хотелось бы все задачи в виде одного документа иметь. Есть где такая подборка?
                                                0
                                                Жаль, но я наверное немного опоздал ..)
                                                projecteuler.net/index.php? section=view_all
                                                  0
                                                  спасибо, хоть я уже и нашел это :)
                                                0
                                                Вот такая вот неприятность случилась ((

                                                Project Euler is offline.

                                                Due to the discovery of a serious security issue a decision was made on Sunday 15 June 2014 to take down the website. The full extent of the issue is still being investigated but in an attempt to be as honest as possible to our members we must make you aware that we have reason to suspect that all or parts of the database may have compromised. Passwords at Project Euler are strongly encrypted using a one-way hash, but if you use the same password at other websites then it is strongly advised that you change it. We are extremely sorry for this inconvenience. At this time we can provide no more information and there is no indication when Project Euler will return.
                                                  0

                                                  Уже всё хорошо

                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                Самое читаемое