浅谈数学在计算机中的应用

http://blog.sina.com.cn/s/blog_3eaaa817010008l4.html


【序言】
 本人对计算机有着浓厚兴趣，深刻体会到了数学这一自然科学的“王后”，在计算机中的广泛应用。本文将以实例与大家共同探讨。

 【数学在编程中的应用】
 首先我们来看一个使用数学方法可以大大提高效率的例子。

 实例一：给定一个自然数a，判断它是不是质数。

 普通的想法：若a是合数，那么必然有一个因数不大于a1/2，建立一个a1/2以内的质数表，逐一检索。显然，这样速度太慢！ 
 下面介绍一种基于费马小定理的Miller-Rabin测试算法：
 首先是引理：费马小定理，相信大家都有耳闻，这里我也不嫌累赘，仍旧列出。
 若n是质数，(a,n)=1，则an-1mod n =1。  
 同样，若我们选取若干个a，都满足以上等式的话，几乎可以肯定n是素数。（尽管不能完全确认，但在实际操作中是可行的）
 下面给出算法：
 Function Miller-Rabin(n:longint):Boolean;
 Begin
   For I:=1 to s do
   Begin
     a:=random(n-2)+2;
     If modular_exp(a,n-1,n)<>1 then return false;
 End;
 Return true;
   End;

 事实上，数学在计算机当中最为重要的还是递推关系的应用：许多看似棘手的题目，在有了这一层的关系后便显得柳暗花明了。
 
