algorithm - 欧拉计划#163 理解

Question

我花了很长时间寻找 this problem 的解决方案.我画了大量的交叉影线三角形，计算简单情况下的三角形，并寻找某种模式。不幸的是，我撞墙了。我很确定我的编程/数学技能不符合这个问题的先决条件。

所以我在网上找到了一个解决方案，以便能够访问论坛。我根本不理解大多数方法，有些方法似乎太复杂了。

任何人都可以让我了解这个问题吗？其中一种方法，可在此处找到:http://www.math.uni-bielefeld.de/~sillke/SEQUENCES/grid-triangles (问题 C)允许使用单个函数。

他们是如何想出这个解决方案的？在这一点上，我真的很想了解这个有趣问题背后的一些概念。我知道查找解决方案不是欧拉精神的一部分，但我很确定我无论如何都不会解决这个问题。

Answer 1

这本质上是枚举组合学中的一个问题，它是计算事物组合的艺术。这是一个美丽的主题，但可能需要一些热身才能欣赏您提供的引用资料中的忍者技巧。

另一方面，该问题的解决方案线程中的评论表明许多人已经使用蛮力方法解决了该问题。最常见的技巧之一是采用图中三条线的所有可能组合，并查看它们是否会产生一个位于最大三角形内的三角形。

通过注意线条位于六个方向之一，您可以大大减少搜索空间。由于包含两条平行线的线组合不会产生三角形，因此您可以迭代线三元组，使三元组中的每条线都有不同的方向。

给定三条线，计算它们的交点。你将拥有三种可能1) 这些线是重合的——它们都相交于一个公共(public)点2)两条线相交于三角形外的一点3) 三个交点都不同，都在外三角形内

只需计算满足条件 (3) 的组合即可。您必须测试的连线数为 O(n³)，这并不令人望而却步。

EDIT1:重读你的问题，我得到的印象是你可能对组合数学解决方案/公式的解释比暴力方法的概述更感兴趣。如果是这样，请这样说，我将删除此答案。但我还要说，那种情况下的问题不适合这个网站。

EDIT2:另见 a combinatorics solution by Bill Daly and others .它在数学上比另一个更温和。