数学与程序设计 章维铣
数学与程序设计
数学是研究现实世界的空间形式和数量关系的科学,是处理客观问题的强有力的工具,几乎在一切自然科学领域中都起着基础性的作用。数学的特点不仅在于概念的抽象性、逻辑的严密性、结论的明确性，还在于它应用的广泛性。
数学方法在程序设计中的运用包括两个方面：化简题目和直接解决问题。 应用数学方法化简题目是解决问题必不可少的重要步骤，也是分析题目的基本方法。应用数学方法化简题目，发掘题目中的隐含条件，寻求更多的“已知”条件，从而为建立数学模型提供依据。而用数学方法直接解题，其效率更是一般算法所不可及的。下面以具体的问题为例，介绍有关的数学知识和数学方法，体会利用数学方法解决问题时的乐趣。
一．数论基础
1．欧几里德转辗相除法 利用gcd(a,b)=gcd(b,a mod b)求a，b的最大公约数： function gcd(a,b:longint):longint; begin
if b=0 then gcdd:=a
else 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; var
t:longint; begin
if b=0 then begin
exgcd:=a; x:=1; y:=0; end else begin
exgcd:=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整数解
第 1 页 共 29 页
数学与程序设计 章维铣
我们的任务是解二元一次不定方程
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’x0,c’y0)也是方程①的一组解，即 a(c’x0)+b(c’y0)=(c’f)=c。
下面给出求二元一次不定方程ax+by=c一组整数解（x0,y0）的算法：
procedure equation(a,b,c:longint;var x0,y0:longint); var d,x,y:longint; begin
d:=exgcd(a,b,x,y);{参见扩展的欧几里德算法} if c mod d<>0 then begin
writeln('no answer'); halt; end else begin
x0:=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)。若能，请列出一种方案。 算法分析：
量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：
第 2 页 共 29 页
数学与程序设计 章维铣
1.总有一个筒中的水没有变动；
2．不是一个筒被倒满就是另一个筒被倒光；
3．c筒仅起中转作用，而本身容积除了必须足够装下a筒和b筒的全部水外，别无其它限制。
因此，问题的实质是水总是按a筒或b筒的容积倒来倒去，最后量出d升水来。即通过c筒的中转作用，把倒满a筒一次记为a +1次，从 a筒中倒出a升记为a -1次；对b筒同样如此定义。若a筒累计x次，b筒累计y次,使得ax+by=c-d，则在c筒中量出d升水。于是，能否在c筒中量出d升水，取决于方程ax+by=c-d是否存在整数解。 参考程序如下:
program mw; type
node=array[0..1] of longint; var
a,b,c:node;
d,step,x,y:longint;
function exgcd(a,b:longint;var x,y:longint):longint; var t:longint; begin if b=0 then begin
exgcd:=a;;x:=1;y:=0; end else begin
exgcd:=exgcd(b,a mod b,x,y); t:=x;x:=y;y:=t-(a div b)*y end; end;
procedure equation(a,b,c:longint;var x0,y0:longint); var d,x,y:longint; begin
d:=exgcd(a,b,x,y); if c mod d>0 then begin
writeln('no answer'); halt; end else begin
x0:=x*(c div d); y0:=y*(c div d); end; end;
procedure fill(var a,b:node);{a筒向b筒倒} var t:longint;
第 3 页 共 29 页
数学与程序设计 章维铣
begin
if a[1] write('a,b,c,d='); readln(a[0],b[0],c[0],d); equation(a[0],b[0],c-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 then repeat if a[1]=0 then fill(c,a) else if 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]=d else repeat if b[1]=0 then fill(c,b) else if 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≡1（mod n） ,则称n是基于a的伪素数。如果一个数是伪素数，它几乎肯定是 素数。另一方面，如果一个数不是伪素数，它一定不是素数。 计算a mod c b n-1 (1) 直接迭代法求ab mod n 根据模算术的基本知识（a*b）mod c=((a mod c)*b) mod c 得到ab mod n的迭代式 算法描述如下： function f1(a,b,n:longint): longint; var d,i:longint; 第 4 页 共 29 页 数学与程序设计 章维铣 begin d:=a; for i:=2 to b do d:=d mod n*a; d:=d mod n; f1:=d; end; （2）加速叠代法求ab mod n 把b化为二进制（btbt-1.···b1b0）,这样有： b=bt2t+bt-12t-1+···+b121+b020 （其中bi=0或1） 于是 b2+b2+···+b2+b2 ab mod n=(a ) mod n tt t-1 t-1 11 00 =（（ a 算法描述： b020 Mod n)* a b121 Mod n)··· function f2(a,b,n:longint):longint; var d,t:longint; begin d:=1;t:=a; while b>0 do begin if t=1 then begin f:=d;exit end ; if b mod 2 =1 then d:=d*t mod n; b:=b div 2; t:=t*t; end; f2:=d end; Miller-Rabbin算法是基于概率论的素数测试算法，对于a≡1（mod n），随机选取s个基a,若an-1≡1（mod n）都成立，则n为素数，否则为合数。下面给出的Miller-Rabbin算法采用计算an-1 mod n的函数f2(a,n-1,n),对于随机选取s个基a, f2(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; begin d:=1;t:=a; while b>0 do begin 第 5 页 共 29 页 n-1