从简单的三角形开始 · 算法程序设计

<table border="1" style="font-family:Simsun; border-collapse:collapse; padding:1pt 5.4pt"><tbody><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">问题主题：三角形</td></tr><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">问题描述： 有n根棍子，棍子i的长度为ai，想要从中选出三根棍子组成周长尽可能长的三角形。请输出最大的周长，若无法组成三角形则输出0。</td></tr><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">样例：输入n=5a={2,3,4,5,10}输出12(选择3,4,5时) 输入n=4a={4,5,10,20}输出 0(无法构成三角形)</td></tr></tbody></table> ### 【解法一】 ### 解题分析：我的思路(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++** <table border="1" style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">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, 不能构成三角形");}</td></tr></tbody></table> **Java** <table border="1" style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)"><pre name="code" class="cpp">#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; }</pre> </td></tr></tbody></table> **** ### 算法复杂度：时间复杂度：O(n3)