怎么算图中有多少个三角形_贪心算法经典例题

怎么算图中有多少个三角形_贪心算法经典例题题目:请说出下面图形中包含多少个三角形?请用一个程序完成计算。C++版本解题思路:(1)给每个交点做标记,如下:(2)总共有36条线段,如果三条线段两两之间存在交点,但一条线上(已经包含了三条

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

题目:请说出下面图形中包含多少个三角形?请用一个程序完成计算。

怎么算图中有多少个三角形_贪心算法经典例题

C++版本

 1 #include<iostream>  2  3 using namespace std;  4  5 const char NO_POINT = '0';  6  7 //任意的一条线  8 const char *map[] = { "ad","ab","db","ae","aj","ah","ej","eh","jh","af","ak","ai","fk","fi","ki","ag","ac","gc",  9 "de","df","dg","ef","eg","fg","bj","bk","bg","jk","jg","kg","bh","bi","bc","hi","hc","ic" }; 10 //共线的点 11 const char *line[] = { "adb","aejh","afki","agc","defg","bjkg","bhic" }; 12 13 //点是否在线上 14 int contain( const char *str, char a) { 15 int i = 0; 16 while (str[i] != '\0') { //注意字符使用单引号,字符串是双引号 17 if (str[i] == a) 18 return 1; 19 i++; 20  } 21 return 0; 22 } 23 24 //三个点是否在一条线上函数 25 int isInALine(const char *str[], char a, char b, char c) { 26 int i ; 27 for (i = 0; i < 7; i++) { 28 if (contain(str[i], a) && contain(str[i], b) && contain(str[i], c)) { 29 return 1; 30  } 31  } 32 return 0; 33 } 34 35 //两条线的交点函数 36 char getCrossPoint(const char *str1, const char *str2) { 37 if (*str1 == *str2) 38 return *str1; 39 if (*str1 == *(str2 + 1)) 40 return *str1; 41 if (*(str1 + 1) == *str2) 42 return *(str1 + 1); 43 if (*(str1 + 1) == *(str2 + 1)) 44 return *(str1 + 1); 45 return NO_POINT; 46 } 47 48 //三条线两两必须有交点,并且三条线不能共线才能构成三角形。 49 int isTriangle(const char *str1, const char *str2, const char *str3) { 50 char Point1, Point2, Point3; 51 Point1 = getCrossPoint(str1, str2); 52 if (Point1 == NO_POINT) 53 return 0; 54 Point2 = getCrossPoint(str1, str3); 55 if (Point2 == NO_POINT) 56 return 0; 57 Point3 = getCrossPoint(str2, str3); 58 if (Point3 == NO_POINT) 59 return 0; 60 if (isInALine(line, Point1, Point2, Point3)) 61 return 0; 62 return 1; 63 } 64 65 int getTriangelCount( const char *str[]) { 66 int i, j, k,count=0; 67 for (i = 0; i < 36; i++) { 68 for (j = i+1; j < 36; j++) { 69 for (k = j+1; k < 36; k++) { 70 if (isTriangle(str[i], str[j], str[k])) 71 count++; 72  } 73  } 74  } 75 return count; 76 } 77 78 int main(int argc, char *argv[]) { 79 cout << getTriangelCount(map); 80  getchar(); 81 return 0; 82 }

 解题思路:

(1)给每个交点做标记,如下:

怎么算图中有多少个三角形_贪心算法经典例题

(2)总共有36条线段,如果三条线段两两之间存在交点,但一条线上(已经包含了三条线交于同一点),则可以构成三角形。如下图所示,最左边的构成三角形,右边两个不构成三角形:
怎么算图中有多少个三角形_贪心算法经典例题

(3)故需要有如下一些子函数:求两条线的交点,三个点是否共线等。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166604.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 爆炸人游戏各关的道具_盗版星露谷可以联机吗

    爆炸人游戏各关的道具_盗版星露谷可以联机吗1.算法流程2.update函数运行流程updateDelta:Updatedeltaifweneedittocheckrelinearizationlater update.pushBackFactors:Addanynewfactors 为每一个新的factor产生一个索引,把新factor装入nonlinearFactors中 把需要移除的factor从nonlinearFactors和linearFactors中同时移除,把从nonlinea.

    2022年10月26日
  • 傅里叶级数与傅里叶变换公式推导「建议收藏」

    傅里叶级数与傅里叶变换公式推导「建议收藏」首先,傅里叶分析是指把一个周期或非周期函数展开成一个个三角函数的叠加,如果是对其还没有基本概念的,可以看看傅里叶分析之掐死教程,这篇文章不依赖数学公式却又十分透彻地讲述了傅里叶分析的基本概念,十分值得一读。但如果先深入探讨其中的数学由来,接下来会讲述详细的数学推导。傅里叶级数三角函数系的正交性三角函数系:{1,sinx,cosx,sin2x,cos2x,…,sinnx,cosnx,…},它由无数个sinnx和cosnx组成,其中n=0,1,2,…。正交性:∫−ππsin⁡nxcos⁡mxdx=0,

  • Mybatis拦截器

    Mybatis拦截器一Mybatis拦截器介绍    Mybatis拦截器设计的初衷就是为了供用户在某些时候可以实现自己的逻辑而不必去动Mybatis固有的逻辑。通过Mybatis拦截器我们可以拦截某些方法的调用,我们可以选择在这些被拦截的方法执行前后加上某些逻辑,也可以在执行这些被拦截的方法时执行自己的逻辑而不再执行被拦截的方法。所以Mybatis拦截器的使用范围是…

  • linux下查看memcache是否正常

    linux下查看memcache是否正常

  • 实战 | SpringBoot微信点餐系统(附源码)[通俗易懂]

    实战 | SpringBoot微信点餐系统(附源码)[通俗易懂]点击上方“java进阶架构师”,选择右上角“置顶公众号”20大进阶架构专题每日送达架构前后端分离:补充:setting.xml文件的作用:settings.xml是ma…

  • 100+个Java项目视频教程+源码+笔记,项目经验不用愁了!

    100+个Java项目视频教程+源码+笔记,项目经验不用愁了!有很多朋友问我,说有没有项目可以分享,最近整理了一些项目,现在分享给大家,希望能帮助大家积累一些项目方面的经验。开源项目分享1、微信小程序开发【前端+后端(Java)】附完整源码地址:微信小程序开发【前端+后端(Java)】附完整源码2、springboot+vue.js搭建图书管理系统开源项目地址:springboot+vue.js搭建图书管理系统开源项目3、仿百度网盘的一款轻量级微服务架构网盘系统地址:仿百度网盘的一款轻量级微服务架构网盘系统4、仿京东电商项目终于开源了~项目经验不愁喽!

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号