实例二：Hannoi塔问题

 Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，
 要求把a柱上n个圆盘按下述规则移到c柱上：
 （1）       一次只能移一个圆盘；
 （2）       圆盘只能在三个柱上存放；
 （3）       在移动过程中，不允许大盘压小盘。
 问将这n个盘子从a柱移到c柱上，总计需要移动多少个盘次？
 解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b
 柱上去；然后将大盘子从a柱移到c柱；最后，将b柱上的小盘子移到c柱上，共计3个盘次，故h2=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个数，
 方格中间的下方有一人，此人可按照正前方相临的五个方向(方格)前进但不能越出方格。人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径，
 使其数相加之和为最大。输出和的最大值。
 解：这题在本质上类似于递推，是从一个点可以到达的点计算可以到达一个点的所有可能点，然后从中发掘它们的关系。我们用坐标（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)的几条路径中产生，既然要求最优方案，当然要挑一条和最大的
 路径，关系式如下：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。
 程序设计中可采用多种数学方法，恰如其分的数学方法可以大大减少程序运行的时间和所需空间，起到优化程序的作用。遇到一道题目时,如进制运算,多项式运算
 等,应不急于马上用递归,回溯等搜索算法,特别是测试数据的范围很大的时候。不妨先用笔算,从中发现一些规律.但是也不是每一道题都可以用数学方法完成,数学
 方法只能用于一些求总数,最值之类的题目上。

 下面便是经典应用之一：

 实例四：砝码设计 

 设有一个天平,可以用来称重.
 任务一:
          设计n个砝码的重量,用他们能称出尽可能多的整数重量.例如,n=2,设计2个砝码的重量分别为1和3, 可称重为1,2,3,4的连续重量.
 任务二:
          在给出n个砝码能称出最大重量范围的一重量x,试给出称出x的方案.
 在上例中:
 给出x=2称出的方案为2+1:3
 x=4称出的方案为4:1+3
 x=1称出的方案为1:1
 输入:n,x(n为砝码个数,x是在称出最大重量范围内的重量)
 输出:砝码方案,称出x的方案.
 输入样例1:2,2 输入样例2:2,4
 输出样例1:1,3 输出样例2:1,3
 由题意可知此题不适合搜索。由任务一可知:n=2时砝码重量最优解为1、3。 我们可以试n=3,n=4...的情况，不难发现本题是一个“平衡三进制”的应用，砝码的重
 量均为3的1至n次方,由于理论推导涉及到累加等数学知识,我们着重看任务二。
 任务二要求输出用砝码称出重为x的重量,实际上就是用3的0至n-1次方的和差来表示x,如样例中的2=3-1,4=1+3等,不难发现,当x除以3余1时,必然x要表示为
 x=a1+a2...+1,余2时x=a1+a2...-1,余0时不用1的砝码.因此取x除以3的余数,可以确定砝码1用不用和用在天平的哪一边.同理,判断3的砝码位置时,可先将x先除以3
 四舍五入,再除以3取余判断.能用3的1至n次方的和差来表示x后,屏幕输出再用一个数组来处理就行了。
 参考算法：
 procedure   balance (x:integer);
 var
    j,b:integer;
 begin
 t1:=0; t2:=0; j:=1;
 
 repeat
 b:=x mod 3;
 x:=round(x/3);
 if b=2 then begin t1:=t1+1; ch1[t1]:=j; end;    {物品一端}
 if b=1 then begin t2:=t2+1; ch2[t2]:=j; end;    {砝码一端}
 j:=j*3;
 until x=0;
 end;

     数学方法的合理运用,可以给编程带来很大方便。

 【数学在计算机图形中的应用】

 1) 代数和三角学

 对于计算机图形学的初学者来说，高中的代数和三角学可能是最重要的数学。日复一日，我从简单的方程解出一个或更多的根。我时常还要解决类似求一些几何图形边长的简单三角学问题。代数和三角学是计算机图形学的最基础的知识。
 如果精通代数和三角学，就可以开始读一本计算机图形学的入门书了。下一个重要的用于计算机图形学的数学——线性代数，多数此类书籍至少包含了一个对线性代数的简要介绍。

 2) 线性代数

 线性代数的思想贯穿于计算机图形学。事实上，只要牵涉到几何数值表示法,就常常抽象出例如x,y,z坐标之类的数值，我们称之为矢量。图形学 自始至终离不开矢量和矩阵。用矢量和矩阵来描述旋转，平移，或者缩放是再好不过了。高中和大学都有线性代数的课程。只要想在计算机图形学领域工作，就应该 打下坚实的线性代数基础。我刚才提到，许多图形学的书都有关于线性代数的简要介绍——足够教给你图形学的第一门课。

 3) 微积分学

 微积分学是高级计算机图形学的重要成分。如果打算研究图形学，我强烈建议你应该对微积分学有初步认识。理由不仅仅是微积分学是一种很有用的工 具，还有许多研究员用微积分学的术语来描述他们的问题和解决办法。另外，在许多重要的数学领域，微积分学被作为进一步学习的前提。学习了基本代数之后，微 积分学又是一种能为你打开多数计算机图形学与后继的数学学习之门的课程。
 微积分学是我介绍的最后一个中学课程，以下提及的科目几乎全部是大学的课程。

 4) 微分几何学

 微分几何学研究支配光滑曲线，曲面的方程组。如果你要计算出经过某个远离曲面的点并垂直于曲面的矢量（法向矢量）就会用到微分几何学。让一辆 汽车以特定速度在曲线上行驶也牵涉到微分几何学。有一种通用的绘制光滑曲面的图形学技术，叫做“凹凸帖图”，这个技术用到了微分几何学。如果要着手于用曲 线和曲面来创造形体（在图形学里称之为建模）你至少应该学习微分几何学的基础。
 
 5) 矩阵方程组

 计算机图形学的许多问题要用到矩阵方程组的数值解法。一些涉及矩阵的问题包括：找出最好的位置与方向以使对象们互相匹配（一个最小二乘法的例 子），创建一个覆盖所给点集的曲面，并使皱折程度最小（薄板样条算法），还有材质模拟，例如水和衣服等。在图形学里矩阵表述相当流行，因此在用于图形学的 数学中我对矩阵方程组的评价是很高的。
 
 6) 概率论与统计学

 计算机图形学的许多领域都要用到概率论与统计学。当研究员涉及人类学科时，他们当然需要统计学来分析数据。图形学相关领域涉及人类学科，例如 虚拟现实和人机交互(HCI)。另外，许多用计算机描绘真实世界的问题牵涉到各种未知事件的概率。两个例子：一棵成长期的树,它的树枝分杈的概率；虚拟的 动物如何决定它的行走路线。最后，一些解高难度方程组的技巧用了随机数来估计他们的解。一个重要的例子：一种称作蒙特卡罗方法的技术经常用于光如何传播的 问题。以上仅是部分一些在计算机图形学里使用概率论和统计学的方法。

 【结束语】

 数学方法的合理运用,可以非计算机学习带来很多方便.越来越多的计算机程序需要应用数学推导、归纳。想要学习好计算机，就必须学习好数学这门基础课程。说数学是自然科学的“王后”，一点不为过。