信息学之数学基础.doc

《信息学之数学基础.doc》由会员分享，可在线阅读，更多相关《信息学之数学基础.doc（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、|第一章 有关数论的算法1.1 最大公约数与最小公倍数1.2 有关素数的算法1.3 方程 ax+by=c 的整数解及应用1.4 求 ab mod n1.1 最大公约数与最小公倍数 1.算法 1: 欧几里德算法求 a，b 的最大公约数 function gcd(a,b:longint):longint;beginif b=0 then gcdd:=aelse gcd:=gcd(b,a mod b);end;2.算法 2:最小公倍数 acm=a*b div gcd(a,b);3.算法 3:扩展的欧几里德算法，求出 gcd(a,b)和满足 gcd(a,b)=ax+by 的整数 x 和 y funct

2、ion exgcd(a,b:longint;var x,y:longint):longint;vart:longint;beginif b=0 then beginresult:=a;x:=1;y:=0;endelsebeginresult:=exgcd(b,a mod b,x,y);t:=x;x:=y;y:=t-(a div b)*y;end;end;（理论依据：gcd(a,b)=ax+by=bx1+(a mod b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1)1. 2 有关素数的算法1.算法 4:求前 n 个素数:program Basic

3、Math_Prime;constmaxn=1000;varpnum,n:longint; p:array1.maxn of longint;|function IsPrime(x:longint):boolean;var i:integer;beginfor i:=1 to pnum doif sqr(pi)0 thenbeginwrite(ai:5); k:=k+1;if k mod 10 =0 then writeln;endend.3.算法 6:将整数分解质因数的积program BasicMath_PolynomialFactors;constmaxp=1000;varpnum,n:l

4、ongint;num,p:array1.maxp of longint;procedure main;var x:longint;|beginfillchar(num,sizeof(num),0);fillchar(p,sizeof(p),0);pnum:=0;x:=1;while(n1) dobegininc(x);if n mod x=0 thenbegininc(pnum);ppnum:=x;while(n mod x=0) dobeginn:=n div x;inc(numpnum);end;end;end;end;procedure out;var j,i:integer;begin

5、for i:=1 to pnum dofor j:=1 to numi dowrite(pi:5);writeln;end;beginmain;out;end.1.3 方程 ax+by=c 的整数解及应用 1.算法 7：求方程 ax+by=c 的整数解 procedure equation(a,b,c:longint;var x0,y0:longint);var d,x,y:longint;begind:=exgcd(a,b,x,y);if c mod d0 thenbeginwriteln(no answer);halt;end elsebegin|x0:=x*(c div d);y0:=y

6、*(c div d);end;end; 2.方程 ax+by=c 整数解的应用 例 1：有三个分别装有 a 升水、b 升水和 c 升水的量筒(gcd(a，b)1，cba0),现 c 筒装满水，问能否在 c 筒个量出 d 升水(cd0)。若能，请列出一种方案。算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变动；2不是一个筒被倒满就是另一个筒被倒光；3c 筒仅起中转作用，而本身容积除了必须足够装下 a 简和 b 简的全部水外，别无其它限制。 程序如下: program mw;typenode=array0.1 of longint;vara,b,c:n

7、ode;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

8、 mod d0 thenbeginwriteln(no answer);halt;end elsebegin|x0:=x*(c div d);y0:=y*(c div d);end;end;procedure fill(var a,b:node);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);writeln(step:5,:,a1:5,b1:5,c1:5);until c1=delserepeatif b1=0 the

