內容
你今天有 N 個長度不等的木棒，而你想知道這些木棒能組合出幾種直角三角形。
輸入
第一行有一數字 T ，代表有幾組測試資料 (1<=T<= 50)
每組測試資料包含兩行
第一行有一數字 N ，代表有幾根木棒 (1<=N<=100)
第二行有 N 個數字 a_i 以空白隔開，代表木棒的長度(1<=a_i<=100)
3
3
3 4 5
6
3 3 4 4 5 5
3
3 4 6
輸出
對於每筆測試資料輸出一行，每行包含一個數字 x 代表可以組成幾種直角三角形。
1
8
0
解題思路
每種相同組合的出現個數為該組合的各棍子個數相乘
假設: 5cm 兩個 4cm 兩個 3cm 三個
那組合出 △543 的次數就會是 2 * 2 * 3 = 12 次
計算過程中會頻繁的出現 1² ~ 100²，所以在程式開始時先打好 1~100 的次方表，之後直接取用。
採用基數排序的方式儲存，所以陣列中會有部分元素為 0，沒有棍子就不可能產生組合，用 continue 跳過避免無謂的計算。
完整程式碼
AC (6ms, 100KB)
#include <stdio.h>
#define MAX 100
int main()
{
int kase, n, tmp, p2List[110], count;
for (int i = 1; i <= MAX; i++)
p2List[i] = i * i;
scanf(" %d", &kase);
while (kase--)
{
count = 0;
int list[MAX + 1] = { 0 };
scanf(" %d", &n);
for (int i = 0; i < n; i++)
{
scanf(" %d", &tmp);
list[tmp]++;
}
for (int i = MAX; i > 2; i--)
{
if (!list[i]) continue;
for (int j = i - 1; j > 1; j--)
{
if (!list[j]) continue;
for (int k = j - 1; k; k--)
{
if (list[k] && p2List[i] == p2List[j] + p2List[k])
count += list[i] * list[j] * list[k];
}
}
}
printf("%d\n", count);
}
return 0;
}
|
