GS亢延海组合数学在计算机中的应用

1、硕士课程论文组合数学在计算机中的应用 学生学号 GS1221611学生姓名 亢延海 学科专业 软件工程硕士指导教师 李卫国 培养院系 软件学院摘 要介绍了组合数学的概念、起源与研究的主要内容，分析了组合数学的特点以及其在生活中的应用，阐述了组合数学与计算机软件的联系，及举例说明了如何应用组合数学化简汉诺塔问题，展示组合数学辉煌的明天。关键词：组合数学，离散数学，计算机科学AbstractThe concept of the combinatorics, the history, the development and the content are introduced. The charac

2、teristics of the combinatorics and its applications to the computer software are analyzed. And demonstrate how to resolve Hanoi tower problem in combinatorics in computer science, showing a brilliant future combinatorics. Key words: combinatorial mathematics, discrete mathematics, Computer Science目录

3、第一章 组合数学概述4第二章 组合数学在生活中的应用4第三章 组合数学与计算机软件43.1信息时代的组合数学53.2组合数学在计算机软件的应用53.3组合数学与计算机软件的关系53.4组合数学在国外软件业的发展状况6第四章 计算机化简汉诺塔问题64.1问题来源64.2分析问题74.3基于JAVA的解决方案74.4结合组合数学化简问题84.5化简后JAVA 的实现8第五章 总结9参考文献10第一章 组合数学概述组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据

4、，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对

5、象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。第二章 组合数学在生活中的应用在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现了一个更简单的证明。当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。航空调度和航班的设定也是

6、组合数学的问题。怎样确定各个航班以满足 不同旅客转机的需要，同时也使得每个机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是 组合数学的问题。组合数学在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关

7、注。总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。第三章 组合数学与计算机软件随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。3.1信息时代的组合数学现代数学可以分为两大类:一类是研究连续对象,如分析、方程等,另一类就是研究离散对象的组合数学。计算机科学就是算法的科学,而计算机所处理的对象是离散的数据,研究离散对象的科学恰恰就是组合数学。因此,在信息时代的今天,组合数学就是信息时代的数学。3.2组合数学

8、在计算机软件的应用随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。组合数学在计算机方面的应用极其广泛。计算机软件与各种算法的研究分不开,为了衡量一个算法的效率,必须估计用此算法解答具有给定长的输入(问题) 时需要多少步(例如算术运算、二进制比较、程序调用等的次数) 。这要求对算法所需的计算量及存储单元数进行估算,这就是计数问题的内容,而组合数学分析主要研究内容就是计数和枚举的方法和理论。3.3组合数学与计算机软件的关系我国在软件上的落后

9、，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外，可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身也已经发展到了很深、很广的程度并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。一般人可能会认为数学是一门纯粹的基础科学，1+1的解决可

10、能不会有任何实际的意义。如果真是这样，一门纯粹学科的发展落后几年，甚至十年，关系也不大。然而中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分析，信息压缩，网络安全，编码技术，系统软件，并行算法，数学机械化和计算机推理，等等。此外，与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的企业抢去很大的市场。如果我们现在在信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；只要我们能抢回信息技术的数学基地，那么我们还有可能在软件产业的竞争中，扭转

11、局面，甚至反败为胜。吴文俊院士开创和领导的数学机械化研究，为中国在信息技术领域占领了一个重要的阵地，有了雄厚的数学基础，自然就有了软件开发的竞争力。这样的阵地多几个，我们的软件产业就会产生新的局面。值得注意的是，印度有很好的统计和组合数学基础，这可能也是印度的软件产业近几年有很大发展的原因。3.4组合数学在国外软件业的发展状况纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard

12、，Yale，.）都有第一流的组合数学家。计算机科学通过对软件产业的促进，带来了巨大的效益，这已是不争之事实。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如IBM，AT&T都有全世界最强的组合研究中心。Microsoft 的Bill Gates近来也在提倡和支持计算机科学的基础研究。例如，Bell实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然日趋激烈。美国政府也成立了离散

13、数学及理论计算机科学中心DIMACS（与Princeton大学，Rutgers大学，AT&T 联合创办的，设在Rutgers大学），该中心已是组合数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在1997年选择了组合数学作为研究专题，组织了为期一年的研究活动。日本的NEC公司还在美国的设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题，该中心主任R. Tarjan即是组合数学的权威。除上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意

