信息学之数学基础

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; begin if b=0 then gcdd:=a else 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

2、的整数x和y function exgcd(a,b:longint;var x,y:longint):longint;vart:longint;beginif b=0 then  begin  result:=a;  x:=1;  y:=0; endelse begin result:=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

3、 b)y1=bx1+(a-(a div b)*b)y1=ay1+b(x1-(a div b)*y1)1. 2有关素数的算法1.算法4:求前n个素数:program BasicMath_Prime;constmaxn=1000;varpnum,n:longint; p:array1.maxn of longint;function IsPrime(x:longint):boolean;var i:integer;beginfor i:=1 to pnum do if sqr(pi)<=x then  begin   if x mod pi=

4、0 then     begin      IsPrime:=false;       exit;     end; end  else  begin   IsPrime:=true;   exit; end;IsPrime:=true;end;procedure main;var x:longint;beginpnu

5、m:=0;x:=1;while(pnum<n) dobegin inc(x); if IsPrime(x) then  begin   inc(pnum);   ppnum:=x;  end;end;end;procedure out;var i,t:integer;beginfor i:=1 to n do begin write(pi:5);t:=t+1; if t mod 10=0 then writeln; end;end;beginreadln(n);main

6、;out;end.2.算法5:求不大于n的所有素数program sushu3;const maxn=10000;vari,k,n:integer;a:array1.maxn of integer;beginreadln(n);for i:=1 to n do ai:=i;a1:=0;i:=2;while i<n dobegin k:=2*i; while k<=n do  begin  ak:=0;  k:=k+i;  end; i:=i+1; while (ai=0) and (i<n) do

7、 i:=i+1;end;k:=0;for i:=1 to n do if ai<>0  then       begin       write(ai:5); k:=k+1;       if k mod 10 =0 then writeln;       endend.3.算法6:将整数分解质因数的积program Basi

8、cMath_PolynomialFactors;constmaxp=1000;varpnum,n:longint;num,p:array1.maxp of longint;procedure main;var x:longint;begin fillchar(num,sizeof(num),0); fillchar(p,sizeof(p),0); pnum:=0; x:=1; while(n>1) do  begin  inc(x);  if n mod x=0 then   

9、begin     inc(pnum);     ppnum:=x;     while(n mod x=0) do       begin        n:=n div x;        inc(numpnum);     

10、 end;   end; end;end;procedure out;var j,i:integer;beginfor 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;begin d:=exgcd(a,b,x,y); if

11、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; 2.方程ax+by=c整数解的应用 例1：有三个分别装有a升水、b升水和c升水的量筒(gcd(a，b)1，c>b>a>0),现c筒装满水，问能否在c筒个量出d升水(c>d>0)。若能，请列出一种方案。算法分析： 量水过程实际上就是倒来倒

12、去，每次倒的时候总有如下几个持点： 1.总有一个筒中的水没有变动； 2不是一个筒被倒满就是另一个筒被倒光； 3c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其   它限制。 程序如下: program mw;typenode=array0.1 of longint;vara,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  be

13、gin   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&

14、#160; 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);var t:longint;begin if a1<b0-b1 then t:=a1               

15、;    else t:=b0-b1; a1:=a1-t; b1:=b1+tend;begin write('a,b,c,d='); readln(a0,b0,c0,d); equation(a0,b0,d,x,y); step:=0; a1:=0;b1:=0;c1:=c0; writeln(step:5,':',a1:5,b1:5,c1:5); if x>0 then  repeat   if a1=0 t

16、hen fill(c,a) else                if b1=b0 then fill(b,c) else fill(a,b);   inc(step);   writeln(step:5,':',a1:5,b1:5,c1:5);  until c1=d  else   repeat    if b1=0

17、 then fill(c,b) else              if 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

18、,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: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

19、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 种不同的方法，在第二类办法中有 m2种不同的方法，在第n类办法中有 mn种不同的方法。那么完成这件事共有 N= m1+m2+.+mn

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

21、，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名男生.      选一位学生代表班级去领奖，有几种不同选法？    &

22、#160; 选出男学生与女学生各一名去参加智力竞赛，有几种不同的选法？    7.105有多少个约数？并将这些约数写出来.    8.从5幅不同的国画、2幅不同的油画、7幅不同的水彩画中选不同画种的两幅画布置房间，有几种选法？    9.若x、y可以取1，2，3，4，5中的任一个，则点(x,y)的不同个数有多少？    10.一个口袋内装有5个小球另一个口袋内装有4个小球，所有这些小球的颜色各不相同 从两个口袋内任取一个小球，有 种不同的取法； 11.从两个口袋内各取一个小球，有 种不同的取法. 12.乘积（a1+

23、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个不同元素中取出m个元素的排列数，用符号 p(n,m)表示. p(n,m)=n(n-1)(n-2)(n-m+

24、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类，每类的个数分别是n1,n2,.nk这n个元素的全排列数为 n!/(n1!*n2!*.*nk!). k类元

25、素,每类的个数无限,从中取出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）  

26、60;    6男女排成一排，2女相邻；(p(7,7)*p(2,2)（2）       6男女排成一排，2女不能相邻；(p(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）     &#

27、160; 4男4女排成一排，同性者不能相邻。(p(4,4)*p(4,4)*p(2,2)有四位医生、六位护士、五所学校。(1)            若要选派三位医生到五所学校之中的三所学校举办健康教育讲座，每所学校去一位医生有多少种不同的选派方法？(c(5,3)*p(4,3)(2)            在医生或护士中任选五人，派到五所学校进行健康情况调查，每校去且仅去一人，有

28、多少种不同的选派方法？(p(10,5)(3)            组成三个体检小组，每组一名医生、两名护士，到五所学校中的三所学校为老师体检，有多少种不同的选派方法？(c(5,3)*p(4,3)*c(6,2)*c(4,2)*c(2,2)平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为顶点，能组成多少个不同四边形？(2250) 平面上有三条平行直线，每条直线上分别有7，5，6个点，且不同直线上三个点都不在同一条直线上。问用这些点为

29、顶点，能组成多少个不同三角形？(751) 将N个红球和M个黄球排成一行。例如:N=2,M=2可得到以下6种排法:红红黄黄 红黄红黄 红黄黄红 黄红红黄 黄红黄红 黄黄红红问题:当N=4,M=3时有多少种不同排法?(不用列出每种排法)(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

30、m=4;var a:array1.m of integer ;    b:array1.m of boolean;procedure print;var i:integer;begin for i:=1 to m do  write(ai); writeln;end;procedure try(dep:integer);var i:integer;begin for i:=1 to m do  if  bi then   begin   adep:=i; bi:=f

31、alse;   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;begin for i:=1 to m do  wr

32、ite(ai); writeln;end;beginfor i:=1 to m do ai:=i;repeat print; i:=m-1; while (i>0) and (ai>ai+1) do i:=i-1; if i>0 then begin  j:=m;  while  aj<ai do j:=j-1;  temp:=ai;ai:=aj;aj:=temp;  k:=i+1;l:=m;  while k<l do  &

33、#160; begin    temp:=ak;ak:=al;al:=temp;     k:=k+1;l:=l-1    end; end;until i=0;end.组合的产生算法算法：（递归，深度优先产生）程序如下：program zuhe;const n=6;m=4;var a:array0.m of integer; i,j:integer;procedure print;var i:integer;begin for i:=1 to m do write

34、(ai); writeln;end;procedure try(dep:integer);var i:integer;begin for i:=adep-1+1  to n-(m-dep) do  begin  adep:=i;  if dep=m then print else try(dep+1);  endend;begina0:=0;try(1);end.算法：根据前一个组合产生下一个组合程序如下：program zuhe;const n=6;m=4;var a:array1.m of integer; i

35、,j:integer;procedure print;var i:integer;begin for i:=1 to m do write(ai); writeln;end;begin for i:=1 to m do  ai:=i; repeat  print;  i:=m;  while (i>0) and (ai=n-(m-i) do dec(i);  if i>0 then   begin    ai:=ai+1;  

36、;  for j:=i+1 to m do aj:=aj-1+1;  end; until i=0;end.练习：已知n（1<=n<=20）个整数x1,x2,xn（1<=xi<=5000000），以及一个整数k（k<n）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和为素数共有多少种。n个部件,每个部件必须经过先A后B两道工序。       以知部件i在A,B 机器上的时间分别为ai，bi。如何安排加工顺序，总加工时间最短？ 输入： 5 部件1234

37、5ai358710bi6 2149输出：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

38、的中点坐标为       x=(x1+x2)/2     y=(y1+y2)/2  3.直线的斜率公式：   已知：平面上的两点的直角坐标分别为P1(x1,y1)，P2(x2,y2),则线段P1P2所在的直线的斜率为      k=（y2-y1)/(x2-x1) 4.直线的点斜式方程:   已知：直线过点P0(x0,y0)，斜率为k,则该直线所在的方程为        y=k(

39、x-x0)+y0=kx+y0-kx0=kx+b(与y轴交点的纵坐标:纵截距) 练习 1.已知:矩形上三点的坐标p1(x1,y1),p2(x2,y2),p3(x3,y3)   (1)求矩形另外一点的坐标p4(x4,y4)。   (2)判断点p(x,y)是在矩形内、矩形外还是在矩形的边上。    4. 2 线段的相交判断 1.叉积 已知：平面上的两点的直角坐标分别为p1(x1,y1)，p2(x2,y2)则 （1）该两点相对坐标原点(0,0)的叉积为m=x1*y2-x2*y1    若m>0 则相对坐标原点,点p1

40、在点p2的顺时针方向    若m<0 则相对坐标原点,点p1在点p2的逆时针方向    若m=0 则原点和p1、p2在一条直线上（2）该两点相对点p0(x0,y0)的叉积为m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0)    若m>0 则相对p0点,点p1在点p2的顺时针方向    若m<0 则相对p0点,点p1在点p2的逆时针方向    若m=0 则p0和p1、p2在一条直线上2.确定两条连续的有向线段p0

41、p1和p1p2在pl点是向左转还是向右转    (1)计算叉积m=(x1-x0)*(y2-y0)-(x2-x0)*(y1-y0) （2）判断m     若m>0 则p1点向左拐     若m<0 则p1点向右拐     若m=0 则点p0、p1、p2在一条直线上 3.确定两条线段p1p2、p3p4是否相交  程序如下：program xdxj;type p=record   

42、  x, y:realend;var p1,p2,p3,p4:p;function m(p1,p2,p0:p):real;begin m:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);end;function max(a,b:real):real;begin if a>b then max:=a else max:=b;end;function min(a,b:real):real;begin if a<b then min:=a else min:=b;end;function acros

43、s(p1,p2,p3,p4:p):boolean;begin if (max(p1.x,p2.x)>=min(p3.x,p4.x) and    (max(p3.x,p4.x)>=min(p1.x,p2.x) and    (max(p1.y,p2.y)>=min(p3.y,p4.y) and    (max(p3.y, p4.y)>=min(p1.y,p2.y) and    (m(p2,p3,p1)*m(p2,p4,p1)<0) a

44、nd (m(p4,p1,p3)*m(p4,p2,p3)<0)   then across:=true else across:=false;end;begin readln(p1.x,p1.y,p2.x,p2.y); readln(p3.x,p3.y,p4.x,p4.y); if across(p1,p2,p3,p4) then writeln('yes') else writeln('no');end.4.寻找凸包算法1.凸包的概念一个点集Q（p0,p1,p2.pn-1)，它的凸包是一个最小的凸多边形P，

45、且满足Q中的每个点或者在P的边界上，或者在P的内部。在直观上，我们可以把Q中的每个点看作露在板外的铁钉那么凸包就是包含所有铁钉的一个拉紧的橡皮绳所构成的形状如图：2.寻找凸包算法算法如下(Graham算法):1)求q中y坐标最小的点p0,若具有最小坐标的点有多个,则取最左边的点作为po.2)对q中剩余的点按逆时针相对p0的极角排序,若有数个保留其中距p0最远的点 得到序列(p1,p2,.pn-1);3)p0,p1,p2相继入栈4)for i=3 to n-1 do    1) while 由次栈顶元素、栈顶元素和Pi所形成角不是向左转do栈顶元素出栈s；

46、    2)pi入栈5)打印按逆时针排列的栈中的各顶点程序如下:program tubao;const maxn=500;type p=record     x,y:real;     end;var n,top:integer;list:array0.maxnof p;s:array1.maxn of integer;f:text;procedure swap(var a,b:p);var t:p;begin t:=a;a:=b;b:=t end;function m(p1,p2,p

47、0:p):real;begin m:=(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);end;function comp(p1,p2:p):boolean;var t:real;begin t:=m(p1,p2,list0); if (t>0) or (t=0) and (sqr(p1.x-list0.x)+sqr(p1.y-list0.y)<  sqr(p2.x-list0.x)+sqr(p2.y-list0.y)   then comp:=true else 

48、comp:=false;end;procedure sort(l,r:integer);var i,j:integer;x:p;begin if r-l+1<=5 then begin  for j:=l+1 to  r do   begin    i:=j;    while (i>1) and comp(listi,listi-1) do     begin  swap(listi,listi-1); dec(i) en

49、d   end;  end else   begin    x:=listl+random(r-l+1);    i:=l;j:=r;    repeat     while comp(listi,x) do inc(j);     while comp(x,listj) do dec(j);     if i<j then swa

50、p(listi,listj)    until i>=j;    sort(l,j);    sort(j+1,r);    endend;procedure init;var i:integer;begin assign(f,'input.txt'); reset(f); readln(f,n); for i:=0 to n-1 do  begin   readln(f,listi.

51、x,listi.y);   if (listi.y<list0.y) or    (listi.y=list0.y) and (listi.x<list0.x)    then swap(list0,listi);   end ; sort(1,n-1) end; procedure graham; var i:integer; begin  for i:=1 to 3 do si:=i-1;  top:=3;&#

52、160; for i:=3 to n-1 do   begin    while m(listi,liststop,liststop-1)>=0 do dec(top);    inc(top);    stop:=i;   end;  for i:=1 to top do   write('(',listsi.x:7:2,',',listsi.y:7:2,')');  w

53、riteln end; begin init; graham; readln end.练习:1.巳知:平面上有n个点(n<=10000)，用Graham算法找出彼此间最远的两个点.第五章 其它数学知识及算法5.1 鸽巢原理5.2 容斥原理5.3 常见递推关系及应用5.1 鸽巢原理 1.简单形式 如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。 例1：在13个人中存在两个人，他们的生日在同一月份里。 例2：设有n对已婚夫妇。为保证有一对夫妇被选出，至少要从这2n个人中选出多少人？（n+1） 2.加强形式 令

54、q1,q2,.qn为正整数。如果将  q1+q2+.+qn-n+1个物体放入n个盒子内,那么或者第一个盒子至少含有q1个物体,或者第二个盒子 至少含有q2个物体,.,或者第n个盒子含有qn个物体. 例3:一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9 个橘子，则放入篮子中的水果的最小件数是多少？（21件） 5. 2   容斥原理及应用    原理：集S的不具有性质P1,P2,.，Pm的物体的个数由下式给出： |A1A2.Am|=|S|-|Ai|+|AiAj|-|AiAjAk|+.+(-1)m

55、|A1A2.Am| 如:m=3,时上式为： |A1A2A3|=|S|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)|A1A2A3| 推论:至少具有性质P1,P2,.Pm之一的集合S的物体的个数有： | A1A2.Am|=|S|A1A2.Am|= |Ai|-|AiAj|+|AiAjAk|+.+(-1)m+1|A1A2.Am| 例4：求从1到1000不能被5，6，和8整除的整数的个数？  （1000-（200+166+125）+（33+25+41）-8=600） 5. 常见递推关系及应用1.算术序列 每一项比前一项大一个常数d； 若初始项为h0：则递推关

56、系为 hn=hn-1+d=h0+nd； 对应的各项为：h0，h0+d，h0+2d，.,h0+nd; 前n项的和为(n+1)h0+dn(n+1)/2 例5: 1,2,3,. 例6: 1,3,5,7.等都是算术序列。 2.几何序列 每一项是前面一项的常数q倍 若初始项为h0：则递推关系为 hn=h0qn-1q=h0qn； 对应的各项为: h0，h0q1，h0q2，.,h0qn例7: 1,2,4,8,16,. 例8: 5,15,45,135,.等都是几何序列; 前n项和为(qn+1-1)/(q-1) )h0 3.Fibonacci序列 除第一、第二项外每一项是它前两项的和； 若首项为f0为0,则序列为0，1，1，2，3，5，8.递推关系为(n>=2)fn=fn-1+fn-2    前n项的和Sn=f0+f1+f2+.+fn=fn+2-1 例9:以下是Fibonacci的示例:       1.楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法?       2.有一对雌雄兔,每两个月就繁殖雌雄各一对