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

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

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

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

Python 渣代码实现:

 

发表评论

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