Рубрика «оптимизация» - 42

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

Но иногда приятнее найти совсем нестандартное решение.
Читать полностью »