数学在计算机编程中的应用

第1页，共3页题目：数学在计算机编程中的应用学院：计算机与信息科学学院专业年级：2009级计算机科学与技术（师范）第2页，共3页学生姓名：祝柱杰学号：20090512160指导教师：沈林职称：讲师2011年11月30日数学在计算机编程中的应用采用递归算法来解决该问题，因为递归算法有这样特征描述：为了求解出规模为n的问题的解，我们先设法将它分解成一些规模较小的问题，然后从这些较小问题的解能方便地构造出大问题的解，并且这些规模较小的问题也能采用同样的方法分解，分解成规模更小的问题。并能从这些更小的问题的结构造出规模稍大问题的解。现在，严格按照递归算法来解决问题。先定义递归方法hanio(intn,charA,charB,charC)，按如下步骤进行解题（设初始盘子个数为n）：若A塔上仅仅只有一个盘子（n=1），则直接从A移动到C，问题完全解决。若A塔上有一个以上的盘子（n1），则需要考虑以下三个步骤。第一步：把（n-l价盘子从Ａ塔经过移动，叠放到B塔上。在不违反规则情况下，所有（n-l）个盘子不能作为一个整体一起移动，而是要符合要求地从一个塔移到另一个塔上。用第3页，共3页hanio(n-l,B,A,C)调用递归方法，注意：这里是借助于C塔，将（n-l价盘子从A塔移动到B塔，A是源塔，B是目标塔。第二步：将剩下的第l个盘子（也就是最底下的一个）直接从A塔叠放到空着的c塔上。第二三步：用第一步的方法，再次将B塔七的所有盘子叠放到c塔上。同样，这一步实际上也是由一系列更小的符合规则的移动盘子的操作组成的。用hanio(n-l,B,A,C)调用递归方法。数学是计算机的鼻祖,计算机学科就是一门脱胎于数学学科的学科，在计算机专业中也普遍采用了数学的基本概念、基本思想以及相应的数学基本方法。数学理论是计算机的基础，而学习学计算机专业，编程又是必须学习的，而编程思想却又是数学思想在计算机应用中的最直接的体现。在商业的开发环境,比如做游戏开发,就需要数学基础很深的人工智能了。很多公司也会找那些数学系的来做开发,对他们来说,由于他们的数学概念模型已经建立了起来了所以他们在计算机方面也会很快就上手,并且很不会比计算机专业的学生差。随着计算机技术的快速发展，数学知识在计算机技术发展中，尤其是在计算机应用程序设计中处于极其重要的地位。同时，用数学思维解决各种程序设计方面的难题也是一个十分重要的步骤。在程序设计当中所解决的相当一部分问题都会涉及到各种各样的科学计算，这需要程序员将实际问题转换为程序，要经过对问题抽象的过程，建立起完善的数学模型，才能设计出好的软件。数学在编程中的体验不光是算法过程的书写，还有逻辑思维方面的能力。而软件编程的思维定式决定了一个人编程的水平，在编程过程中，数学思维清晰，编写出来的程序让人耳目一新。结合教学，通过调查分析，了解到超过85%的学生，他们在编程时是根据语法而编写程序，完全脱离了软件编程的思维，这种思维定式使得他们编写的程序相当糟糕，没有一点逻辑。所以数学思维不够，在软件编程会有很多的疑虑，显的有点缩手缩尾，而且写的程序也不够健全，缺乏逻辑。第4页，共3页总结数学在计算机中的应用：一、逻辑学在学科中的应用从早期的数理逻辑发展到今天的程序设计模型论。二、数学在学科中的应用从早期的抽象代数发展到今天的图形学、工程问题方面三、几何学的应用从早期的二维平面计算机绘图发展到今天的三维动画软件系统，并在与复分析的结合中产生了分形理论与技术。四、游戏、图形软件开发中引用了线性代数中大量的坐标变换，矩阵运算。五、在数据压缩与还原、信息安全方面引入了小波理论、代数编码理论等。六、图像/声音图像压缩算法/人工智能/CAD等领域广泛使用微积分作理论研究工具下面我将从一下的三个例子来分析数学在编程中的具体的应用。典型实例一：Hannoi塔问题[问题]Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，要求把a柱上n个圆盘按下述规则移到c柱上：(1)一次只能移一个圆盘；(2)圆盘只能在三个柱上存放；(3)在移动过程中，不允许大盘压小盘。问将这n个盘子从a柱移到c柱上，总计需要移动多少个盘次？解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，(1)当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h1=1。(2)当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共计3个盘次，故h2=3。(3)以此类推，当a柱上有n(n=2)个盘子时，总是先借助c柱把上面的n-1个盘移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动h(n-1)+1+h(n-1)个盘次。所以：hn=2h(n-1)+1（边界条件：h1=1）这个问题其实只是数学题目的简单变形。下面再来看一个应用更加灵活的例子：典型实例二：方格取数在一个n*m的方格中，m为奇数，放置有n*m个数，方格中间的下方有一人，此人可按照正前方相临的五个方向(方格)前进但不能越出方格。人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，使其数相加之和为最大。输出和的最大值。解：这题在本质上类似于递推，是从一个点可以到达的点计算可以到达一个点的所有可能点，然后从中发掘它们的关系。(1)我们用坐标（x,y）唯一确定一个点，其中（m,n）表示图的右上角，而人的出发点是([m/2],0)，受人前进方向的限制，能直接到达点(x,y)的点只有(x+2,y-1),(x+1,y-1),(x,y-1),(x-1,y-1),(x-2,y-1)。到达(x,y)的路径中和最大的路径必然要从到x+2,y-1),(x+1,y-1),(x,y-1),(x-1,y-1),(x-2,y-1)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的路径，(2)关系式如下：F(x,y)=Max{F(x+2,y-1),F(x+1,y-1),F(x,y-1),F(x-1,y-1),F(x-2,y-1)}+Num(x,y)其中Num(x,y)表示(x,y)点上的数字。边界条件为：F([m/2],0)=0,F(x,0)=-0(1=x=m且x[m/2])。这种问题，涉及到最值，采用的递推手法被称为动态规划。简称DP。典型实例三：从3个红球，5个白球，6个黑球中任意取出8个球，且其中必须有白球，输出所有可第5页，共3页能的方案。程序:#includestdio.hvoidmain(){inti,j,k;//I代表红球,j代表白球,k代表黑球printf(\nredwriteblack\n);for(i=0;i=3;i++)for(j=1;j=5;j++)//j=1是因为题目中要求必须要有白球{k=8-i-j;//黑球的个数if(k=0&&k=6){printf(%3d,%3d,%3d,i,j,k);//输出组成方案}}}从上面的例子中我们可以看到数学思维在编程中的体验。程序设计中可采用多种数学方法，恰如其分的数学方法可以大大减少程序运行的时间和所需空间，起到优化程序的作用。遇到一道题目时,如进制运算,多项式运算等,应不急于马上用递归,回溯等搜索算法,特别是测试数据的范围很大的时候。不妨先用笔算,从中发现一些规律.但是也不是每一道题都可以用数学方法完成,数学方法只能用于一些求总数,最值之类的题目上。数学方法的合理运用,可以给编程带来很大方便，现在一些软件的编写，越来越多的用到数学推导归纳。要在如此众多的程序编写员里面取得优异成绩，坚实的数学基础和能力是很重要的。程序设计解决问题都是实际应用问题,涉及各种各样的科学计算,而实际问题转换为程序,要经过一个对问题抽象的过程,建立起完善的数学模型,才能设计一个问题解决的程序。这需要程序员具有良好的数学基础。软件编程的思想最重要是算法，而算法是建立在数学思维上的，其实说白了，程序只是一件衣服，算法才是它的灵魂，算法就来自于数学，没有深厚的数学思维功底，是弄不懂算法的。