机器学习经典算法:决策树(2)

1. 概述

决策树(Decision Tree)是有监督学习中的一种算法,并且是一种基本的分类与回归的方法。决策树有两种:分类树和回归树。

  • 决策树是用于分类和回归的工具,它将数据特征值拆分为决策节点处的分支(例如,如果特征是一种颜色,则每种可能的颜色都会成为一个新分支),直到做出最终决策输出。
  • 一般来说,决策树只是一个嵌套 if-else 条件的结构。在数学上,决策树使用平行于任何一个轴的超平面将坐标系切割成超长方体。

树形结构

2. 构建

过程包括:特征选择、决策树的生成和决策树的剪枝

特征选择

标准:希望决策树的分支节点所包含的样本尽可能属于同一类别,也就是节点的纯度(purity)越来越高。

下面三个图表示的是纯度越来越低的过程,最后一个表示的是纯度最低的状态。

度量不纯度的指标有很多种,比如:熵、增益率、基尼指数。本文使用熵(香农熵)

香农熵

熵定义为信息的期望值。在信息论与概率统计中,熵是表示随机变量不确定性的度量。假定当前样本集合D中一共有n类样本,第i类样本为 ,那么 的信息定义为:

其中

通过上式,我们可以得到所有类别的信息。为了计算熵,我们需要计算所有类别所有可能值包含的信息期望值(数学期望),通过下面的公式得到:

值越小,则D的不纯度就越低。

"""
    函数功能:计算香农熵
    参数说明:
    	dataSet:原始数据集
    返回:
    	ent:香农熵的值
"""
def calEnt(dataSet):
    n = dataSet.shape[0] #数据集总行数
    iset = dataSet.iloc[:,-1].value_counts() #标签的所有类别
    p = iset/n #每一类标签所占比
    ent = (-p*np.log2(p)).sum() #计算信息熵
    return ent

信息增益

信息增益(Information Gain)的计算公式其实就是父节点的信息熵与其下所有子节点总信息熵之差。

信息增益的计算公式为:

3. 递归构建

ID3

构建决策树的算法有很多,比如ID3、C4.5和CART,本文选择ID3算法。

def createTree(dataSet):
    featlist = list(dataSet.columns) #提取出数据集所有的列
    classlist = dataSet.iloc[:,-1].value_counts() #获取最后一列类标签
    
    #判断最多标签数目是否等于数据集行数,或者数据集是否只有一列
    if classlist[0]==dataSet.shape[0] or dataSet.shape[1] == 1:
    	return classlist.index[0] #如果是,返回类标签
    
    axis = bestSplit(dataSet) #确定出当前最佳切分列的索引
    bestfeat = featlist[axis] #获取该索引对应的特征
    myTree = {bestfeat:{}} #采用字典嵌套的方式存储树信息
    
    del featlist[axis] #删除当前特征
    
    valuelist = set(dataSet.iloc[:,axis]) #提取最佳切分列所有属性值
    
    for value in valuelist: #对每一个属性值递归建树
    	myTree[bestfeat][value] = createTree(mySplit(dataSet,axis,value))
    return myTree

4. 存储

构造决策树是很耗时的任务,即使处理很小的数据集,也要花费几秒的时间,如果数据集很大,将会耗费很多计算时间。因此为了节省时间,建好树之后立马将其保存,后续使用直接调用即可。

#树的存储
np.save('myTree.npy',myTree)

#树的读取
read_myTree = np.load('myTree.npy').item()
read_myTree

5. 实战

5.1. 导入数据

lenses = pd.read_table('lenses.txt',header = None)
lenses.columns =['age','prescript','astigmatic','tearRate','class']
lenses

5.2. 划分数据

import random

"""
函数功能:切分训练集和测试集
参数说明:
    dataSet:输入的数据集
    rate:训练集所占比例
返回:
    train,test:切分好的训练集和测试集
"""
def randSplit(dataSet, rate):
    l = list(dataSet.index) #提取出索引
    random.shuffle(l) #随机打乱索引
    dataSet.index = l #将打乱后的索引重新赋值给原数据集
    n = dataSet.shape[0] #总行数
    m = int(n * rate) #训练集的数量
    train = dataSet.loc[range(m), :] #提取前m个记录作为训练集
    test = dataSet.loc[range(m, n), :] #剩下的作为测试集
    dataSet.index = range(dataSet.shape[0]) #更新原数据集的索引
    test.index = range(test.shape[0]) #更新测试集的索引
    return train, test

