欧拉计划 #163 理解
我花了很长时间寻找这个问题的解决方案。我画了大量的交叉阴影三角形，计算了简单情况下的三角形，并寻找某种模式。不幸的是，我碰壁了。我很确定我的编程/数学技能不符合这个问题的先决条件。
所以我在网上找到了一个解决方案，以便能够访问论坛。大多数方法我根本不明白，有些方法看起来太复杂了。
谁能让我理解这个问题？其中一种方法，可以在这里找到： http://www.math .uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles（问题C） 允许使用单个函数。
他们是如何想出这个解决方案的？此时，我真的很想了解这个有趣问题背后的一些概念。我知道查找解决方案不是欧拉精神的一部分，但我相当确定无论如何我都无法解决这个问题。
I spent quite a long time searching for a solution to this problem. I drew tons of cross-hatched triangles, counted the triangles in simple cases, and searched for some sort of pattern. Unfortunately, I hit the wall. I'm pretty sure my programming/math skills did not meet the prereq for this problem.
So I found a solution online in order to gain access to the forums. I didn't understand most of the methods at all, and some just seemed too complicated.
Can anyone give me an understanding of this problem? One of the methods, found here: http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (Problem C)
allowed for a single function to be used.
How did they come up with that solution? At this point, I'd really just like to understand some of the concepts behind this interesting problem. I know looking up the solution was not part of the Euler spirit, but I'm fairly sure I would not have solved this problem anyhow.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这本质上是枚举组合学中的一个问题，枚举组合学是计算事物组合的艺术。这是一个美丽的主题，但可能需要一些热身才能欣赏您提供的参考资料中的忍者技巧。
另一方面，该问题的解决方案线程中的评论表明许多人已经使用暴力方法解决了该问题。最常见的技巧之一是采用图中三条线的所有可能组合，并查看它们是否产生位于最大三角形内的三角形。
您可以通过注意线位于六个方向之一来大大减少搜索空间。由于包含两条平行线的线组合不会产生三角形，因此您可以迭代线三元组，以便三元组中的每条线都有不同的方向。
给定三条线，计算它们的交点。你将有三种可能
1）这些线是重合的——它们都相交于一个公共点
2）两条直线相交于三角形外的一点
3）所有三个交点都是不同的，并且它们都位于外三角形内
只需计算满足条件（3）的组合即可。您必须测试的行组合数量为 O(n3)，这并不令人望而却步。
编辑1：重读你的问题，我的印象是你可能更感兴趣的是组合数学解决方案/公式的解释，而不是暴力方法的概述。如果是这样的话，请说出来，我会删除这个答案。但我还要说，这种情况下的问题不适合这个网站。
EDIT2：另请参阅Bill Daly 等人的组合解决方案。从数学上来说，它比另一种更温和一些。
This is essentially a problem in enumerative combinatorics, which is the art of counting combinations of things. It's a beautiful subject, but probably takes some warming up to before you can appreciate the ninja tricks in the reference you gave.
On the other hand, the comments in the solutions thread for the problem indicate that many have solved the problem using a brute force approach. One of the most common tricks involves taking all possible combinations of three lines in the diagram, and seeing whether they yield a triangle that is inside the largest triangle.
You can cut down the search space considerably by noting that the lines are in one of six directions. Since a combination of lines that includes two lines that are parallel will not yield a triangle, you can iterate over line triples so that each line in the triple has a different direction.
Given three lines, calculate their intersection points. You will have three possibilities
1) the lines are coincident - they all intersect in a common point
2) two of the lines intersect at a point outside the triangle
3) all three points of intersection are distinct, and they all lie within the outer triangle
Just count the combos satisfying condition (3) and you are done. The number of line combos you have to test is O(n3), which is not prohibitive.
EDIT1: rereading your question, I get the impression you might be more interested in getting an explanation of the combinatorics solution/formula than an outline of a brute force approach. If that's the case, say so and I'll delete this answer. But I'd also say that the question in that case would not be suitable for this site.
EDIT2: See also a combinatorics solution by Bill Daly and others. It is mathematically a little gentler than the other one.
我还没有解决 project euler 的这个问题，并且正在离开您提供的问题和解决方案。在单一功能的情况下，所提出的方法最终是简单的模式发现。求解器根据交叉点中存在的三角形类型将所提出的问题分为三个部分。这是解决此类问题的相当标准的方法，将较大的模式分解为较小的模式以使解决起来更容易。我只能假设用于表达各种形式的三角形的函数是通过非常敏锐的模式发现思维或某些数论/几何生成的。这也超出了这个解释和我的知识范围。这个问题与编程无关。这基本上完全是数学。如果您通读您喜欢的网站，您可以看到解决问题所经历的逻辑。
I have not solved this problem for project euler and am going off of the question and the solution you provided. In the case of the single function, the methodology presented was ultimately simple pattern finding. The solver broke the presented question into three parts, based on the types of triangles that were present from the intersections. It's a fairly standard aproach to this kind of problem, break the larger pattern down into smaller ones to make solving easier. The functions used to express the various forms of triangles I can only assume were generated with either a very acute pattern finding mind or some number theory / geometry. It is also beyond the scope of this explanation and my knowledge. This problem has nothing to do with programming. It's basically entirely mathematics. If you read through the site you liked you can see the logic that is gone through to reach the questions.