从简单的三角形开始

最后更新于:2022-04-01 20:19:33

问题主题:三角形

问题描述:

    有n根棍子,棍子i的长度为ai,想要从中选出三根棍子组成周长尽可能长的三角形。请输出最大的周长,若无法组成三角形则输出0

样例:

输入

n=5

a={2,3,4,5,10}

输出

12(选择3,4,5)

 

输入

n=4

a={4,5,10,20}

输出

    0(无法构成三角形)

### 【解法一】 ### 解题分析: 我的思路(java实现)是: 1.先将棍子根据长度从小到大排序; 2.第一根棍子取最长的a1 = a[n-1]; 3.第二根棍子取次长的a2=a[n-2]; 4.第三根棍子取a3=a[n-3],如果a1+a2>a3,则说明可以构成三角形,输出最大周长; 5.如不能构成三角形,则a3依次取a[n-4], a[n-5]... 6.如果a3=a[0]时依旧不行,则要循环a2, 使a2依次取a[n-3],a[n-4]... 7.如果再不行,要变换a1值,a1=a[n-2], a2=a[n-3]...  也就是使a1,a2,a3依次从高到低取值。 8.a1,a2,a3分别取到最小值a[2],a[1],a[0]还是不能构成三角形时,输出0,结束计算. 书上的分析(用C++实现)是: 直接用三重循环枚举所有的根子选择方案。再用以下公式判断能否构成三角形。 最长棍子的长度<其余两个棍子的长度之和 ### 程序实现: **C++**

public void contructTriangle(int a[]) {

// 对数组a进行排序

Arrays.sort(a);

int n = a.length;

int a1, a2, a3;

for (int i = n - 1; i >= 0; i--) {

a1 = a[i];

for (int j = i - 1; j >= 0; j--) {

a2 = a[j];

for (int k = j - 1; k >= 0; k--) {

a3 = a[k];

if (a2 + a3 > a1) {

System.out.println("最大" + (a1 + a2 + a3) + "三角形为" + a1 + "," + a2 + ","

+ a3 );

return ;

}

}

}

}

System.out.println("0,  不能构成三角形");

}

**Java**

#include <iostream>
#include <algorithm>
void constriangle(int* a, int n) {
int ans = 0;	//答案 
int len, ma, result;
//让i<j<k,这样棍子就不会被重复选了
for(int i=0; i<n; i++){
for(int j=i+1; j<n; j++) {
for(int k=j+1; k<n; k++) {
len = a[i] + a[j] + a[k];
ma = max(a[i], max(a[j], a[k]));
int rest = len-ma;
if(ma <rest) {
ans = max(ans, len);
}
}
}
}
cout<<ans<<endl;
}
 
int main() {
int a[5] = {2, 3, 4, 5, 10};
constriangle(a, 5);
return 0;
}

**** ### 算法复杂度:    时间复杂度:O(n3)
';