b557 - 直角三角形
題目描述
題目給定一組木棒的長度，要求計算可以組成幾種直角三角形。
解題思路
此題的解題思路是先將木棒長度排序，然後使用三重迴圈枚舉所有可能的組合，檢查是否滿足勾股定理。排序可以避免重複計算。具體來說，對於每三個木棒長度 a, b, c (其中 a < b < c)，如果 a*a + b*b == c*c，則表示可以組成一個直角三角形，計數器加一。
複雜度分析
- 時間複雜度: O(n^3) 因為使用了三重迴圈，其中 n 是木棒的數量。排序的時間複雜度為 O(n log n)，但相較於 O(n^3) 可以忽略。
- 空間複雜度: O(n) 主要用於儲存木棒長度的陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int a,i,c;
cin >> a;
while(cin >> a){
int t[a];
for(i=0;i<a;i++)
cin >> t[i];
c=0;
sort(t,t+a);
for(int i=0;i<a;i++){
for(int j=i+1;j<a;j++){
for(int k=j+1;k<a;k++){
if(t[i]*t[i]+t[j]*t[j]==t[k]*t[k])
c++;
}
}
}
cout << c << endl;
}
}