Идея проекта Эйлера № 163

Я потратил довольно много времени на поиск решения этой проблемы. Я нарисовал тонны треугольных треугольников, подсчитал треугольники в простых случаях и искал какой-то узор. К сожалению, я ударился о стену. Я уверен, что мои навыки программирования/математики не соответствовали требованиям этой проблемы.

Итак, я нашел решение онлайн, чтобы получить доступ к форумам. Я не понимал большинство методов вообще, и некоторые просто казались слишком сложными.

Может ли кто-нибудь дать мне понимание этой проблемы? Один из методов, найденный здесь: http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (проблема C) допускается использование одной функции.

Как они придумали это решение? На данный момент я бы просто хотел понять некоторые концепции этой интересной проблемы. Я знаю, что поиск решения не был частью духа Эйлера, но я уверен, что я бы так и не решил эту проблему.

Ответ 1

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

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

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

Учитывая три линии, вычислите их точки пересечения. У вас будет три возможности 1) линии совпадают - все они пересекаются в общей точке 2) две линии пересекаются в точке вне треугольника 3) все три точки пересечения различны, и все они лежат внутри внешнего треугольника

Просто подсчитайте комбо, удовлетворяющее условию (3), и все готово. Количество строк, которые вы должны проверить, - O (n ³), что не является запретительным.

EDIT1: перечитывая свой вопрос, у меня создается впечатление, что вам может быть больше интересно получить объяснение решения/формулы комбинаторики, чем набросок подхода грубой силы. Если это так, скажем так, и я удалю этот ответ. Но я бы также сказал, что вопрос в этом случае не подходит для этого сайта.

EDIT2: См. также комбинаторное решение Билла Дейли и других. Это математически немного мягче, чем другое.

Ответ 2

Я не решил эту проблему для project euler, и я уйду от вопроса и вашего решения. В случае единственной функции представленная методология была в конечном счете простой находкой. Решатель разбил представленный вопрос на три части, основываясь на типах треугольников, которые присутствовали на пересечениях. Это довольно стандартный подход к этой проблеме, разбивает более крупный рисунок на более мелкие, чтобы облегчить решение. Функции, используемые для выражения различных форм треугольников, которые я могу только предположить, были получены либо с очень острым умом, либо с разной теорией/геометрией чисел. Это также выходит за рамки этого объяснения и моих знаний. Эта проблема не имеет ничего общего с программированием. Это в основном полностью математика. Если вы читаете сайт, который вам понравился, вы можете увидеть логику, которая прошла, чтобы достичь вопросов.