信息学之数学基础Word文档格式.docx
《信息学之数学基础Word文档格式.docx》由会员分享，可在线阅读，更多相关《信息学之数学基础Word文档格式.docx（21页珍藏版）》请在冰点文库上搜索。
pnum,n:
p:
array[1..maxn]oflongint;
functionIsPrime（x:
boolean;
vari:
integer;
fori:
=1topnumdo
ifsqr（p[i]）<
=xthen
begin
ifxmodp[i]=0then
IsPrime:
=false;
exit;
end;
end
=true;
IsPrime:
proceduremain;
varx:
pnum:
while（pnum<
n）do
inc（x）;
ifIsPrime（x）then
inc（pnum）;
p[pnum]:
procedureout;
vari,t:
=1tondo
write（p[i]:
5）;
=t+1;
iftmod10=0thenwriteln;
readln（n）;
main;
out;
end.
2.算法5:
求不大于n的所有素数
programsushu3;
constmaxn=10000;
i,k,n:
a:
array[1..maxn]ofinteger;
=1tondoa[i]:
=i;
a[1]:
i:
=2;
whilei<
ndo
k:
=2*i;
whilek<
=ndo
a[k]:
k:
=k+i;
=i+1;
while（a[i]=0）and（i<
n）doi:
ifa[i]<
>
0
then
write（a[i]:
=k+1;
ifkmod10=0thenwriteln;
end
3.算法6:
将整数分解质因数的积
programBasicMath_PolynomialFactors;
maxp=1000;
num,p:
array[1..maxp]oflongint;
fillchar（num,sizeof（num）,0）;
fillchar（p,sizeof（p）,0）;
while（n>
1）do
inc（x）;
ifnmodx=0then
while（nmodx=0）do
n:
=ndivx;
inc（num[pnum]）;
varj,i:
forj:
=1tonum[i]do
writeln;
1.3方程ax+by=c的整数解及应用
1.算法7：
求方程ax+by=c的整数解
procedureequation（a,b,c:
varx0,y0:
longint）;
vard,x,y:
d:
=exgcd（a,b,x,y）;
ifcmodd>
0then
writeln（'
noanswer'
）;
halt;
endelse
x0:
=x*（cdivd）;
y0:
=y*（cdivd）;
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;
a,b,c:
node;
d,step,x,y:
vart:
ifb=0then
exgcd:
;
else
t:
=t-（adivb）*y
procedurefill（vara,b:
node）;
ifa[1]<
b[0]-b[1]thent:
=a[1]
elset:
=b[0]-b[1];
=a[1]-t;
b[1]:
=b[1]+t
write（'
a,b,c,d='
readln（a[0],b[0],c[0],d）;
equation（a[0],b[0],d,x,y）;
step:
c[1]:
=c[0];
writeln（step:
5,'
:
'
a[1]:
5,b[1]:
5,c[1]:
ifx>
repeat
ifa[1]=0thenfill（c,a）else
ifb[1]=b[0]thenfill（b,c）elsefill（a,b）;
inc（step）;
writeln（step:
untilc[1]=d
ifb[1]=0thenfill（c,b）else
ifa[1]=a[0]thenfill（a,c）elsefill（b,a）;
untilc[1]=d;
1.4求a^bmodn
1.算法8:
直接叠代法求a^bmodn
functionf（a,b,n:
longint;
vard,i:
begin
=2tobdod:
=dmodn*a;
=dmodn;
f:
=d;
2.算法9:
加速叠代法
vard,t:
whileb>
0do
begin
ift=1thenbegin
exitend
;
ifbmod2=1thend:
=d*tmodn;
b:
=bdiv2;
=t*tmodn;
=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不同的方法，那么完成这件事有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）
３．求下列不同的排法种数：
6男２女排成一排，2女相邻；
（p（7,7）*p（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女排成一排，同性者不能相邻。
４．有四位医生、六位护士、五所学校。
若要选派三位医生到五所学校之中的三所学校举办健康教育讲座，每所学校去一位医生有多少种不同的选派方法？
（c（5,3）*p（4,3））
在医生或护士中任选五人，派到五所学校进行健康情况调查，每校去且仅去一人，有多少种不同的选派方法？
（p（10,5））
组成三个体检小组，每组一名医生、两名护士，到五所学校中的三所学校为老师体检，有多少种不同的选派方法？
（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!
*2!
）
10．求取自1,2,...k的长为r的非减序列的个数为（c（r+k-1,r））
3.３排列与组合的产生算法
1．排列的产生
方法１：
（递归，深度优先产生）
程序如下：
programpailei;
constm=4;
vara:
array[1..m]ofinteger;
array[1..m]ofboolean;
procedureprint;
=1tomdo
write（a[i]）;
proceduretry（dep:
integer）;
if
b[i]then
a[dep]:
b[i]:
ifdep=mthenprintelsetry（dep+1）;
fillchar（b,sizeof（b）,true）;
try
（1）;
方法２．根据上一个排列产生下一个排列．
constm=5;
i,j,temp,k,l:
=1tomdoa[i]:
repeat
print;
=m-1;
while（i>
0）and（a[i]>
a[i+1]）doi:
=i-1;
ifi>
j:
=m;
while
a[j]<
a[i]doj:
=j-1;
temp:
=a[i];
a[i]:
=a[j];
a[j]:
=temp;
l:
whilek<
ldo
=a[k];
a[k]:
=a[l];
a[l]:
=l-1
untili=0;
２．组合的产生算法
算法１：
programzuhe;
constn=6;
m=4;
array[0..m]ofinteger;
i,j:
=1tomdowrite（a[i]）;
=a[dep-1]+1
ton-（m-dep）do
a[0]:
算法２：
根据前一个组合产生下一个组合
array[1..m]ofinteger;
a[i]:
print;
i:
while（i>
0）and（a[i]=n-（m-i））dodec（i）;
ifi>
=a[i]+1;
forj:
=i+1tomdoa[j]:
=a[j-1]+1;
１．已知n（1<
=n<
=20）个整数x1,x2,…,xn（1<
=xi<
=5000000），以及一个整数k（k<
n）。
从n个整数中任选k个整数相加，可分别得到一系列的和。
现在，要求你计算出和为素数共有多少种。
２．n个部件,每个部件必须经过先A后B两道工序。
以知部件i在A,B机器上的时间分别为ai，bi。
如何安排加工顺序，总加工时间最短？
输入：
5
部件
1
2
3
4
5
ai
8
7
10
bi
6
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.直线的斜率公式：
已知：
平面上的两点的直角坐标分别为P1
升级会员 