解题:网上争论比较多一道题,大家想想用程序怎么解?

三角形 争论 程序 一道 三条 三行 线段 伯乐

10-25 22:00 程序员的那些事 (iProgrammer) 科技

解题:网上争论比较多一道题,大家想想用程序怎么解?_程序员的那些事_读一读网站 解题:网上争论比较多一道题,大家想想用程序怎么解?,读一读网站提供程序员的那些事热门推荐内容等信息。

(点击上方公众号,可快速关注)


来源:伯乐在线 - kingecg

网址:http://group.jobbole.com/25030



一共有多少三角形?


这个是目前网上争论比较多一个题目。大家想下用程序怎么解?


我自己的理解:


本题目可以看作一个寻路问题:


1)先从最外层的任一定点出发,沿其相连的边如果经过2个转折可以回到出发点,则认为


是一个三角形,记录下路径。


2)枚举完step 1中出发点相关的三角形后,从图中删除该出发点和相连的边。然后对剩下的图重复step 1.


直到最后找不出三角形为止。


需要建模的数据:


点:序号,坐标


边:起始点,斜率


下面是伯乐在线部分网友的回复:


苹果没有熟


也可以建模顶点及其共线点,3层循环解决


zarahwest


24个


知音难寻


146个三角形。一共十一个点,没个三角形有三个点。C11 3=165,在同一天直线上的三个点不能组成三角形,共7条边(3个点的三条,4个点的4条),3*C3 3+4*C4 3=19。165-19=146个。


怒打装13犯


从所有线段中任意取出三条,将这三条线段的端点(共6个)去除重复点后如果只得到3个点且这3个点不共线,那么就能构成一个三角形。


空城


总共11个点,每两个点之间有联通的设置权值为1(不分长短都设置为1),建立


11行*11列的矩阵,从第一行第一列的点出发,遍历第一行其余10个点,若有遍历到的权值为1,则根据遍历到的点去找相应行的点,如遍历到第一行第二列的权值为1,则再去查找相应的第二行,依次遍历第二行,若有遍历到第二行某个列的权值为1,则再根据遍历到的点去找相应行的点,如遍历到第二行第三列的权值为1,则再去查找相应的第三行,然后到目前为止总共找了两个列点,再看第三行到发起列(即第一列)的权值是否为1,若为1,则构成三角形,后续的依次类推,即可。。。。。。


Loranzo_湯鎧賢_汤铠贤


int[] LINE_01 = {A, B, H};

int[] LINE_02 = {A, C, F, I};

int[] LINE_03 = {A, D, G, J};

int[] LINE_04 = {A, E, K};

int[] LINE_05 = {B, C, D, E};

int[] LINE_06 = {H, F, G, E};

int[] LINE_07 = {H, I, J, K};


点赋值,设线段。

任意三个数组并集,长度等于三个数组总长度-3

则三角形数量加1。

三层循环。


不过好像效率不高。


关注「程序员的那些事」

看更多精选话题

↓↓

更多阅读

读一读网站 www.duyidu.com 备案号: 闽ICP备12001821号-1    免责声明  提交公众号   商务合作QQ: