2
判定给定边长可否构成三角形的一个定理
source link: http://z-rui.github.io/post/2015/03/theorem/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
判定给定边长可否构成三角形的一个定理 | 睿
本定理来自一道算法竞赛题：
给定任意多条边，每条边都是不超过1,000,000,000的正整数。请给出一个算法，判断其中是否存在3条边可以构成三角形。
应用该定理可以有效地解决此问题。
给定n个边长，如果其中最大的边长与最小的边长的比值小于第n个斐波那契数，那么其中必存在3个边长可以构成三角形。
由题中条件可知，最大的边长和最短的边长的比值不超过1,000,000,000<F45。所以，只要边的个数达到45，根据上述定理，就必然存在3条边可以构成三角形。如果边的个数少于45个，也很好办，穷举解决即可（(453)=14190，穷举量很小）。
使用反证法，承认条件但否定结论，即假设给定的n个边长中的任意3个都不能构成三角形。将n条边以由小到大的顺序记作s1,s2,…,sn。我们将用归纳法证明sn/s1≥Fn，其中Fn表示第n个斐波那契数。
当k=1,2时，s1/s1=1≥F1,s2/s1≥1≥F2显然成立。假设sk/s1≥Fk,sk+1/s1≥Fk+1成立，那么因为sk,sk+1,sk+2三者不能构成三角形，所以最长的边不会小于另外两边之和。所以有sk+2/s1≥(sk+sk+1)/s1≥Fk+Fk+1=Fk+2。接下来使用归纳法即可。
我们所得到的结论和条件相矛盾：sn/s1≥Fn。这说明假设不成立，所以，定理是成立的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK