[离散数学趣味题目]1,Catalan数饭后，姐妹洗碗，妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞。共有n个两两相异的碗，洗前也摞成一摞，也许因为妹妹贪玩，碗拿进橱子不及时，姐姐就把洗过的碗摞在傍边：-...+阅读

离散数学是数学的几个分支的总称，以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数无穷个元素；因此它充分描述了计算机科学离散性的特点。内容包含：数理逻辑、集合论、代数结构、图论、组合学、数论等。《离散数学》课程简介 离散数学是计算机专业的一门重要基础课。它所研究的对象是离散数量关系和离散结构数学结构模型。 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系， 因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。离散数学课程主要说明离散数学的各个分支的基本概念、基本理论和基本方法。

这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中；同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。 >>

数据结构用到离散数学的

一、语言是最重要的基本功 无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要 过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所 周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的 优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的 操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而 竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出 了更高的要求，是相当不利的。

其实，笔者并不主张大家在这种场合过多地运用面向对 象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会 降低程序的执行效率。 接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没 有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效 率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高 了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。

而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的 可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同 学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间 的。 C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一 接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。

但是 ，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必 须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法； 另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂 度，切忌对STL中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。

通过以上的分析，我们可以看出仅就信息学竞赛而言，对语言的掌握并不要求十分 全面，但是对于经常用到的部分，必须十分熟练，不允许有半点不清楚的地方，下面我 举个真实的例子来说明这个道理——即使是一点很细微的语言障碍，都有可能酿成错误 ： 在去年清华的赛区上，有一个队在做F题的时候使用了cout和printf的混合输出，由 于一个带缓冲一个不带，所以输出一长就混乱了。

只是因为当时judge team中负责F题的 人眼睛尖，看出答案没错只是顺序不对（答案有一页多，是所有题目中最长的一个输出 ），又看了看程序发现只是输出问题就给了个Presentation error（格式错）。如果审 题的人不是这样而是直接给一个 Wrong Answer，相信这个队是很难查到自己错在什么地 方的。 现在我们转入第二个方面的讨论，基础学科知识的积累。

二、以数学为主的基础知识十分重要 虽然被定性为程序设计竞赛，但是参赛选手所遇到的问题更多的是没有解决问题的 思路，而不是有了思路却死活不能实现，这就是平时积累的基础知识不够。今年World Final的总冠军是波兰华沙大学，其成员出自于数学系而非计算机系，这就是一个鲜活的 例子。竞赛中对于基础学科的涉及主要集中于数学，此外对于物理、电路等等也可能有 一定应用，但是不多。

因此，大一的同学也不必为自己还没学数据结构而感到不知从何 入手提高，把数学捡起来吧！下面我来谈谈在竞赛中应用的数学的主要分支。

1、离散数学——作为计算机学科的基础，离散数学是竞赛中涉及最多的数学分支， 其重中之重又在于图论和组合数学，尤其是图论。 图论之所以运用最多是因为它的变化最多，而且可以轻易地结合基本数据结构和许 多算法的基本思想，较多用到的知识包括连通性判断、DFS和BFS，关节点和关键路径、 欧拉回路、最小生成树、最短路径、二部图匹配和网络流等等。

虽然这部分的比重很大 ，但是往往也是竞赛中的难题所在，如果有初学者对于这部分的某些具体内容暂时感到 力不从心，也不必着急，可以慢慢积累。 竞赛中设计的组合计数问题大都需要用组合数学来解决，组合数学中的知识相比于 图论要简单一些，很多知识对于小学上过奥校的同学来说已经十分熟悉，但是也有一些 部分需要先对代数结构中的群论有初步了解才能进行学习。

组合数学在竞赛中很少以难 题的形式出现，但是如果积累不够，任何一道这方面的题目却都有可能成为难题。

2、数论——以素数判断和同余为模型构造出来的题目往往需要较多的数论知识来解 决，这部分在竞赛中的比重并不大，但只要来上一道，也足以使知识不足的人冥思苦想 上一阵时间。素数判断和同余最常见的是在以密码学为背景的题目中出现，在运用密码 学常识确定大概的过程之后，核心算法往往要涉及数论的内容。

3、计算几何——计算几何相比于其它部分来说是比较独立的，就是说它和其它的知 识点很少有过多的结合，较常用到的部分包括——线段相交的判断、多边形面积的计算 、内点外点的判断、...

谁有离散数学的概念总结呀？？

图论基本概念 重要定义：有向图：每条边都是有向边的图。无向图：每条边都是无向边的图。混合图：既有有向边又有无向边的图。 自回路：一条边的两端重合。重数：两顶点间若有几条边，称这些边为平行边，两顶点a,b间平行边的条数成为（a,b）的重数。 多重图：含有平行边的图。简单图：不含平行边和自回路的图。注意！一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D。称为的G定向图.底图：如果把一个有向图的每一条有向边的方向都去掉，得无向图G称为的D底图。逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。赋权图：每条边都赋上了值。

出度：与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。 入度：以该定点为终边的边数为入度。特殊！度数为零的定点称为孤立点。度数为一的点为悬挂点。无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn 完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。竟赛图：阶图中如果其底图是无向完全图，则程此有向完全图是竟塞图。注意！n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2。下面介召图两种操作：①删边：删去图中的某一条边但仍保留边的端点。②删点：删去图中某一点以及与这点相连的所有边。子图：删去一条边或一点剩下的图。生成子图：只删边不删点。

主子图：图中删去一点所得的子图称的主子图。补图：设为阶间单无向图，在中添加一些边后，可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图。重要定理：定理5.1.1 设图G是具有n个顶点m条边的有向图，其中点集V={v,v，….，v} deg+(vi)=deg-(vi)=m 定理5.1.2 设图G是具有n个顶点m条边的无向图，其中点集V={v,v,v，……，v} deg(vi)=2m 推论 在无向图中，度数为积数的顶点个数为偶数。通路和富权图的最短通路1通路和回路 基本概念：通路的长度：通路中边的条数。回路：如果通路中始点与终点相同。简单通路：如果通路中各边都不相同。基本通路：如果通路中各顶点都不相同。显然（基本通路一定是简单通路，但简单通路不一定是基本通路） 可达：在图G中如果存在一条v到d通路则称从v到d是可达。

连通：在无向图中如果任意两点是可达的，否则是不连通的。强连通：在有向图中如果任意两点是互可达的。单向连通：在有向图中如果存在任意两点的通路。弱连通：在有向图中如果其底图是连通的。权：在图的点或边上表明某种信息的数。赋权图：含有权的图。赋权图的最短通路问题的算法：先求出到某一点的最短通路，然后利用这个结果再去确定到另一点的最短通路，如此继续下去，直到找到到的最短通路为止。指标：设V是图的点集，T是V的子集，且T含有z但不含a，则称T为目标集。在目标集T中任取一个点t，由a到t但不通过目标集T中其它点所有通路中，个边权和的最小者称为点t关与T的指标记作DT(t)。图和矩阵 住意两个的区别：A·A 中元素的意义：当且仅当a 和a 都是1时，a a =1而a 和a 都为1意味着图G中有边（v ,v ）和（v ,v ）。

于是可得如下结论：从顶点v 和v 引出的边，如果共同终止于一些顶点，则这些终止顶点的数目就是b 的值；特别对于b ，其值就是v 的出度。A ·A中元素的意义：当且仅当a 和a 都为1时，a a =1，这意味着图中有边（v ,v ）和（v ,v ）。于是的得如下结论：从某些点引出的边，如果同时终止于v 和v ，则这样的顶点数就是的值。特别对于b ，其值就是的v 入度。幂A 中元素的意义：当m=1时，a 中的元素=1，说明存在一条边（v ,v ），或者说从v 到v 存在一条长度为一的通路。A 中元素a 表示从v 到v 的长度为m的所有通路的数目。 欧拉图 主要定义：如果图中存在一条通过图中个边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图。如果图中存在一条通过图中各边一次且仅一次的通路，则称此回路为欧拉通路，具有欧拉通路的图称为半欧拉图。

主要定理：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。设图G是有向连通图，图G是欧拉图的充要条件是图中每个顶点的入度和出度相等。设图G是有向连通图，图G是半欧拉图的充要条件是至多有两个顶点，其中一个顶点入度比它的出度大1，另一个顶点入度比它的出度少1；而其他顶点的入度和出度相等。哈密顿图 主要定义：如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。 主要定理：设图G是哈密顿图，如果从G中删去个p顶点得到图G'，则图G'的连通分支数小于等于p。

设图G是具有n个顶点的无向简单图，如果G中任意两个不同顶点的度数之和大于等于n-1，则具有哈密顿通路，即G是半...

离散数学讲些什么内容

离散数学（Discretemathematics）是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。离散的含义是指不同的连接在一起的元素，主要是研究基于离散量的结构和相互间的关系，其对象一般是有限个或可数个元素。离散数学在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。 通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础0学科内容1.集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数2.图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用3.代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4.组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理5.数理逻辑部分：命题逻辑、一阶谓词演算、消解原理。

以下为关联文档：

离散数学——二部图复习定义1： 若能将无向图G= 的顶点集V划分成两个子集 V1和V2（V1交V2为空集），使得G中任何一条边的两个端点一个属于V1，另一个属于V2，则称G为二部图（也称偶图），V 1、V2称为互补顶点子集，此时...

离散数学的离散是什么意思离散相对于连续而言，你应该学过高数吧，连续通俗来讲指平滑的过渡，比如1和2之间可以有无数的数，可以无限分割。 而离散指数据的不连续性，比如1,2,3。。。。这样画出的曲线是不连续...

离散数学集合证明(A∩B)∪c(A∪B) = (A∩B)∪（c(A)∩c( B)) = ((A∩B)∪c(A)）∩（（A∩B）∪c( B)) = (B∪c(A)）∩（A∪c( B)) = (A∪c(B)）∩（c(A)∪B), 注：这里c(A) 表示 A 的补集。 A∩（B±C） = A∩（（B-C）∪（C-...

求解离散数学题目证明：对于任意的正整数 a,b,c,d,m,n (1) 因为 ab=ba 所以<<a,b>,<a,b>&gt；€R 即R满足自反性 (2)如果 ad=bc 那么cb=da 所以 如果<<a,b>,<c,d>&gt；€R 必有<<c,d>,<a,b>&gt；€R...

求几道离散数学题1）对任意（a,b）∈R1∩R2， 则有（a,b）∈R1,(a,b)∈R2 ∵R1,R2是自反的 ∴（a,a）∈R1,(a,a)∈R2 ∴（a,a）∈R1∩R2 ∴R1∩R2是自反的 2）对任意（a,b）∈R1∩R2， 则有（a,b）∈R1,(a,b)∈R2 ∵R1,R2是对...

2道离散数学题5. R是A上的自反的，S是对称的，R是传递关系 对于任意关系X={a}，有<a,a&gt；的成为自反的，显然R成立，其他不满足 关于对称型，若某对称关系X中含有{a,b}关系，则X必含有{b,a}关系，显然只有...

离散数学题1个(1) G={(v1,v2)(v1,v6)(v2,v1)(v2,v6)(v2,v5)(v2,v3)(v3,v2)(v3,v4)(v3,v5)(v4,v3)(v4,v5)(v5,v3)(v5,v2)(v5,v6)(v6,v1)(v6,v2)(v6,v5)} (2)1 1 0 0 0 0 1 1 1 0 1 1 0 1 1...

离散数学有什么内容离散数学有什么内容，离散数学难不难啊：离散数学（Discrete mathematics）是数学的几个分支的总称，以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数无穷...

离散数学推理论证例题求解释离散数学推理论证例题求解释：楼主你好、遇到这种题 要冷静， 首先后边标注P的表示已知条件，标注类似T (1)E这样的，就是由前面第 （1）步的结论继续推证得到的结果。E应该是根据定理推...