9、n 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.1.4 求 ab mod n 1.算法 8:直接叠代法求 ab mod n function f(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; f:=d; end; 2.算法 9:加速叠代法 function f(a,b,n

10、: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; f:=d end; 练习： 1.熟记并默写以上算法.第三章 排列与组合3.1 加法原理与乘法原理3.2 排列与组合概念与计算公式3.3 排列与组合的产生算法3.1 加法原理与乘法原理 1.加法原理： 做一件事情，完成它可以有 n 类办法，在第一类办法中有 m1

11、种不同的方法，在第二类办法中有 m2种不同的方法，在第 n 类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+.+mn 种不同的方法。 2.乘法原理： |做一件事情，完成它需要分成 n 个步骤，做第一步有 m1 种不同的方法，做第二步有 m2种不同的方法，做第 n 步有 种 mn不同的方法，那么完成这件事有 N=m 1*m2*.*mn 种不同的方法。 3.两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。 练习： 1.由数字 1，2，3，4，5 可以组成多少个三位数（各位上的数字允许重复）？ 2.由数字 0、1，2，3，4，5 可

12、以组成多少个三位数（各位上的数字允许重复）？ 3.由数字 0，1，2，3，4，5 可以组成多少个十位数字大于个位数字的两位数？ 例 4. 一个三位密码锁,各位上数字由 0,1,2,3,4,5,6,7,8,9 十个数字组成,可以设置多少种三位数的密码(各位上的数字允许重复)？首位数字不为 0 的密码数是多少种？首位数字是 0 的密码数又是多少种？ 5.如图，要给地图 A、B、C、 D 四个区域分别涂上 3 种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，不同的涂色方案有多少种？ 6.某班有 22 名女生，23 名男生. 选一位学生代表班级去领奖，有几种不同选法？ 选出男

13、学生与女学生各一名去参加智力竞赛，有几种不同的选法？ 7.105 有多少个约数？并将这些约数写出来. 8.从 5 幅不同的国画、2 幅不同的油画、7 幅不同的水彩画中选不同画种的两幅画布置房间，有几种选法？ 9.若 x、y 可以取 1，2，3，4，5 中的任一个，则点(x,y)的不同个数有多少？ 10.一个口袋内装有 5 个小球另一个口袋内装有 4 个小球，所有这些小球的颜色各不相同 从两个口袋内任取一个小球，有 种不同的取法； 11.从两个口袋内各取一个小球，有 种不同的取法. 12.乘积（a 1+a2+a3）(b 1+b2+b3+b4)(c1+c2+c3+c4+c5)展开共有 个项。 13

14、.有四位考生安排在 5 个考场参加考试.有 种不同的安排方法。 (答案:125；180；15；1000，900，100；6；45，506；8；59；25；9；20；60；625） 3. 2 排列与组合的概念与计算公式 1排列及计算公式 从 n 个不同元素中，任取 m(mn)个元素按照一定的顺序排成一列，叫做从 n 个不同元素中取出 m 个元素的一个排列；从 n 个不同元素中取出 m(mn)个元素的所有排列的个数，叫做从 n个不同元素中取出 m 个元素的排列数，用符号 p(n,m)表示. p(n,m)=n(n-1)(n-2)(n-m+1)=n!/(n-m)!(规定 0!=1). 2组合及计算公式

15、 从 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); 其他排列与组合公式 从 n 个元素中取出 r 个元素的循环排列数p(n,r)/r=n!/r(n-r)!. n 个元素被分成 k 类，每类的个数分别是 n1,n2,.nk这 n 个元素的全排列数为 n!/(n1!*n2!*.*nk!). |k 类元素,每类的

16、个数无限,从中取出 m 个元素的组合数为 c(m+k-1,m). 练习： 1（1）用 0，1，2，3，4 组合多少无重复数字的四位数？（96） （2）这四位数中能被 4 整除的数有多少个？（30） （3）这四位数中能被 3 整除的数有多少个？（36） 2用 0，1，2，3，4 五个数字组成无重复数字的五位数从小到大依次排列. （1） 第 49 个数是多少？（30124） （2） 23140 是第几个数？（40） 求下列不同的排法种数：（1） 6 男女排成一排，2 女相邻；(p(7,7)*p(2,2)（2） 6 男女排成一排，2 女不能相邻；(p(6,6)*p(7,2)（3） 5 男 3 女排成

17、一排，3 女都不能相邻;(p(5.5)*p(6,3)（4） 4 男 4 女排成一排，同性者相邻；(p(4,4)*p(4,4)*p(2,2)（5） 4 男 4 女排成一排，同性者不能相邻。(p(4,4)*p(4,4)*p(2,2)有四位医生、六位护士、五所学校。(1) 若要选派三位医生到五所学校之中的三所学校举办健康教育讲座，每所学校去一位医生有多少种不同的选派方法？(c(5,3)*p(4,3)(2) 在医生或护士中任选五人，派到五所学校进行健康情况调查，每校去且仅去一人，有多少种不同的选派方法？(p(10,5)(3) 组成三个体检小组，每组一名医生、两名护士，到五所学校中的三所学校为老师体检，

18、有多少种不同的选派方法？(c(5,3)*p(4,3)*c(6,2)*c(4,2)*c(2,2)平面上有三条平行直线，每条直线上分别有 7，5 ，6 个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？(2250) 平面上有三条平行直线，每条直线上分别有 7，5 ，6 个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同三角形？(751) 将 N 个红球和 M 个黄球排成一行。例如:N=2,M=2 可得到以下 6 种排法:红红黄黄 红黄红黄 红黄黄红 黄红红黄 黄红黄红 黄黄红红问题:当 N=4,M=3 时有多少种不同排法?(不用列出每

19、种排法)(35)8.用 20 个不同颜色的念珠穿成一条项链,能做多少个不同的项链.(20!/20)9在单词 MISSISSIPPI 中字母的排列数是(11!/(1!*4!*4!*2!)10求取自 1,2,.k 的长为 r 的非减序列的个数为(c(r+k-1,r)3.排列与组合的产生算法1排列的产生方法：（递归，深度优先产生）程序如下：program pailei;const m=4;var a:array1.m of integer ;b:array1.m of boolean;procedure print;var i:integer;beginfor i:=1 to m do|write(

20、ai);writeln;end;procedure try(dep:integer);var i:integer;beginfor i:=1 to m doif bi thenbeginadep:=i; bi:=false;if dep=m then print else try(dep+1);bi:=true;end;end;beginfillchar(b,sizeof(b),true);try(1);end.方法根据上一个排列产生下一个排列程序如下：program pailei;const m=5;var a:array1.m of integer ;i,j,temp,k,l:integer;procedure print;var i:integer;beginfor i:=1 to m dowrite(ai);writeln;end;beginfor i:=1 to m do ai:=i;repeatprint;i:=m-1;while (i0) and (aiai+1) do i:=i-1;if i0 thenbeginj:=m;while ajai do j:=j-1;temp:=ai;ai:=aj;aj:=temp;k:=i+1;l:=m;while kl do