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

怎么算图中有多少个三角形_贪心算法经典例题题目:请说出下面图形中包含多少个三角形?请用一个程序完成计算。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)


相关推荐

  • linux ubuntu 关闭防火墙命令,LINUX关闭防火墙的方法

    linux ubuntu 关闭防火墙命令,LINUX关闭防火墙的方法LINUX关闭防火墙的方法导语:LINUX关闭防火墙的方法,你懂吗?下面的是百分网小编为大家搜集的LINUX关闭防火墙的方法,欢迎阅读,谢谢!(1)重启后永久性生效:开启:chkconfigiptableson关闭:chkconfigiptablesoff(2)即时生效,重启后失效:开启:serviceiptablesstart关闭:serviceiptablesstop需要说…

    2022年10月26日
  • vue获取上传文件路径_vue中文件上传及接收「建议收藏」

    vue获取上传文件路径_vue中文件上传及接收「建议收藏」准备:前端:vue环境+axios+elemen-ui后端:node.jsmulter前端代码://引入axiosimportaxiosfrom’axios’;//获取用户信息getUserInfo(){//发送请求获取用户信息getInfo().then(res=>{//接收数据let{data}=res;this.userInfo=data[0…

  • OpenGrok简单使用

    OpenGrok简单使用OpenGrok一个快速、便于使用的源代码搜索与对照引擎。它帮助你搜索,对照,定位你的源代码树。它能够明白各种程序文件格式和版本控制历史记录。借助Eclipse以及本地源码可以比较方便地分析Android源码,但是对于Native代码的调用就无法通过Eclipse的快速定位来查看相应的Native源码了,而且Android源码中对Native库的加载一般不是通过在Sta…

  • UFT对table的操作

    UFT对table的操作通常Table(类似电子表格的行和列组成的二维网格)中的数据是动态从后台数据库中抽取并呈现给用户的。下面是HTML的webtable的句法,tr代表一行,td代表所属行中单独的一个小格。<tableborder=”1″><tr><th>Month</th><th>Savings</th></tr><tr><td>January</td

  • MySQL轻快入门2021.3.18(字符集与乱码)[通俗易懂]

    MySQL轻快入门2021.3.18(字符集与乱码)[通俗易懂]输入,查询,展示的字符集编码一致就不会出现乱码。连接器好像对我们没有影响(仅限于gdk,utf-8),连接器字符编码太小转换的时候会造成数据的丢失。校对集就是它们的排序规则

  • Spring整合Mybatis注解方式

    Spring整合Mybatis注解方式Spring整合Mybatis(注解方式)目录Spring整合Mybatis(注解方式)环境准备纯注解方式配置类具体内容测试类具体内容环境准备jar包:Spring所需依赖:spring-context、spring-aspects、aspectjrt、aspectjweaver、spring-tx、spring-jdbcmybatis所需要:mybatis、mybatis-spring、mysql-connector-java、(druid、c3p0、HikariCP)辅

发表回复

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

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