信息学之数学基础Word文档格式.docx

1、pnum,n:p:array1.maxn of longint;function IsPrime（x:boolean;var i:integer;for i:=1 to pnum doif sqr（pi）=x then begin if x mod pi=0 then IsPrime:=false; exit; end;end=true;IsPrime:procedure main;var x:pnum:while（pnumn） doinc（x）;if IsPrime（x） then inc（pnum）; ppnum:procedure out;var i,t:=1 to n dowrite（

2、pi:5）;=t+1;if t mod 10=0 then writeln;readln（n）;main;out;end.2.算法5:求不大于n的所有素数program sushu3;const maxn=10000;i,k,n:a:array1.maxn of integer;=1 to n do ai:=i;a1:i:=2;while in dok:=2*i;while k=n do ak: k:=k+i;=i+1;while （ai=0） and （in） do i:if ai0 then write（ai:=k+1; if k mod 10 =0 then writeln; end3.

3、算法6:将整数分解质因数的积program BasicMath_PolynomialFactors;maxp=1000;num,p:array1.maxp of longint;fillchar（num,sizeof（num）,0）;fillchar（p,sizeof（p）,0）;while（n1） do inc（x）; if n mod x=0 then while（n mod x=0） do n:=n div x; inc（numpnum）;var j,i:for j:=1 to numi dowriteln;1.3方程ax+by=c的整数解及应用 1.算法7：求方程ax+by=c的整数解

4、 procedure equation（a,b,c:var x0,y0:longint）;var d,x,y:d:=exgcd（a,b,x,y）;if c mod d0 then writeln（no answer）; halt;end else x0:=x*（c div d）; y0:=y*（c div d）; 2.方程ax+by=c整数解的应用 例1：有三个分别装有a升水、b升水和c升水的量筒（gcd（a，b）1，cba0）,现c筒装满水，问能否在c筒个量出d升水（cd0）。若能，请列出一种方案。算法分析：量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：1.总有一个筒中的水没有变

5、动；2不是一个筒被倒满就是另一个筒被倒光；3c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其 它限制。程序如下:program mw;typenode=array0.1 of longint;a,b,c:node;d,step,x,y:var t:if b=0 then exgcd:; else t:=t-（a div b）*yprocedure fill（var a,b:node）;if a1 repeat if a1=0 then fill（c,a） else if b1=b0 then fill（b,c） else fill（a,b）; inc（step）; wr

6、iteln（step: until c1=d if b1=0 then fill（c,b） else if a1=a0 then fill（a,c） else fill（b,a）; until c1=d;1.4 求ab mod n 1.算法8:直接叠代法求ab mod n function f（a,b,n: longint;var d,i:begin =2 to b do d:=d mod n*a;=d mod n;f:=d;2.算法9:加速叠代法 var d,t:while b0 do begin if t=1 then begin exit end ;if b mod 2 =1 then

7、d:=d*t mod n; b:=b div 2;=t*t mod n;=d 练习：1.熟记并默写以上算法.第三章 排列与组合3.1 加法原理与乘法原理3.2 排列与组合概念与计算公式3.3 排列与组合的产生算法3.1加法原理与乘法原理 1.加法原理：做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2种不同的方法，在第n类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+.+mn 种不同的方法。2.乘法原理：做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有 种mn不同的方法，那么

8、完成这件事有 N=m1*m2*.*mn 种不同的方法。3.两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。1.由数字1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？ 2.由数字0、1，2，3，4，5可以组成多少个三位数（各位上的数字允许重复）？ 3.由数字0，1，2，3，4，5可以组成多少个十位数字大于个位数字的两位数？例 4. 一个三位密码锁,各位上数字由0,1,2,3,4,5,6,7,8,9十个数字组成,可以设置多少种三位数的密码（各位上的数字允许重复）？首位数字不为0的密码数是多少种？首位数字是0的密码数又是多少种？5.如图

9、，要给地图A、B、C、D四个区域分别涂上3种不同颜色中的某一种，允许同一种颜色使用多次，但相邻区域必须涂不同的颜色，不同的涂色方案有多少种？6.某班有22名女生，23名男生. 选一位学生代表班级去领奖，有几种不同选法？ 选出男学生与女学生各一名去参加智力竞赛，有几种不同的选法？ 7.105有多少个约数？并将这些约数写出来. 8.从5幅不同的国画、2幅不同的油画、7幅不同的水彩画中选不同画种的两幅画布置房间，有几种选法？ 9.若x、y可以取1，2，3，4，5中的任一个，则点（x,y）的不同个数有多少？ 10.一个口袋内装有5个小球另一个口袋内装有4个小球，所有这些小球的颜色各不相同 从两个口袋内

10、任取一个小球，有 种不同的取法；11.从两个口袋内各取一个小球，有 种不同的取法. 12.乘积（a1+a2+a3）（b1+b2+b3+b4）（c1+c2+c3+c4+c5）展开共有 个项。13.有四位考生安排在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个不同元素

11、中取出m个元素的排列数，用符号 p（n,m）表示. p（n,m）=n（n-1）（n-2）（n-m+1）= n!/（n-m）!（规定0!=1）. 2组合及计算公式 从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类，每类的个

12、数分别是n1,n2,.nk这n个元素的全排列数为 n!/（n1!*n2!*.*nk!）. k类元素,每类的个数无限,从中取出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） 求下列不同的排法种数： 6男女排成一排，2女相邻；（p（7,7）*p（2,2） 6男女排成一排，2女不能相邻；（p

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

14、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时有多少种不同排法?（不用列出每种排法）（35）8.用20个不同颜色的念珠穿成一条项链,能做

15、多少个不同的项链.（20!/20）9在单词MISSISSIPPI 中字母的排列数是（11!/（1!*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 ;array1.m of boolean;procedure print;=1 to m do write（ai）;procedure try（dep:integer）; if bi then adep: bi: if dep=m then

16、print else try（dep+1）;fillchar（b,sizeof（b）,true）;try（1）;方法根据上一个排列产生下一个排列const m=5;i,j,temp,k,l:=1 to m do ai:repeatprint;=m-1;while （i0） and （aiai+1） do i:=i-1;if i j:=m; while ajai do j:=j-1; temp:=ai;ai:=aj;aj:=temp;l: while k0） and （ai=n-（m-i） do dec（i）; if i=ai+1; for j:=i+1 to m do aj:=aj-1+1;已

17、知n（1=n=20）个整数x1,x2,xn（1=xi=5000000），以及一个整数k（kn）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和为素数共有多少种。n个部件,每个部件必须经过先A后B两道工序。 以知部件i在A,B 机器上的时间分别为ai，bi。如何安排加工顺序，总加工时间最短？输入：5 部件12345ai8710bi69输出：341 5 4 2 3第四章 计算几何4.1 基础知识4.2 线段相交判断4.3 寻找凸包算法4.1 基础知识 1.两点间的距离公式：已知：平面上的两点的直角坐标分别为P1（x1,y1），P2（x2,y2），则P1和P2两点间的距离为 d=sqrt（x1-x2）*（x1-x2）+（y1-y2）*（y1-y2） 2.线段的中点坐标公式：平面上的两点的直角坐标分别为P1（x1,y1），P2（x2,y2），则线段P1P2的中点坐标为 x=（x1+x2）/2 y=（y1+y2）/23.直线的斜率公式： 已知：平面上的两点的直角坐标分别为P1