从N个整数中判断是否有三个整数能组成三角形

解决这个问题，可以用斐波那契数列（Fibonacci sequence）

原因

• 斐波那契数列中的数是不可能组成三角形的。
• 而我们只要在这些数列里面加一个数就可以有一个三角形可以组成

有了这个原因我们就可以写一个非常快速就可以判断出结果的函数。

如果题目限制了N个整数的数据大小不能超过int型。那么我们算出斐波那契数列哪一项大于int的范围。

int 大于0的范围:0~2147483647

斐波那契数列第47项超过int

所以假设输入的n有46个，这时候还没有超过int ，所以小于46的都要判断。

当如果大于等于47个，由于第47个已经大于了int了，所以不可能取第47个，所以此时一定会有一个数，不是斐波那契数列中的数，此时就一定会有三个整数可以组成一个三角形。

以下给出代码

#include<iostream>
#include<algorithm>
using namespace std;

int a[1000];//存一堆整数

int main()
{
	//关闭cin同步，此时速度会比scanf()还快。而且输入方便 
	std::ios::sync_with_stdio(false);
	int n;cin>>n;

	int flag=0;

	for(int i=0;i<n;i++)
	     cin>>a[i];

	if(n>=47) 
	{ 
		flag=1;
		cout<<"YES";
	} 
	else
	{
		//这个排序是快排，排序后，前两项相加大于第三项一定可以组成一个三角形。
		sort(a,a+n);
		
		for(int i=0;i<n-2;i++)//前两项之和大于第三项的判断。
		{
			if(a[i]+a[i+1]>a[i+2])
			{
				cout<<"YES";
				flag=1;
				break;
			}
		}
	}
	
	if(flag==0)cout<<"NO";
	return 0;
}

原创文章，如有错误请指出，谢谢。