14、大利、西班牙等国家都建立了各种形式的组合数学研究中心。近几年，南美国家也在积极推动组合数学的研究。澳大利亚，新西兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。日本有组合数学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本的组合数学这几年的发展极为迅速。台湾、香港两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重点方向来发展。世界各地对组合数学的如此钟爱显然是有原因的，那就是没有组合数学就没有计算机科学，没有计算机软

15、件。第四章 计算机化简汉诺塔问题4.1问题来源汉诺塔( Hanoi tower ) 问题源自一个古老的传说, 相传在古印度的一座神庙前, 有一根串着64 个祭神用的圆盘的柱子, 这些圆盘是按大小顺序叠放的, 大的在下, 小的在上, 僧侣们要将这些圆盘借助一个柱子移到另一个柱子上, 移动过程中一次只能移动一个, 并且要始终保证每个柱子上的圆盘大的在下, 小的在上，什么时候移完，就意味着世界末日的到来。 现我们假定三根柱子A、B、C, 圆盘的数量为n。问题的图形描述如下图所示：4.2分析问题 当盘子数为2时,只需要将上面的一个盘子从A搬到B上,再将A柱的最下面的盘子从A 搬到C 柱上, 最后把B

16、上的盘子搬到C 柱上即可, 搬运次数为3次;现我们假定盘子数n时,把A柱上面的n-1盘子看成一个整体, 并设把A柱上的n-1个盘子搬到B上, 设需要的搬运次数为hn-1,则n个盘子的搬运过程类似于2个盘子,即把A柱上的n-1个盘子从A搬到B柱上,搬运次数为hn-1,再把A柱的最下面的盘子从A 搬到C柱上,搬运次数为1次,最后把B上的盘子搬到C柱上,搬运次数同样也为hn-1,总共的搬运次数为hn=2*hn-1+1。 4.3基于JAVA的解决方案由公式我们可以利用递推关系解决汉诺塔问题。以下为程序中的类图图中出现了两个类, 类hannuta 主要用于进行递归调用, 谨记要设置递归出口; 类hann

17、uta1 进行输入、调用类hannuta进行递归、输出显示结果, 其中属性sum1用于存放最终结果, 字符串变量ns 来获取对话框中的字符, 属性n 则存放柱子上的圆盘数。程序段如下: hannuta hh = new hannuta( ) ; /声明一个新类 ns= JOptionPane.showInputDialog("inputa number") ; /显示对话框 n = Integer.parseInt(ns); /从对话框获取数据, 并转换成整数 sum1= hh.jiajia(n); /调用方法 System.out.println("sum =

18、"+ sum 1); /输出结果 class hannuta /命名类 long jiajia(int n) / 定义方法, 实现递归 long sum=0; /存放递归结果 if (n= = 1) /递归出口 sum = 1; else sum = 2*jiajia(n- 1)+ 1; /递归调用 return sum; /返回数值 4.4结合组合数学化简问题 上面用递推关系解答了这个计数问题, 现用母函数为工具求得计数序列的通用表达式, 从而化简递推关系。母函数在组合数学中是重要的计数工具, 利用母函数可解出非线性常系数递推关系。对于序列a0,a1, a2, , 定义G( x )

19、 = a0+ a1 + a2 + 为序列的母函数, 其中序列与母函数是一一对应的。下面我们利用母函数化简上面的递推关系。设序列h1 , h2, h3, 的母函数为H( x ) , 则H( X ) = H1X + H2 X 2 + H3 X 3 + KK = HnXn在Hk= 2*Hk-1+1 等式两端同乘以Xk , 并形式地求和得H( X ) - X = 2*X*H( X ) + X2/( 1- X ) ( 1- 2X )H( X )=X + X2/(1- X) H( X )=X/( ( 1 - X ) ( 1- 2X ) H( X ) = A/( 1-2X ) + B/( - X ) , 由

20、待定系数法解得A=1, B=-1, 所以H( X ) = 1/( 1 - 2X )-1/( 1- X ) 。利用标准母函数展开为:H( X )=(1+2X+22X2 + K ) - ( 1+ X + X2 + K ) = (2k - 1)Xk , 则xn的系数即为所求的结果即Hn=2n- 1。 4.5化简后JAVA 的实现long sum; /定义变量, 存放最终结果 long mul=1; /存放中间变量2n 的结果 int n,i; String ns; ns=JOptionPane.showInputDialog( "input a number"); /显示对话框 n=Integer.parseInt( ns ); /从对话框获取数据, 并转换成整for( i= 1;