信息的学之数学基础.docx

信息的学之数学基础.docx

《信息的学之数学基础.docx》由会员分享，可在线阅读，更多相关《信息的学之数学基础.docx（27页珍藏版）》请在冰点文库上搜索。

信息的学之数学基础

第一章有关数论的算法

1.1最大公约数与最小公倍数

1.2有关素数的算法

1.3方程ax+by=c的整数解及应用

1.4求a^bmodn

1.1最大公约数与最小公倍数

1.算法1:

欧几里德算法求a，b的最大公约数 

functiongcd（a,b:

longint）:

longint;

 begin

 ifb=0thengcdd:

=a

 elsegcd:

=gcd（b,amodb）;

 end;

2.算法2:

最小公倍数acm=a*bdivgcd（a,b）;

3.算法3:

扩展的欧几里德算法，求出gcd（a,b）和满足gcd（a,b）=ax+by的整数x和y 

functionexgcd（a,b:

longint;varx,y:

longint）:

longint;

var

t:

longint;

begin

ifb=0then 

 begin

 result:

=a;

 x:

=1;

 y:

=0;

 end

else

 begin

 result:

=exgcd（b,amodb,x,y）;

 t:

=x;

 x:

=y;

 y:

=t-（adivb）*y;

 end;

end;

（理论依据：

gcd（a,b）=ax+by=bx1+（amodb）y1=bx1+（a-（adivb）*b）y1=ay1+b（x1-（adivb）*y1））

1.2有关素数的算法

1.算法4:

求前n个素数:

programBasicMath_Prime;

const

maxn=1000;

var

pnum,n:

longint; 

p:

array[1..maxn]oflongint;

functionIsPrime（x:

longint）:

boolean;

vari:

integer;

begin

fori:

=1topnumdo

 ifsqr（p[i]）<=xthen

 begin

  ifxmodp[i]=0then

    begin

     IsPrime:

=false;

      exit;

    end;

 end 

 else

 begin

  IsPrime:

=true;

  exit;

 end;

IsPrime:

=true;

end;

proceduremain;

varx:

longint;

begin

pnum:

=0;

x:

=1;

while（pnum

begin

 inc（x）;

 ifIsPrime（x）then

 begin

  inc（pnum）;

  p[pnum]:

=x;

 end;

end;

end;

procedureout;

vari,t:

integer;

begin

fori:

=1tondo

 begin

 write（p[i]:

5）;t:

=t+1;

 iftmod10=0thenwriteln;

 end;

end;

begin

readln（n）;

main;

out;

end.

2.算法5:

求不大于n的所有素数

programsushu3;

constmaxn=10000;

var

i,k,n:

integer;

a:

array[1..maxn]ofinteger;

begin

readln（n）;

fori:

=1tondoa[i]:

=i;

a[1]:

=0;

i:

=2;

whilei

begin

 k:

=2*i;

 whilek<=ndo

 begin

 a[k]:

=0;

 k:

=k+i;

 end;

 i:

=i+1;

 while（a[i]=0）and（i

=i+1;

end;

k:

=0;

fori:

=1tondo

 ifa[i]<>0 then

      begin

      write（a[i]:

5）;k:

=k+1;

      ifkmod10=0thenwriteln;

      end

end.

3.算法6:

将整数分解质因数的积

programBasicMath_PolynomialFactors;

const

maxp=1000;

var

pnum,n:

longint;

num,p:

array[1..maxp]oflongint;

proceduremain;

varx:

longint;

begin

 fillchar（num,sizeof（num）,0）;

 fillchar（p,sizeof（p）,0）;

 pnum:

=0;

 x:

=1;

 while（n>1）do

 begin

 inc（x）;

 ifnmodx=0then

   begin

    inc（pnum）;

    p[pnum]:

=x;

    while（nmodx=0）do

      begin

       n:

=ndivx;

       inc（num[pnum]）;

     end;

  end;

 end;

end;

procedureout;

varj,i:

integer;

begin

fori:

=1topnumdo

forj:

=1tonum[i]do

write（p[i]:

5）;

writeln;

end;

begin

main;

out;

end.

1.3方程ax+by=c的整数解及应用

1.算法7：

求方程ax+by=c的整数解

procedureequation（a,b,c:

longint;varx0,y0:

longint）;

vard,x,y:

longint;

begin

 d:

=exgcd（a,b,x,y）;

 ifcmodd>0then

 begin

 writeln（'noanswer'）;

 halt;

 endelse

 begin

 x0:

=x*（cdivd）;

 y0:

=y*（cdivd）;

 end;

end;

2.方程ax+by=c整数解的应用

例1：

有三个分别装有a升水、b升水和c升水的量筒（gcd（a，b）＝1，c>b>a>0）,现c筒装满水，

问能否在c筒个量出d升水（c>d>0）。

若能，请列出一种方案。

算法分析：

 量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：

 1.总有一个筒中的水没有变动；

 2．不是一个筒被倒满就是另一个筒被倒光；

 3．c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其

  它限制。

程序如下:

programmw;

type

node=array[0..1]oflongint;

var

a,b,c:

node;

d,step,x,y:

longint;

functionexgcd（a,b:

longint;varx,y:

longint）:

longint;

vart:

longint;

begin

 ifb=0then

 begin

  exgcd:

=a;;x:

=1;y:

=0;

 end

 else

 begin

  exgcd:

=exgcd（b,amodb,x,y）;

  t:

=x;x:

=y;y:

=t-（adivb）*y

 end;

end;

procedureequation（a,b,c:

longint;varx0,y0:

longint）;

vard,x,y:

longint;

begin

 d:

=exgcd（a,b,x,y）;

 ifcmodd>0then

 begin

 writeln（'noanswer'）;

 halt;

 endelse

 begin

 x0:

=x*（cdivd）;

 y0:

=y*（cdivd）;

 end;

end;

procedurefill（vara,b:

node）;

vart:

longint;

begin

 ifa[1]

=a[1]

                  elset:

=b[0]-b[1];

 a[1]:

=a[1]-t;

 b[1]:

=b[1]+t

end;

begin

 write（'a,b,c,d='）;

 readln（a[0],b[0],c[0],d）;

 equation（a[0],b[0],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）;

 ifx>0then

 repeat

  ifa[1]=0thenfill（c,a）else

               ifb[1]=b[0]thenfill（b,c）elsefill（a,b）;

  inc（step）;

  writeln（step:

5,':

',a[1]:

5,b[1]:

5,c[1]:

5）;

 untilc[1]=d

 else

  repeat

   ifb[1]=0thenfill（c,b）else

             ifa[1]=a[0]thenfill（a,c）elsefill（b,a）;

   inc（step）;

  writeln（step:

5,':

',a[1]:

5,b[1]:

5,c[1]:

5）;

  untilc[1]=d;

end.

1.4求a^bmodn

1.算法8:

直接叠代法求a^bmodn

functionf（a,b,n:

longint）:

longint;

vard,i:

longint;

begin

 d:

=a;

 fori:

=2tobdod:

=dmodn*a;

 d:

=dmodn;

 f:

=d;

end;

2.算法9:

加速叠代法

functionf（a,b,n:

longint）:

longint;

vard,t:

longint;

begin

 d:

=1;t:

=a;

 whileb>0do

 begin

ift=1thenbegin

f:

=d;exitend  ;

ifbmod2=1thend:

=d*tmodn;

  b:

=bdiv2; 

  t:

=t*tmodn;

 end;

 f:

=d

end;

练习：

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不同的方法，那么完成这件事有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.如图，要给地图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个小球，所有这些小球的颜色各不相同①从两个口袋内任取一个小球，有种不同的取法；

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（m≤n）个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m（m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号p（n,m）表示.

p（n,m）=n（n-1）（n-2）……（n-m+1）=n!

/（n-m）!

（规定0!

=1）.

2．组合及计算公式

从n个不同元素中，任取m（m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m（m≤n）个元素的所有组合的个数，叫做从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类元素,每类的个数无限,从中取出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女排成一排，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）           　组成三个体检小组，每组一名医生、两名护士，到五所学校中的三所学校为老师体检，有多少种不同的选派方法？

（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时有多少种不同排法?

（不用列出每种排法）（35）

8.用20个不同颜色的念珠穿成一条项链,能做多少个不同的项链.（20!

/20）

9．在单词MISSISSIPPI中字母的排列数是（11!

/（1!

*4!

*4!

*2!

）

10．求取自1,2,...k的长为r的非减序列的个数为（c（r+k-1,r））

 3.３排列与组合的产生算法

1．排列的产生

方法１：

（递归，深度优先产生）

程序如下：

programpailei;

constm=4;

vara:

array[1..m]ofinteger;

   b:

array[1..m]ofboolean;

procedureprint;

vari:

integer;

begin

 fori:

=1tomdo

 write（a[i]）;

 writeln;

end;

proceduretry（dep:

integer）;

vari:

integer;

begin

 fori:

=1tomdo

 if b[i]then

  begin

  a[dep]:

=i;b[i]:

=false;

  ifdep=mthenprintelsetry（dep+1）;

  b[i]:

=true;

  end;

end;

begin

fillchar（b,sizeof（b）,true）;

try

（1）;

end.

方法２．根据上一个排列产生下一个排列．

程序如下：

programpailei;

constm=5;

vara:

array[1..m]ofinteger;

i,j,temp,k,l:

integer;

procedureprint;

vari:

integer;

begin

 fori:

=1tomdo

 write（a[i]）;

 writeln;

end;

begin

fori:

=1tomdoa[i]:

=i;

repeat

 print;

 i:

=m-1;

 while（i>0）and（a[i]>a[i+1]）doi:

=i-1;

 ifi>0then

 begin

 j:

=m;

 while a[j]

=j-1;

 temp:

=a[i];a[i]:

=a[j];a[j]:

=temp;

 k:

=i+1;l:

=m;

 whilek

   begin

   temp:

=a[k];a[k]:

=a[l];a[l]:

=temp;

    k:

=k+1;l:

=l-1

   end;

 end;

untili=0;

end.

２．组合的产生算法

算法１：

（递归，深度优先产生）

程序如下：

programzuhe;

constn=6;m=4;

vara:

array[0..m]ofinteger;

 i,j:

integer;

procedureprint;

vari:

integer;

begin

 fori:

=1tomdowrite（a[i]）;

 writeln;

end;

proceduretry（dep:

integer）;

vari:

integer;

begin

 fori:

=a[dep-1]+1 ton-（m-dep）do

 begin

 a[dep]:

=i;

 ifdep=mthenprintelsetry（dep+1）;

 end

end;

begin

a[0]:

=0;

try

（1）;

end.

算法２：

根据前一个组合产生下一个组合

程序如下：

programzuhe;

constn=6;m=4;

vara:

array[1..m]ofinteger;

 i,j:

integer;

procedureprint;

vari:

integer;

begin

 fori:

=1tomdowrite（a[i]）;

 writeln;

end;

begin

 fori:

=1tomdo

 a[i]:

=i;

 repeat

 print;

 i:

=m;

 while（i>0）and（a[i]=n-（m-i））dodec（i）;

 ifi>0then

  begin

   a[i]:

=a[i]+1;

   forj:

=i+1tomdoa[j]:

=a[j-1]+1;

 end;

 untili=0;

end.

练习：

１．已知n（1<=n<=20）个整数x1,x2,…,xn（1<=xi<=5000000），以及一个整数k（k

从n个整数中任选k个整数相加，可分别得到一系列的和。

现在，要求你计算出和为素数共有多少种。

２．n个部件,每个部件必须经过先A后B两道工序。

      以知部件i在A,B机器上的时间分别为ai，bi。

如何安排加工顺序，总加工时间最短？

输入：

5

部件

1

2

3

4

5

ai

3

5

8

7

10

bi

6 

2

1

4

9

输出：

34

15 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）/2 

3.直线的斜率公式：

 已知：

平面上的两点的直角坐标分别为P