[2017年整理]数学与程序设计

《[2017年整理]数学与程序设计》由会员分享，可在线阅读，更多相关《[2017年整理]数学与程序设计（97页珍藏版）》请在金锄头文库上搜索。

1、数学与程序设计数学是研究现实现实 世界的空间间形 式和数量关系的科学,是处处理客观问观问 题题的强有力的工具,几乎在一切自然 科学领领域中都起着基础础性的作用。 数学的特点不仅仅在于概念的抽象性 、逻辑逻辑 的严严密性、结论结论 的明确性， 还还在于它应应用的广泛性。数学方法在程序设计设计 中的运用 包括两个方面：化简题简题 目和直接解 决问题问题 。应用数学方法化简题目是解决问题必不 可少的重要步骤，也是分析题目的基本方 法。应用数学方法化简题目，发掘题目中 的隐含条件，寻求更多的“已知”条件， 从而为建立数学模型提供依据。而用数学 方法直接解题，其效率更是一般算法所不 可及的。下面以具体的

2、问题为例，介绍有 关的数学知识和数学方法，体会利用数学 方法解决问题时的乐趣。数论论基础础1欧几里德转辗转辗 相除法 利用 gcd(a,b)=gcd(b,a mod b)求a，b的最大 公约约数：Function gcd(a,b:longint):longint; begin if b=0 then gcd:=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

3、 exgcd(a,b:longint;var x,y:longint):longint; var t:longint; begin if b=0 then beginexgcd:=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）如何把上述算法写成迭代形式？ 2）满足gcd(a,b)=ax+by的整数对（x，y ）是否是唯一的？3. 求解二元一次不定方程ax+by=c整数解 我们的任务是解二元一次不定方程ax+by=c 其中a,b,c都是整数，所求的解(x,

4、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的讨论，我们假 定a0，b0，并且a=b。 假定方程有解，即系数满足：gcd(a,b)|c，这 时，c=c/gcd(a,b)一定是个整数。我们先讨 论下面的方程：ax+by= gcd(a,b) 根据上述扩展的欧几里德算法，一定存在整 数x

5、0和y0满足ax+by =gcd(a,b)。显然，如果(x0,y0)是方程的一组解，则 (cx0,cy0)也是方程的一组解，即 a(cx0)+b(cy0)=(cf)=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 da0),现c筒装满水， 问能否在c筒中量出d升水(a+b+d=cd0)。若能 ，请列出一种方案。 算法分析：量水过程实际上就是倒来倒

6、去，每次倒的时候 总有如下几个持点：1.总有一个筒中的水没有变动；2不是一个筒被倒满就是另一个筒被倒光；3c筒仅起中转作用，而本身容积除了必须足 够装下a筒和b筒的全部水外，别无其它限制。 方程ax+by=c整数解的应用因此，问题的实质是水总是按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是否存在整数解。例1参考程序program mw; type

7、node=array01 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; 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;例1参考程序procedure equation(a,b,c:longint;var x0,y0:longint

8、); var d,x,y:longint; begind:=exgcd(a,b,x,y);if c mod d0 thenbeginwriteln(no answer);halt;end elsebeginx0:=x*(c div d);y0:=y*(c div d);end; end;例1参考程序procedure fill(var a,b:node);a筒向b筒倒 var t:longint; beginif a10 thenrepeatif a1=0 then fill(c,a) elseif b1=b0 then fill(b,c) else fill(a,b);inc(step);w

9、riteln(step:5,:,a1:5,b1:5,c1:5);until c1=delserepeatif b1=0 then fill(c,b) elseif a1=a0 then fill(a,c) else fill(b,a);inc(step);writeln(step:5,:,a1:5,b1:5,c1:5);until c1=d; end.4素数的快速测试-Miller-Rabbin算法 同余 若a mod c=b mod c,称a和b关于模c同余，记作 ab(mod c). 伪素数 对正整数n，如果an-11（mod n） ,则称n是基于a的伪素 数。如果一个数是伪素数，它几乎肯

10、定是 素数。另一方面，如果 一个数不是伪素数，它一定不是素数。计算ab mod c （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; 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

11、-1+b121+b020 （其中bi=0或1） 于是ab mod n= a mod n 算法描述： function f2(a,b,n:longint):longint; var d,t:longint; begin d:=1;t:=a; while b0 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 mod n; end; f2:=d end; bt2t+bt-12t- 1+b121+b020Miller-Rabbin算法是基于概率论的素 数测试算法

12、，对于an-11（mod n） ，随机选取s个基a,若an-11（mod n）都成立，则n为素数，否则为合 数。下面给出的Miller-Rabbin算法 采用计算an-1 mod n的函数f2(a,n- 1,n),对于随机选取s个基a, f2(a,n -1,n)都等于1，则认为n为素数。Miller-Rabbin算法 描述Miller-Rabbin算法 ： Function Miller_Rabbin(n:longint):boolean; Var I,a:longint;Bl:Boolean; function f2(a,b,n:longint):longint; var d,t:longi

13、nt; begin d:=1;t:=a; while b0 do begin if t=1 then begin f:=d;exit end ; Miller-Rabbin算法 描述if b mod 2 =1 then d:=d*t mod n; b:=b div 2; t:=t*t mod n; end; f2:=d end; begini:=0;bl:=tuue;while (i1 then bl:=false;end;miller_rabbin:=blend;二. 组合数学基础 1加法原理与乘法原理 11 加法原理： 做一件事情，完成它可以有n类办法，在第一类办法中 有m1 种不同的方法

14、，在第二类办法中有 m2种不同的 方法，在第n类办法中有 mn种不同的方法。那 么完成这件事共有 N= m1+m2+.+mn 种不同的方法 。 12 乘法原理： 做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法， ，做第n步有 种mn不同的方法，那么完成这件事有 N=m1*m2*.*mn 种不同的方法。13 两个原理的区别：一个与分类有关， 一个与分步有关；加法原理是“分类完成” ，乘法原理是“分步完成”。2排列与组合的概念与计算公式 21排列及计算公式 从n个不同元素中，任取m(mn)个元素按照 一定的顺序排成一列，叫做从n个不同元 素中取出m个

15、元素的一个排列；从n个不同 元素中取出m(mn)个元素的所有排列的 个数，叫做从n个不同元素中取出m个元素 的排列数，用符号 p(n,m)表示. p(n,m)=n(n-1)(n-2)(n-m+1)= n!/(n- m)!(规定0!=1). 22 组合及计算公式 从n个不同元素中，任取m(mn)个元素并成一 组，叫做从n个不同元素中取出m个元素的一个 组合；从n个不同元素中取出m(mn)个元素的 所有组合的个数，叫做从n个不同元素中取出m 个元素的组合数.用符号c (n,m)表示. c(n,m)=p(n,m)/m!=n!/(n-m)!*m!)； c(n,m)=c(n,n-m); 23 n个元素中取出r个元素的循环排列数 p(n,r)/r=n!/r(n-r)!. 24 n个元素被分成k类，每类的个数分别是 n1,n2,.nk这n个元素的全排列数为 n!/(n1!*n2!*.*nk!). 25 可重复组合如果上述组合定义中每一个元素可重复选取 ，则称为n元集中的可重复r-组合。n元集中的可 重复r-组合的总数为C(n+r-1,r)。 证明：从n元集中可重复地选取r个元素，设第一个元 素选x1个，第二个元素选x2个，第n个元素选 xn个，则议程x1+x2+xn=r的非负整数解的个数 就是n元集中的可重复r-组合的总数。