Парсер Хабра: Нестандартное решение одной задачи с ProjectEuler

среда, 30 октября 2013 г.

Нестандартное решение одной задачи с ProjectEuler

Задачки с Project Euler хороши тем, что позволяют развлечься и потренировать мозг на разных уровнях сложности для одной и той же задачи. Самый простенький подход — brute force. Первые два десятка задач на 99% решаются именно таким подходом. После отправки правильного ответа на задачу открывается ветка форума по ней. Любители из десятков стран соревнуются, кто процитирует решение поизощреннее. Более продвинутые используют встроенные возможности языков, на которых пишут решение, но суть одна и та же — перебор или явный с кучей вложенных циклов или неявный через вызов специальных функций. Особенно красиво это выглядит в языках Python или Ruby ( часто в одну-две строчки), помногословнее в Java и C++. Чем дальше, тем натужнее выглядят «силовые» решения, с использованием классов вроде BigInteger. С увеличением номера задачи грубую силу удается успешно применитьвсе реже и все сложнее. Появляется много задач на чистую математику, где нужно решить задачу на бумаге, а потом закодировать что-то совсем несложное. Иногда писать можно обойтись без написания кода вовсе, таких задач много — например, на применение комбинаторики.

Но иногда приятнее найти совсем нестандартное решение.

Пример. Задача 9. Найти пифагорейский триплет целых чисел a, b, c, такой что a + b + c = 1000. Напомню, пифагорейский триплет — это три целых положительны числа a < b < c, являющиеся сторонами прямоугольного треугольника, т.е. a^2 + b^2 = c^2. Самый известный школьный пример: 3, 4, 5.

Переборное решение очевидно. Она сильно сокращается по времени, если знать свойства таких триплетов, можно много итераций сэкономить. Но мы пойдем другим путем.

Будем использовать для решения оптимизационный инструмент Solver в комплекте MS Excel любой версии.

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

Кстати, Solver мне не удалось приткнуть для решения задачи о максимальной сумме пути — там совсем негладкая получается функция, случайная.

Несколько задачек, как я говорил, удалось решить без кода, аналитически. Один раз пришлось посчитать биномиальный коэффициент, для этого использовал инженерный калькулятор Windows. Одна задача в конце первой сотне решилась с помощью SQL — надо было только скопировать данные в табличу — регулярка в Notepad++, создающая DDL скрипт, после чего заполнение таблицы и запрос в одну строку.

Очень улекательно также посмотреть на статистику projectEuler. Максимально эффективные используемые языки и среды — не C++\Java, а французский матпакет PARI/GP, Mathematics, Python и Haskel. Используется множество экзотических (статистика на момент написания поста):

Больше всего народу, конечно, из Штатов — около 28 тысяч, из Китая и России примерно одинаковое число — около 3000. Но если ткнуть в страну и посмотреть топ 100 по задачам, видно, что китайцы эффективнее — там больше число людей, решивших, более 400, 350, 300, итд. задач. А в Индии наоборот — участников примерно в 2.5 раза больше, но супер-решателей поменьше, чем в РФ. По-моему если нормализовать это все на число населения, то начиная с какого-то статистически значимого числа участников на страну можно получить оценку эффективности высшего образования в ней.

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: