数学与程序设计

数学与程序设计 章维铣

数学与程序设计

数学是研究现实世界的空间形式和数量关系的科学,是处理客观问题的强有力的工具,几乎在一切自然科学领域中都起着基础性的作用。数学的特点不仅在于概念的抽象性、逻辑的严密性、结论的明确性，还在于它应用的广泛性。

数学方法在程序设计中的运用包括两个方面：化简题目和直接解决问题。 应用数学方法化简题目是解决问题必不可少的重要步骤，也是分析题目的基本方法。应用数学方法化简题目，发掘题目中的隐含条件，寻求更多的“已知”条件，从而为建立数学模型提供依据。而用数学方法直接解题，其效率更是一般算法所不可及的。下面以具体的问题为例，介绍有关的数学知识和数学方法，体会利用数学方法解决问题时的乐趣。

一．数论基础

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

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数学与程序设计在线全文阅读。