这张图中能数出多少个三角形?

只能一个个数吗? 有没有方便的计算方法?

推荐  (3) | 19人关注关注
11个答案
89 1

程序放在最后面了,算法和@粉紫色郁金香 一样,记录每条线段上的顶点,然后58个顶点C(58,3)挨个查是不是三角形。用@非乌龟 提出的直接套图论算法也很合适,但是这里面因为共线的点比较多,按照无向图来存的话稍微麻烦一点,而且因为数据量比较小,速度优势也不会很明显。在此严正声明:Mathematica大法好

-----------------------------------------------------------------------------------------

我数到了184个,如果需要额外的数据请联系我

111、184放大了是这个样子的

数数的动图

点击访问视频

--------------------------------------------------------------------------------

定义图中各个顶点的坐标和各条线段上的顶点,是用另一段Mathematica代码+手工生成的。

处理出来

这是用来找三角形的代码

这是用来输出上面那个大图的代码

Mathematica源程序放在了https://infotomb.com/hs4et.txt 可以拿来玩,扩展名要改成.nb

32 0

哈哈哈,这个东西某次面试(程序员)的时候被问到如何计算。

先给出当时的回答,让我去写写段程序算下结果等会来贴结果。

更新: 结果算完了,184个! 程序清单见最后。

我给出的简单明了的暴力求解方案,要点如下:

  1. 用某种数据结构表示出所有的点和所有的线(即点之间的共线关系)。
  2. 遍历所有的三点组合,对每一个组合,用上一条中的信息判定3个点是否两两之间都有连线,并排除三点共线的情况,通过的话三角形数量+1。

因为2里面得出来的三角形互相之间顶点都不同,所以不会出现重复的问题。又因为所有可能的三角形顶点都在这个范围内,所以也不会有遗漏。

具体实现:

  1. 所有点编号。
  2. 生成所有可能组合,递归或者循环都可。
  3. 线的记录方式。每一条线都用其上所有点的数组来标记,比如 [2,5,19],表示一条通过这3点的线。
  4. 两个点之间是否有连线的判定就是看这两个点是否在上一步的某一个数组中同时出现。另外这一步要排除三点共线的情况,只要判定三点是否都在同一个数组里就行。

--------以下为计算程序,为了保持格式用了全角空格来标记缩进。不能直接复制运行。----

<?php
//总共多少个点
$dots = 58;
//记录所有线的数组。我给点编号的顺序很随意,
//记录线的顺序也很随意(记录一条涂黑一条..)
//这个表示形式并不唯一。
$lines = array(
  [1,2,5,8,11,14,19,20,21,22,23,24],
  [1,4,7,10,13,16,33,32,31,30],
  [1,3,6,9,12,15,34,44,45,55,26],
  [24,25,26,27,28,29,30],
  [2,3,4],
  [5,6,7],
  [8,9,10],
  [11,12,13],
  [14,15,16],
  [8,12,18,16],
  [10,12,17,14],
  [11,17,15],
  [13,18,15],
  [15,19],
  [15,35,36,37,33],
  [23,58,25],
  [22,57,26],
  [24,58,57,56,43,44,38,36,16],
  [21,56,55,53,52,28],
  [19,34,38,39,40,32],
  [21,42,41,34,35,16],
  [16,37,39,46,54,53,26],
  [33,40,47,51,52,27],
  [32,48,50,28],
  [31,49,29],
  [20,42,43,45,54,51,50,29],
  [20,41,44,46,47,48,49,30],
);

/**** 开始! ****/

//这数组用来记录所有三角形(顶点三元组)
$triangles = [];

//直接三重循环遍历所有顶点三元组,约定$i<$j<$k。
for($i=1; $i<=$dots; $i++){
  for($j=$i+1; $j<=$dots; $j++){
    for($k=$j+1; $k<=$dots; $k++){
      //判定
      if(is_triangle($i, $j, $k)){
        $triangles[] = [$i,$j,$k];
      }
    }
  }
}

//这里只输出数量,如果需要更详细的信息可以查看数组内容。
echo count($triangles);

/**** 结束, 以下是辅助函数 ****/

/**
* 给定顶点三元组是否是三角形?
*
* @return boolean
*/
function is_triangle($i, $j, $k){
  //排除三点共线先。
  if(in_one_line($i,$j,$k)){
    return false;
  }
  //两两之间都有连线?
  if( in_one_line($i,$j) and in_one_line($j,$k) and in_one_line($i,$k)){
    return true;
  }

  return false;
}

/**
* 判定给定的点是否全部在同一条直线上。
* 接受任意数量参数。
*
* @return boolean
*/
function in_one_line(...$dots){
  global $lines;
  foreach($lines as $line){
    $ok = true;
    foreach($dots as $dot){
      $ok = $ok && in_array($dot, $line);
    }
    if($ok){
      return true;
    }
  }
  return false;
}


31 1

非乌龟代数拓扑硕士,C#程序员

2015-07-21 16:37

Stackoverflow上有一个问答是关于这种问题的算法的。

这个问题似乎已经作为比较成熟的问题被大家讨论过了:

现在在上班,等我方便的时候具体研究一下。

1 0

千度建筑工程技术专业,软件爱好者

2015-07-24 00:23
支持者: 这座城有多空

这是一道拓扑题啊。。。

1 0

撒隆巴斯学完经济学法律,学完法律抓人去。。。

2015-07-24 00:49
支持者: 海流

看明白了,大意就是统计所有点,然后取其中三点的组合数量,再排除三点间没有全部连线的情况。

1 0

Noctambulator数学与应用数学专业理学学士

2015-07-24 21:25
支持者: 怀璧

粗略想出来的算法:

假设有n个点 先将每个点编号为一个数字i 然后每条线记为一个包含几个数字的集合Aj 共m个 两点在同一集合内就代表他们共线 这些全部作为输入数据

再添加个共线判断函数f(a,b),输入两数字a,b 如果它们在同一集合内输出就为1 否则输出为0 在读取了集合Am后这个函数可以很快求出来

然后从1开始 研究所有包含1的集合Aj 遍历所有两两不同的Aj中各自的元素 有共线的元素就视为找到了一个三角形 可以记录下这三点

找完后从所有Aj集合中去除1这个元素 代表1为顶点的三角形都找完了 以后不再考虑1

之后继续判断2 判断3…… 这样一直判断到n-2号点即可

0 0

这个……可以用排列组合来解么……

0 0

简单地说,就是按一个方向遍历所有的点。

选一个凸角顶点开始,顺时针出发找第二点,再从第二点顺时针出发找第三点,若第三点与第一点有连线则三角形数+1;找下一个第三点,判断,直到没有满足要求的第三点;找下一个第二点,同样遍历直到没有满足要求的第二点;抹去第一点及以之为端点的线段。

重复上述步骤。


0 3

营销账号真无聊,都来果壳营销了。

2 13

LunaLovegood跳线达人 跑题专家 博爱界人士 泛科技主题旁观者

2015-07-23 00:36
支持者: 七为 Vonaway

和图中的猫毛一样多

查看更多

添加回答

登录 后回答问题,你也可以用以下帐号直接登录

相关问答

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2018] 6282-492号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区