问题描述
最多可以组成几个直角三角形,一个边只能用一次。
输入描述:
第一行输入一个正整数T(1<=T<=100),表示有T组测试数据.
对于每组测试数据,接下来有T行,每行第一个正整数N,表示线段个数(3<=N<=20),接着是N个正整数,表示每条线段长度,(0<a[i]<100)。
输出描述:
对于每组测试数据输出一行,每行包括一个整数,表示最多能组合的直角三角形个数
思路
将整数列表进行排序,要组成直角三角形,则第三条边大于前两条边,从大到小遍历列表,将其作为第三条边,再从小到大确定第二条边,若找到第三条边与其成功配对,则这三个元素从列表中删除,表示已经用过。再对剩余元素进行相同的操作。
代码实现
def is_vertical(i, j, k):
if i ** 2 == j ** 2 + k ** 2:
return True
return False
def rec(list_1):
if len(list_1) < 3:
return 0
if len(list_1) == 3:
if is_vertical(list_1[2], list_1[1], list_1[0]):
return 1
return 0
count = 0
for i in range(len(list_1) - 1, 1, -1):
flag = False
for j in range(0, i):
for k in range(j + 1, i):
if is_vertical(list_1[i], list_1[j], list_1[k]):
count += 1
flag = True
new_list = list_1[:]
new_list.pop(i)
new_list.pop(k)
new_list.pop(j)
break
if flag:
break
if flag:
break
count += rec(new_list)
return count
rows = int(input().strip())
nums = []
for i in range(rows):
a = list(map(int, input().strip().split(' ')))[1:]
a.sort()
nums.append(a)
for num_list in nums:
print(rec(num_list))
输入
2
7 6 8 10 15 17 24 26
14 8 10 7 24 25 8 15 17 9 12 15 9 40 41
输出
2 (8,15,17;10,24,26)
4 (7 24 25;8 15 17;9 12 15;9 40 41)