最多几个直角三角形python

问题描述

最多可以组成几个直角三角形，一个边只能用一次。

输入描述：
第一行输入一个正整数T（1<＝T<＝100），表示有T组测试数据.
对于每组测试数据，接下来有T行，每行第一个正整数N，表示线段个数（3<＝N<＝20），接着是N个正整数，表示每条线段长度，（0

输出描述：
对于每组测试数据输出一行，每行包括一个整数，表示最多能组合的直角三角形个数

思路

将整数列表进行排序，要组成直角三角形，则第三条边大于前两条边，从大到小遍历列表，将其作为第三条边，再从小到大确定第二条边，若找到第三条边与其成功配对，则这三个元素从列表中删除，表示已经用过。再对剩余元素进行相同的操作。

代码实现

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))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

输入
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）