判定给定边长可否构成三角形的一个定理

本定理来自一道算法竞赛题:

给定任意多条边,每条边都是不超过1,000,000,000的正整数。请给出一个算法,判断其中是否存在3条边可以构成三角形。

应用该定理可以有效地解决此问题。

定理

给定n个边长,如果其中最大的边长与最小的边长的比值小于第n个斐波那契数,那么其中必存在3个边长可以构成三角形。

应用

由题中条件可知,最大的边长和最短的边长的比值不超过\(1,000,000,000 < F_{45}\)。所以,只要边的个数达到45,根据上述定理,就必然存在3条边可以构成三角形。如果边的个数少于45个,也很好办,穷举解决即可(\({45 \choose 3} = 14190\),穷举量很小)。

继续阅读 →