Euler понимание № 163 проекта
Я провел довольно долгое время, ища решение этой проблемы. Я потянул тонны штриховавших треугольников, считал треугольники в простых случаях и искал своего рода шаблон. К сожалению, я врезался в стену. Я вполне уверен, мои навыки программирования/математики не встретили prereq для этой проблемы.
Таким образом, я нашел решение онлайн для получения доступа к форумам. Я не понял большинство методов вообще, и некоторые просто казались слишком сложными.
Кто-либо может дать мне понимание этой проблемы? Один из методов, найденных здесь: http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (проблема C) позволил, чтобы использовалась единственная функция.
Как они предлагали то решение? На данном этапе я был бы действительно точно так же, как для понимания некоторых понятий позади этой интересной проблемы. Я знаю, что поиск решения не был частью Euler духа, но я абсолютно уверен, что не решил бы эту проблему во всяком случае.
2 ответа
По сути, это проблема в перечислительной комбинаторике, которая представляет собой искусство подсчета комбинаций вещей. Это прекрасный предмет, но, вероятно, нужно немного разогреться, прежде чем вы сможете оценить ниндзя-трюки в приведенной вами ссылке.
С другой стороны, комментарии в теме решений этой задачи показывают, что многие решили задачу с помощью перебора. Один из самых распространенных трюков заключается в том, чтобы взять все возможные комбинации трех линий на диаграмме и посмотреть, дают ли они треугольник, который находится внутри самого большого треугольника.
Вы можете значительно сократить пространство поиска, заметив, что линии идут в одном из шести направлений. Поскольку комбинация прямых, включающая две параллельные прямые, не даст треугольника, можно перебирать тройки прямых так, чтобы каждая прямая в тройке имела разное направление.
Даны три прямые, вычислите точки их пересечения. У вас будет три возможности 1) линии совпадают - все они пересекаются в общей точке 2) две прямые пересекаются в точке вне треугольника 3) все три точки пересечения различны, и все они лежат внутри внешнего треугольника
Просто подсчитайте комбинации, удовлетворяющие условию (3), и все готово. Количество комбинаций линий, которые нужно проверить, равно O(n3), что не является запретительным.
EDIT1: перечитав ваш вопрос, у меня сложилось впечатление, что вы больше хотите получить объяснение комбинаторного решения/формулы, чем набросок подхода грубой силы. Если это так, скажите об этом, и я удалю этот ответ. Но я бы также сказал, что вопрос в таком случае не подходит для этого сайта.
EDIT2: Смотрите также комбинаторное решение Билла Дейли и других. С математической точки зрения оно немного мягче, чем другое.
Я не решил эту проблему для проекта euler и отказываюсь от вопроса и решения, которое вы предоставили. В случае единственной функции представленная методология заключалась в конечном итоге в простом поиске паттернов. Решатель разбил представленный вопрос на три части в зависимости от типов треугольников, которые присутствовали на пересечениях. Это довольно стандартный подход к такого рода проблемам: разбейте более крупный шаблон на более мелкие, чтобы облегчить решение. Я могу только предположить, что функции, используемые для выражения различных форм треугольников, были созданы либо очень острым умом нахождения закономерностей, либо некоторой теорией / геометрией чисел. Это также выходит за рамки данного объяснения и моих знаний. Эта проблема не имеет ничего общего с программированием. Это в основном математика. Если вы прочитали понравившийся вам сайт, вы увидите логику, которая использовалась для ответа на вопросы.