数三角形问题的程序算法和数据结构

题目:数出类似下面的图中共有多少个三角形。(标号是后面我的算法用的) 手动算法:以每个最小块为单位,数出由1个、2个、……、n个单位组成的三角形数量。

提出的程序算法和数据结构:(简单的枚举,高中竞赛渣不会啥高级算法了)

  1. 输入点的数量,以及有几个点在一条线上(由一长条线连起来)的信息。例如:共11个点,0-1-7、0-2-8、……都在一条线上。
  2. 枚举所有不同的三个点的集合,判断是否为三角形:
    1. 若三点在同一条线上(即包含在上述输入的一个集合里),三角形三点不能成一条直线,否决。
    2. 若其中两个点不在任何一个相同集合里,即两点之间没有线连接,否决。
    3. 否则(两两在同一集合,三个不在同一集合),数一个三角形。

Python 渣代码实现:

#!/usr/bin/python3

######## INPUT ########
Points = 11
Sets = [
    {0,1,7}, {0,2,5,8}, {0,3,6,9}, {0,4,10},
    {1,2,3,4}, {4,5,6,7}, {7,8,9,10}
]
######## INPUT ########

test2 = lambda x, y: sum([(x in t and y in t) for t in Sets]) > 0
test3 = lambda x, y, z: sum([(x in t and y in t and z in t) for t in Sets]) > 0
result = [{a, b, c} for a in range(Points) for b in range(a+1,Points) for c in range(b+1,Points) if test2(a,b) and test2(b,c) and test2(a,c) and not test3(a,b,c)]
count = len(result)
print(count)

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注