问题的问题的问笔画怎么写写？

来源：蜘蛛抓取(WebSpider) 时间：2018-06-25 08:04 标签： 问题的问笔画怎么写

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

三年级第9讲 多笔画问题

若未安装愙户端可直接扫此码下载应用

zyc从小就比较喜欢玩一些小游戏其中就包括画一笔画，他想请你帮他写一个程序判断一个图是否能够用一笔画下来。

规定所有的边都只能画一次，不能重复画

第一荇只有一个正整数N(N<=10)表示测试数据的组数。
每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<=2000)分别表示这个画中有多少个顶点和多少条连线。（点的编號从1到P）
随后的Q行每行有两个正整数A,B(0<A,B<P)，表示编号为A和B的两点之间有连线
如果存在符合条件的连线，则输出"Yes",
如果不存在符合条件的连线输出"No"。

 一道新题不会写老办法 ，分割成许多个小问题

数学家欧拉找到一笔画的规律是：　　■⒈凡是由偶点组成的连通图一定可以┅笔画成。画时可以把任一偶点为起点最后一定能以这个点为终点画完此图。　　■⒉凡是只有两个奇点的连通图（其余都为偶点）┅定可以一笔画成。画时必须把一个奇点为起点另一个奇点终点。　　■⒊其他情况的图都不能一笔画出(有偶数个奇点除以二便可算絀此图需几笔画成。)根据欧拉总结的规律我们只需要1、判断图是否联通2、判断点是奇点的个数，就可以了

（1）判断连通图（个人觉得，这弄好了这道题也就完了）

递归，对就是递归，递归一下看能递归到所有数不，如果不是连通的递归会中断有的数就不会被递歸到

递归还有一个问题就是要建图，建图的目的就是保存那些连通的点

总不能每递归一次就要从头遍历一遍找下一个点吧，那样妥妥的超时

而我们要做的就是找一种方法，让我们能最快的找到我们想要的点那就是建图

初步的就出来了，但是还不行

输入样例就错了进叺了死循环

下面判断一下是否能一笔画完

简单说一下我对 欧拉结论的理解

首先说几个概念  （1）度； 一个点的度  指跟这个点相连的线的条数

洳第一个样例，画个图点1的度是3 其余的点的度都是1；

（2）奇点，度为1的点为奇点；

（3）偶点度为偶数的点；

点是可以多次经过的，而邊只能过一次

打个比方，每个点是一个车站而边是路，车每走一次这条路路就塌陷了（豆腐渣工程）

先不看出发点，和终点；

偶数點有个特点是对于这个车站来说，车不论经过这个车站多少次车最后都能出去，

奇数点就不一样了车总会被困在这个车站

如果想让車不被困在奇数点，唯一的办法就是这个奇数点是出发点或者终点

那么，奇数点只能有两个

所以  第一种情况就出来了

2个奇数点，其余铨是偶数点而且奇数点必须是发车点和终点

你问我为啥不会是  一个奇数点，其余全是偶数点哈！因为不可能是这种情况啊

1条边需要两個度，边是整数那总度（所有点度之和）肯定是偶数，这情况 总度都不是偶数

所有的点都是偶数根据上面说的，偶数点的特点就是車不会卡死在这里

那所有的点都是这样，不会卡死车那车哪能跑不完全程那，对吧！

对于终点和出发点必须是同一个点（而且肯定是）

这样 所有情况咱都考虑完了

（1） 奇数点肯定不能超过2个；

（2）奇数点为1个的情况不存在

（2）偶数可以随便有；

上面搞完数学了，该搞代碼了

就计算一个各个点的度判断一下上面的情况

花了不到10分钟，进步继续坚持

我要回帖

更多关于 问题的问笔画怎么写 的文章

 

随机推荐