数学在程序设计中的应用

数学是研究现实世界的空间形式和数量关系的科学,是处理客观问题的强有力的工具,几乎在一切自然科学领域中都起着基础性的作用。

数学的特点不仅在于概念的抽象性、逻辑的严密性、结论的明确性，还在于它应用的广泛性。

数学方法在程序设计中的运用包括两个方面：化简题目和直接解决问题。

应用数学方法化简题目是解决问题必不可少的重要步骤，也是分析题目的基本方法。

应用数学方法化简题目，发掘题目中的隐含条件，寻求更多的“已知”条件，从而为建立数学模型提供依据。

而用数学方法直接解题，其效率更是一般算法所不可及的。

下面以具体的问题为例，介绍有关的数学知识和数学方法，体会利用数学方法解决问题时的乐趣。

一．数论基础1．欧几里德转辗相除法利用gcd(a,b)=gcd(b,a mod b)求a，b的最大公约数：function gcd(a,b:longint):longint;beginif b=0 then gcdd:=aelse gcd:=gcd(b,a mod b);end;思考：如何把上述算法写成迭代形式？2．扩展的欧几里德算法如果gcd(a,b)=d，一定存在整数x和y满足gcd(a,b)=ax+by。

求d及满足gcd(a,b)=ax+by的整数对（x，y）的算法如下：function exgcd(a,b:longint;var x,y:longint):longint;vart:longint;beginif b=0 thenbeginexgcd:=a;x:=1;y:=0;endelsebeginexgcd:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*y;end;end;注释1思考：1）如何把上述算法写成迭代形式？2）满足gcd(a,b)=ax+by的整数对（x，y）是否是唯一的？3.求解二元一次不定方程ax+by=c整数解我们的任务是解二元一次不定方程ax+by=c ①其中a,b,c都是整数，所求的解(x,y)也是整数关于方程①的可解性，有下面的两个重要的结论：（1）设gcd(a,b)表示整数a,b的最大公约数。

方程①有解的充分必要条件是gcd(a,b)|c。

（记号“x|y”表示x能整除y，即存在整数k，使y=kx）。

（2）如果(x0,y0)是方程①的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程①的解。

下面我们讨论具体求解的方法。

为了避免计算中对负数和0的讨论，我们假定a>0，b>0，并且a>=b。

假定方程①有解，即系数满足：gcd(a,b)|c，这时，c’=c/gcd(a,b)一定是个整数。

我们先讨论下面的方程：ax+by= gcd(a,b) ②根据上述扩展的欧几里德算法，一定存在整数x0和y0满足ax+by =gcd(a,b)。

显然，如果(x0,y0)是方程②的一组解，则(c’x,c’y)也是方程①的一组解，即a(c’x0)+b(c’y)=(c’f)=c。

下面给出求二元一次不定方程ax+by=c一组整数解（x0,y0）的算法：procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);{参见扩展的欧几里德算法}if c mod d<>0 thenbeginwriteln('no answer');halt;end elsebeginx0:=x*(c div d);y0:=y*(c div d);end;end;说明：（1）如果a,b中有一个小于0，例如a<0，可以令x’=-x，解方程ax’+by=c。

求解后，再令x=-x’就可以了。

（2）利用前面讲过的性质：“如果(x0,y0)是方程①的一组解，则对任何整数t,(x0+bt,y0-at)也都是方程①的解”。

可以通过任何整数t得到方程①的其余解。

方程ax+by=c整数解的应用例1：有三个分别装有a升水、b升水和c升水的量筒(c>b>a>0),现c筒装满水，问能否在c筒中量出d升水(a+b+d>=c>d>0)。

若能，请列出一种方案。

算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变动；2．不是一个筒被倒满就是另一个筒被倒光；3．c筒仅起中转作用，而本身容积除了必须足够装下a筒和b筒的全部水外，别无其它限制。

因此，问题的实质是水总是按a筒或b筒的容积倒来倒去，最后量出d升水来。

