Pau*_*aul 17 algorithm math geometry combinatorics
我花了很长时间寻找这个问题的解决方案.我绘制了大量的交叉阴影三角形,在简单的情况下计算三角形,并搜索某种模式.不幸的是,我碰到了墙.我很确定我的编程/数学技能不符合这个问题的先决条件.
所以我在网上找到了一个解决方案,以便访问论坛.我根本不了解大多数方法,有些看起来太复杂了.
谁能让我理解这个问题？其中一种方法可以在这里找到:http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles(问题C)允许使用单个函数.
他们是如何提出这个解决方案的？在这一点上,我真的只想了解这个有趣问题背后的一些概念.我知道查找解决方案不是欧拉精神的一部分,但我很确定无论如何我都不会解决这个问题.
这本质上是枚举组合学中的一个问题，枚举组合学是计算事物组合的艺术。这是一个美丽的主题，但可能需要一些热身才能欣赏您提供的参考资料中的忍者技巧。
另一方面，该问题的解决方案线程中的评论表明许多人已经使用暴力方法解决了该问题。最常见的技巧之一是采用图中三条线的所有可能组合，并查看它们是否产生位于最大三角形内的三角形。
您可以通过注意线位于六个方向之一来大大减少搜索空间。由于包含两条平行线的线组合不会产生三角形，因此您可以迭代线三元组，以便三元组中的每条线都有不同的方向。
给定三条线，计算它们的交点。您将有三种可能性：1) 两条线重合 - 它们都相交于一个公共点 2) 其中两条线相交于三角形之外的一点 3) 所有三个交点都是不同的，并且它们都位于外三角形内
只需数出满足条件 (3) 的组合即可。您必须测试的行组合数量为 O(n 3 )，这并不令人望而却步。
编辑1：重读你的问题，我的印象是你可能更感兴趣的是组合数学解决方案/公式的解释，而不是暴力方法的概述。如果是这样的话，请说出来，我会删除这个答案。但我还要说，这种情况下的问题不适合这个网站。
EDIT2：另请参阅Bill Daly 等人的组合解决方案。从数学上来说，它比另一种更温和一些。