從簡單的三角形開始 · 算法程序設計

<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)