即通过c 筒的中转作用，把倒满a筒一次记为a +1次，从 a筒中倒出a升记为a -1次；对b筒同样如此定义。

若a筒累计x次，b筒累计y次,使得ax+by=d，则量出d升水。

于是，能否在c筒中量出d升水，取决于方程ax+by=d是否存在整数解。

参考程序如下:program mw;typenode=array[0..1] of longint;vara,b,c:node;d,step,x,y:longint;function exgcd(a,b:longint;var x,y:longint):longint;var t:longint;beginif b=0 thenbeginexgcd:=a;;x:=1;y:=0;endelsebeginexgcd:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*yend;end;procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d>0 thenbeginwriteln('no answer');halt;end elsebeginx0:=x*(c div d);y0:=y*(c div d);end;end;procedure fill(var a,b:node);{a筒向b筒倒}var t:longint;beginif a[1]<b[0]-b[1] then t:=a[1]else t:=b[0]-b[1];a[1]:=a[1]-t;b[1]:=b[1]+tend;beginwrite('a,b,c,d=');readln(a[0],b[0],c[0],d);equation(a[0],b[0],d,x,y);step:=0;a[1]:=0;b[1]:=0;c[1]:=c[0];writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);if x>0 thenrepeatif a[1]=0 then fill(c,a) elseif b[1]=b[0] then fill(b,c) else fill(a,b);inc(step);writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);until c[1]=delserepeatif b[1]=0 then fill(c,b) elseif a[1]=a[0] then fill(a,c) else fill(b,a);inc(step);writeln(step:5,':',a[1]:5,b[1]:5,c[1]:5);until c[1]=d;end.4．素数的快速测试----Miller-Rabbin算法同余若a mod c=b mod c,称a和b关于模c同余，记作a≡b(mod c).伪素数对正整数n，如果a n-1≡1（mod n） ,则称n是基于a的伪素数。

如果一个数是伪素数，它几乎肯定是素数。

另一方面，如果一个数不是伪素数，它一定不是素数。

计算a b mod c(1)直接迭代法求a b mod n根据模算术的基本知识（a*b）mod c=((a mod c)*b) mod c 得到a b mod n的迭代式算法描述如下：function f1(a,b,n:longint): longint;var d,i:longint;begind:=a;for i:=2 to b do d:=d mod n*a;d:=d mod n;b 020 aMod n)* b 121 Mod n)···a f1:=d;end;（2）加速叠代法求a b mod n把b 化为二进制（b t b t-1.···b 1b 0）,这样有：b=b t 2t +b t-12t-1+···+b 121+b 020 （其中b i =0或1）于是 a b mod n=(a ) mod n =（（算法描述： function f2(a,b,n:longint):longint;var d,t:longint;begind:=1;t:=a;while b>0 dobeginif t=1 then beginf:=d;exit end ;if b mod 2 =1 then d:=d*t mod n;b:=b div 2;t:=t*t;end;f2:=dend;Miller-Rabbin 算法是基于概率论的素数测试算法，对于a n-1≡1（mod n ），随机选取s 个基a,若a n-1≡1（mod n ）都成立，则n 为素数，否则为合数。

下面给出的Miller-Rabbin 算法采用计算a n-1 mod n 的函数f 2(a,n-1,n),对于随机选取s 个基a, f 2(a,n-1,n)都等于1，则认为n 为素数。

Function Miller_Rabbin(n:longint):boolean;Var I,a:longint;Bl:Boolean;function f2(a,b,n:longint):longint;var d,t:longint;begind:=1;t:=a;while b>0 dobeginif t=1 then beginf:=d;exit end ;if b mod 2 =1 then d:=d*t mod n;b:=b div 2;b t 2t +b t-12t-1+···+b 121+b 020t:=t*t;end;f2:=dend;begini:=0;bl:=tuue;while (i<s) and bl dobeginint(i);a:=random(n-2)+2;if f2(a,n-1,n)<>1 then bl:=false;end;miller_rabbin:=blend;二组合数学基础1．加法原理与乘法原理1．1加法原理：做一件事情，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有m n种不同的方法。