5.3. 生成树

#利用训练集生成决策树
lensesTree = createTree(train1)
lensesTree

#构造注解树
createPlot(lensesTree)

5.4. 分类

#用决策树进行分类并计算有预测准确率
acc_classify(train1,test1)

本文转载于网络 如有侵权请联系删除

相关文章

  • 搭建私有镜像仓库

    “本文将使用Podman在本地搭建一个私有的镜像仓库,并查询该私有库的镜像”1,创建registry目录。 $mkdir-p/opt/registry/{auth,certs,data}复制2,生成registry服务器证书,并创建密码。$cd/opt/registry/certs $opensslreq-newkeyrsa:4096-nodes-sha256-keyoutdomain.key-x509-days365-outdomain.crt Generatinga4096bitRSAprivatekey ....................++ ......................................................................................................................................++ writingnewprivatekeyto'domain.key' ----- Youareabouttobeaskedtoenterinfo

  • 如何排查Go 程序 CPU 占用过高问题

    内推美团:求一份Java简历,坐标:北京。左边二维码有我联系方式前言如果要在golang开发过程中进行性能调优,一般需要使用pprof,本文介绍的是pprof工具使用方法。下载测试代码goget中可以获取测试程序,注意加上-d避免下载后自动安装Githubgoget-dgithub.com/wolfogre/go-pprof-practice cd$GOPATH/src/github.com/wolfogre/go-pprof-practice复制如果goget下载不了,可以gitclone下载girclonehttps://github.com/wolfogre/go-pprof-practice复制对代码进行编译然后运行gomodinit gomodtidy复制最后再运行gobuild ./go-pprof-practice复制保持程序运行,打开浏览器访问http://localhost:6060/debug/pprof/,可以看到如下页面:在这里插入图片描述参数说明类型描述备注allocs内存分配情况的采样信息可以用浏览器打开,但可读性不高blocks阻塞操作情况的采样信息可以用

  • CPVR2020|无监督视觉表征学习中的动量对比

    作者|程豪 编辑|李仲深今天给大家介绍的是何凯明等人在CVPR2020上发表的文章MomentumContrastforUnsupervisedVisualRepresentationLearning。如果从字典查找的角度看对比学习,那么这篇文章提出了动量对比(Moco)的方法,就是利用队列和移动平均编码器构建出动态字典进行查找。这就能够动态地构建一个大而一致的字典,从而增强无监督对比学习。实验结果表明Moco学习到的表征能够很好地用到下游任务中。Moco在7个检测/分割任务中超过了其他通过有监督预训练模型的结果。这表明在许多视觉任务中,无监督和有监督的表征学习之间的差距已经基本上被缩小了。一、研究背景无监督表征学习在自然语言处理中非常成功,如GPT和BERT。但在计算机视觉领域,基于有监督的预训练模型仍然占主导地位,而无监督的预训练方法普遍滞后。原因可能是它们各自信号空间的差异。语言任务具有离散的信号空间(单词、子单词单元等),用于构建无监督的标记化词典比较容易。相比之下,计算机视觉任务更关注词典的建立,因为原始信号是在一个连续的高维空间中,这点是与单词不同。这篇文章提出了“动量对比

  • 链表:由浅入深

    今天又到了算法的主题了,上次我们聊到了数组:面试中的疑难点,这次我们来聊另外一种线性结构,链表。 本质虽然链表与数组一样都是线性结构,但它们之间还是有本质的区别的。数组在内存中是一块连续的存储区域,而链表可以支持随机存储,非连续的存储空间。链表的种类可以分为,单链表、双向链表、循环链表、双向循环链表。它们的本质都是一样的,不同的是具体的表现与应用。简单来说,对于单链表是每一个节点都有一个next后续指针,它都指向当前节点的下一个链表节点;对于链表的尾节点,由于是链表的最后一个节点,所以它的next为null。双向链表与单链表所不同的是,它除了有next指针之外,还有prev前驱指针,它指向于当前节点的上一个节点;特殊的,链表的头节点的prev为null。循环链表与单链表的区别是,它的最后一个节点的next将不再为null,而是指向头节点或者链表的其它位置节点。而对于双向循环链表也是同样的原理。插入我们都听过这么一句话,链表适合插入与删除。这主要是由于链表自身的数据结构决定的。对于单链表来说,向已知的一个节点后插入一个新的节点,它所要做的事情就是将当前节点的next指针指向新的节点,然后

  • Docker日常使用方式

    前提在安装docker之前,建议你设置系统的国内镜像源先哦,很快~嗯,快。 阿里云镜像源:https://developer.aliyun.com/mirror/安装安装docker下面都是官网地址: ubuntu:https://docs.docker.com/engine/install/ubuntu/ centos:https://docs.docker.com/engine/install/centos/ 其他版本就是url后面的几个英文不同。开机启动sudosystemctlenabledocker.service复制设置国内镜像docker中国区的镜像:https://registry.docker-cn.com 网易:http://hub-mirror.c.163.com 中国科技大学:https://docker.mirrors.ustc.edu.cn 阿里云:https://cr.console.aliyun.com/点击左侧栏有个镜像加速地址,就可以看到你的加速镜像地址 sudomkdir-p/etc/docker sudotee/etc/docker/daemon

  • 理解CSS布局和块格式化上下文

    在进行html布局及css编写的时候,你是否遇到过这样的问题:子元素设置浮动脱离文档流后,父元素无法将其完全包裹子元素浮动实现两栏布局时,另一个子元素与浮动子元素重叠垂直方向的外边距margin重叠 ...通常我们使用块级格式化上下文(BFC)就能解决。什么是BFC?块格式化上下文(BlockFormattingContext,BFC)是Web页面的可视化CSS渲染的一部分,是块盒子的布局过程发生的区域,也是浮动元素与其他元素交互的区域。FC(formattingcontext)直译过来是格式化上下文,它是页面中的一块渲染区域,有一套渲染规则,决定了其子元素如何布局,以及和其他元素之间的关系和作用。BFC就是页面上的一个隔离的独立容器,容器里面的子元素不会影响到外面的元素,并且容器元素不会影响兄弟元素的布局。什么情况下会创建BFC根元素或包含根元素的元素浮动元素(元素的float不是none)绝对定位元素(元素的position为absolute或fixed)行内块元素(元素的display为inline-block)表格单元格(元素的display为table-cell,HTML表格

  • 《PMBOK导读》第十一章 风险管理

    第十一章风险管理简介项目管理49个子过程,其中项目风险管理的7个项目风险管理包括规划风险管理、识别风险、开展风险分析、规划风险应对、实施风险应对和监督风险的各个过程。项目风险管理的目标在于提高正面风险的概率和(或)影响,降低负面风险的概率和(或)影响,从而提高项目成功的可能性项目风险管理的过程是11.1规划风险管理—定义如何实施项目风险管理活动的过程11.2识别风险—识别单个项目风险,以及整体项目风险的来源,并记录风险特征的过程11.3实施定性风险分析—通过评估单个项目风险发生的概率和影响以及其他特征,对风险进行优先级排序,从而为后续分析或行动提供基础的过程11.4实施定量风险分析—就已识别的单个项目风险和其他不确定性的来源对整体项目目标的综合影响进行定量分析的过程11.5规划风险应对—为处理整体项目风险敞口,以及应对单个项目风险,而制定可选方案、选择应对策略并商定应对行动的过程11.6实施风险应对—执行商定的风险应对计划的过程11.7监督风险—在整个项目期间,监督商定的风险应对计划的实施、跟踪已识别风险、识别和分析新风险,以及评估风险管理有效性的过程项目风险管理的核心概念每个项目都在

  • Python3刷题系列(七)

    目录:1,Leetcode-2412,Leetcode-693,Leetcode-14,Leetcode-3475,Leetcode-4556,Leetcode-2157,Leetcode-758,Leetcode-1671,Leetcode-241:https://leetcode.com/problems/different-ways-to-add-parentheses/#leetcode-241:分治思想 classSolution:#使用递归实现分治思想,战胜了63.59% defdiffWaysToCompute(self,input:str)->List[int]: return_list=[] foriinrange(len(input)): c=input[i] ifcin['+','-','*']: left=self.diffWaysToCompute(input[:i]) right=self.diffWaysToCompute(input[i+1:]) forlinleft: forrinrig

  • 开发dubbo应用程序(一)入门demo详解

    1.简介:引用自Dubbo官方文档简介: http://dubbo.apache.org/zh-cn/docs/user/dependencies.html 随着互联网的发展,网站应用的规模不断扩大,常规的垂直应用架构已无法应对,分布式服务架构以及流动计算架构势在必行,亟需一个治理系统确保架构有条不紊的演进。 单一应用架构 当网站流量很小时,只需一个应用,将所有功能都部署在一起,以减少部署节点和成本。此时,用于简化增删改查工作量的数据访问框架(ORM)是关键。 垂直应用架构 当访问量逐渐增大,单一应用增加机器带来的加速度越来越小,将应用拆成互不相干的几个应用,以提升效率。此时,用于加速前端页面开发的Web框架(MVC)是关键。 分布式服务架构 当垂直应用越来越多,应用之间交互不可避免,将核心业务抽取出来,作为独立的服务,逐渐形成稳定的服务中心,使前端应用能更快速的响应多变的市场需求。此时,用于提高业务复用及整合的分布式服务框架(RPC)是关键。 流动计算架构 当服务越来越多,容量的评估,小服务资源的浪费等问题逐渐显现,此时需增加一个调度中心基于访问压力实时管理集群容量,提高集群利用率。

  • 人生苦短,为什么我要用Python?

    选自GitHub机器之心编译参与:卓汇源、思源本文转自机器之心,转载需授权随着机器学习的兴起,Python逐步成为了「最受欢迎」的语言。它简单易用、逻辑明确并拥有海量的扩展包,因此其不仅成为机器学习与数据科学的首选语言,同时在网页、数据爬取可科学研究等方面成为不二选择。此外,很多入门级的机器学习开发者都是跟随大流选择Python,但到底为什么要选择Python就是本文的核心内容。本教程的目的是让你相信两件事:首先,Python是一种非常棒的编程语言;其次,如果你是一名科学家,Python很可能值得你去学习。本教程并非想要说明Python是一种万能的语言;相反,作者明确讨论了在几种情况下,Python并不是一种明智的选择。本教程的目的只是提供对Python一些核心特征的评论,并阐述作为一种通用的科学计算语言,它比其他常用的替代方案(最著名的是R和Matlab)更有优势。本教程的其余部分假定你已经有了一些编程经验,如果你非常精通其他以数据为中心的语言(如R或Matlab),理解本教程就会非常容易。本教程不能算作一份关于Python的介绍,且文章重点在于为什么应该学习Python而不是怎样写

  • 投融资汇总 | 本周(1.29-2.4)时空电动获IDG资本10亿元投资

    国内外致力于未来出行生态打造的公司,融资金额普遍偏高。本周投融资事件共33起,其中人工智能领域融资事件为18起,收购事件为1起,占比58%,最为火热;未来医疗领域融资事件为7起,物联网4起,3R(VR/AR/MR)领域为2起,新能源为1起。与上周相比,本周投融资事件的整体配比没有太大变化,人工智能领域的大数据分析和应用类型的公司依然是最受资本欢迎的,未来医疗领域融资的方向还是侧重于药物研制方面。本周值得关注的融资事件中,人工智能、未来医疗和物联网领域内各有一起较大的融资事件,分别为:时空电动获IDG资本10亿元的投资;一脉阳光(一家医疗影像公司)获4亿元B轮融资,由百度资本领投;智能卧室家居产品制造商麟盛科技获2亿元战略投资。人工智能 新农宝农业信息化服务商新农宝宣布完成2000万元的A+轮融资,本轮投资方为夸克资本、甲子启航。新农宝业务方向是面向于涉农农业提供信息化云服务,助力涉农企业进行数字化转型与升级,平台的特点是提供全渠道、全场景解决方案,以新农宝农业云(U-Cloud)为例,该云平台包含五大模块:U田(农田植保运营管理系统)、U智(全渠道营销与运营管理系统)、U问(农技专家在

  • P1801 黑匣子_NOI导刊2010提高(06)

    题目描述BlackBox是一种原始的数据库。它可以储存一个整数数组,还有一个特别的变量i。最开始的时候BlackBox是空的.而i等于0。这个BlackBox要处理一串命令。命令只有两种:ADD(x):把x元素放进BlackBox;GET:i加1,然后输出Blackhox中第i小的数。记住:第i小的数,就是BlackBox里的数的按从小到大的顺序排序后的第i个元素。例如:我们来演示一下一个有11个命令的命令串。(如下图所示)现在要求找出对于给定的命令串的最好的处理方法。ADD和GET命令分别最多200000个。现在用两个整数数组来表示命令串:1.A(1),A(2),…A(M):一串将要被放进BlackBox的元素。每个数都是绝对值不超过2000000000的整数,M$200000。例如上面的例子就是A=(3,1,一4,2,8,-1000,2)。2.u(1),u(2),…u(N):表示第u(j)个元素被放进了BlaekBox里后就出现一个GET命令。例如上面的例子中u=(l,2,6,6)。输入数据不用判错。输入输出格式输入格式:第一行,两个整数,M,N。第二行,M个整数,表示A(l)……

  • .NET Core的日志[4]:将日志写入EventLog

    面向Windows的编程人员应该不会对EventLog感到陌生,以至于很多人提到日志,首先想到的就是EventLog。EventLog不仅仅记录了Windows系统自身针对各种事件的日志,我们的应用也可以利用提供的API将日志消息写到EventLog中。与EventLog相关的API都定义在System.Diagnostics.EventLog这个类型中,我们不仅仅可以利用它读取、写入和删除日志,还可以使用它来创建和删除EventSource。.NETCore的日志模型利用EventLogLogger实现了与EventLog的集成,不过EventLogLogger使用的是一个抽象化的EventLog。目录 一、抽象化的EventLog 二、EventLogLogger 三、EventLogLoggerProvider一、抽象化的EventLogEventLogLogger定义在“Microsoft.Extensions.Logging.EventLog”这个NuGet包中。就目前这个版本来说,该NuGet包承载的程序集只适用于.NETFramework应用,换句话说,EventLogL

  • 教你用Ossim平台检测网络的Shellcode攻击

    教你用Ossim平台检测网络的Shellcode攻击行为 教程: http://www.tudou.com/programs/view/-hxTm0q1tDY/   以下是视频截图:     更多视频内容: 本文出自“李晨光原创技术博客”博客,请务必保留此出处http://chenguang.blog.51cto.com/350944/1393312

  • http协议

    主要特点   简单快速:客户向服务器请求服务时,只需传送请求方法和路径,使得HTTP服务器的程序规模小,因而通信速度很快。   灵活:http允许传输任意类型的数据对象   无连接:限制每次连接只处理一个请求。服务器处理完客户的请求,并收到客户的应答后,即断开连接。采用这种方式可以节省传输时间。   无状态:协议对于事务处理没有记忆能力。缺少状态意味着如果后续处理需要前面的信息,则它必须重传. 报文组成   请求报文:请求行,请求头,空行,请求体   响应报文:状态行,响应头,空号,响应体 1POST/HTTP1.1 2Host:www.wrox.com 3User-Agent:Mozilla/4.0(compatible;MSIE6.0;WindowsNT5.1;SV1;.NETCLR2.0.50727;.NETCLR3.0.04506.648;.NETCLR3.5.21022) 4Content-Type:application/x-www-form-urlencoded 5Content-Length:40 6Connection:Keep-Alive 7 8name=Prof

  • Windows安装tensorflow教程 GPU版

      前置准备 查看GPU型号 电脑桌面->右键我的电脑->选择管理->点击设备管理器 如下图:   如果不是英伟达显卡,那么不用往下看了,GAMEOVER!   查看CUDA算力 gpu版本要求电脑的GPU硬件必须有CUDA支持,并且计算能力最低为3.5以上。 查看地址在这里:https://developer.nvidia.com/cuda-gpus 这个就是我的:   下载GPU驱动 下载地址:https://www.nvidia.com/download/index.aspx?lang=en-us# 我的演示:   这个驱动的版本号必须要达到418.x以上   下载Anaconda 清华大学镜像地址:https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/ 我下载的版本是:Anaconda3-5.3.1-Windows-x86_64.exe 配置高级选项的时候 第一个我选择将Anaconda加入环境变量 第二个注册P

  • XStream 遇到的问题

      1.xstreamxml转bean对象,双划线问题    解决:主要是用到了newXmlFriendlyNameCoder("_-","_"),在创建XStream对象时可XStreamxStream=newXStream(newXppDriver(newXmlFriendlyNameCoder("_-","_")));   2.获取节点的属性值以及自身值     方法1:@XStreamConverter(value=ToAttributedValueConverter.class,strings={"value"})         对应的value是bean对象的属性名,具体示例: @XStreamAlias("RETURNCODE") @XStreamConverter(value=ToAttributedValueConverter.class,strings={"value"}) publicclassReturnCodeVO{ @XStreamAsAttribute @XStreamAlias("CODE") privateStringcode

  • js 浮点数计算Bug

    之前在写项目时候,直接对带小数点的数据进行运算,发现所得到的值并不是自己想要的。 经过一系列学习后,发现在JavaScript中,浮点数运算都是先转换成二进制,在转成二进制的时候有出现无限循环小数,故之后的运算都出现了问题(这是基于IEEE754数值的浮点计算的通病)。 因此,就翻阅了前公司的js工具库,找到一些用于运算的函数。 //加法 functionaccAdd(arg1,arg2){ varr1,r2,m; try{r1=arg1.toString().split(".")[1].length}catch(e){r1=0} try{r2=arg2.toString().split(".")[1].length}catch(e){r2=0} m=Math.pow(10,Math.max(r1,r2)) return((arg1*m+arg2*m)/m).toFixed(2); } //除法 functionaccDiv(arg1,arg2){ vart1=0,t2=0,r1,r2; try{t1=arg1.toString().split(".")[1].length}catc

  • 2.27专项测试复盘

    总排序趟数与初始状态无关的有:(除了快速排序和优化的冒泡,其他都是) 算法复杂度与初始状态无关的有:堆排序、归并排序、选择排序、基数排序。 元素总比较次数与初始状态无关的有:选择排序、基数排序。 元素总移动次数与初始状态无关的有:归并排序、基数排序。 快速排序的最坏情形是数组为正序或逆序,如果pos总是选择第一个元素,那么每次划分只得到一个比上一次划分少一个记录的子序列,此时需要执行次递归调用。显然,采用A(划分元素为三者居中),能够将每次待排序的pos尽可能一分为二,从而使得递归深度为log(2,n),即空间复杂度为O(log(2,n))。 排序时,若不采用计数排序的等空间换时间的方法,合并m个长度为n的已排序数组的时间复杂度最优为(O(mn(logm))) 解析:当n=1时,就成了m个数的归并排序,时间复杂度为O(mlogm) 在最好情况下,下列排序算法中()排序算法所需比较关键字次数最少。 A.冒泡排序 B.直接插入排序 C.快速排序 D.归并排序 解析:冒泡注意加flag可以在无交换时一次退出,最优O(N),比较N-1次;直插法在原数组有序时也只比较

  • GDI双缓冲绘图

    一、简介 在进行复杂图形绘制时,若直接在屏幕DC上进行绘制,则会出现明显的闪烁。闪烁产生的原因是当绘制的图形较为复杂时,图形绘制过程中就被刷新到屏幕上,导致结果断断续续地显示出来。双缓冲绘图的原理是在另开辟一块内存用于绘制,当所有绘制工作完成后将内存数据一次性拷贝到屏幕上。 双缓冲绘图步骤: 创建兼容DC(CreateCompatibleDC) 创建兼容位图(CreateCompatibleBitmap) 将兼容位图选入兼容DC(SelectObject) 在兼容DC中进行绘制工作 将兼容DC中的像素拷贝至屏幕DC(BitBlt) 从兼容DC中换出兼容位图(SelectObject) 删除兼容位图(DeleteObject) 删除兼容DC(DeleteObject) 二、实现: 演示程序绘制了从窗口中心发射的300条射线,为了凸显双缓冲的效果,特意在绘制每条线段时添加延时操作(sleep)。可以发现,若直接在屏幕DC上绘制,能够明显感觉到每条线段的绘制过程,而采用双缓冲则无此现象。 直接绘制代码: voidCtestBFDlg::OnBnClickedDirectDraw() {

  • P1331 海战(洛谷)

    题目描述 在峰会期间,武装部队得处于高度戒备。警察将监视每一条大街,军队将保卫建筑物,领空将布满了F-2003飞机。此外,巡洋船只和舰队将被派去保护海岸线。不幸的是因为种种原因,国防海军部仅有很少的几位军官能指挥大型海战。因此,他们考虑培养一些新的海军指挥官,他们选择了“海战”游戏来帮助学习。 在这个著名的游戏中,在一个方形的盘上放置了固定数量和形状的船只,每只船却不能碰到其它的船。在这个题中,我们仅考虑船是方形的,所有的船只都是由图形组成的方形。编写程序求出该棋盘上放置的船只的总数。 输入格式 输入文件头一行由用空格隔开的两个整数R和C组成,1<=R,C<=1000,这两个数分别表示游戏棋盘的行数和列数。接下来的R行每行包含C个字符,每个字符可以为“#”,也可为“.”,“#”表示船只的一部分,“.”表示水。 输出格式 为每一个段落输出一行解。如果船的位置放得正确(即棋盘上只存在相互之间不能接触的方形,如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只,则称这两艘船相互接触了)。就输出一段话“ThereareSships.”,S表示船只的数量。否则输出“Bad

相关推荐

推荐阅读