信息学之数学基础 本文关键词：信息学，数学，基础
信息学之数学基础 本文简介：第一章有关数论的算法1.1最大公约数与最小公倍数1.2有关素数的算法1.3方程ax+by=c的整数解及应用1.4求a^bmodn1.1最大公约数与最小公倍数1.算法1:欧几里德算法求a，b的最大公约数functiongcd(a,b:longint):longint;beginifb=0thengcd
信息学之数学基础 本文内容：
第一章
有关数论的算法
1.1
最大公约数与最小公倍数
1.2
有关素数的算法
1.3
方程ax+by=c的整数解及应用
1.4
求a^b
mod
n
1.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的整数x和y
function
exgcd(a,b:longint;var
x,y:longint):longint;
var
t:longint;
begin
if
b=0
then
begin
result:=a;
x:=1;
y:=0;
end
else
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
b)y1=bx1+(a-(a
div
b)*b)y1=ay1+b(x1-(a
div
b)*y1))
1.
2有关素数的算法
1.算法4:求前n个素数:
program
BasicMath_Prime;
const
maxn=1000;
var
pnum,n:longint;
p:array[1maxn]
of
longint;
function
IsPrime(x:longint):boolean;
var
i:integer;
begin
for
i:=1
to
pnum
do
if
sqr(p[i])0
then
begin
write(a[i]:5);
k:=k+1;
if
k
mod
10
=0
then
writeln;
end
end.
3.算法6:将整数分解质因数的积
program
BasicMath_PolynomialFactors;
const
maxp=1000;
var
pnum,n:longint;
num,p:array[1maxp]
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
begin
inc(pnum);
p[pnum]:=x;
while(n
mod
x=0)
do
begin
n:=n
div
x;
inc(num[pnum]);
end;
end;
end;
end;
procedure
out;
var
j,i:integer;
begin
for
i:=1
to
pnum
do
for
j:=1
to
num[i]
do
write(p[i]:5);
writeln;
end;
begin
main;
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
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)。若能，请列出一种方案。
算法分析：
量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点：
1.总有一个筒中的水没有变动；
2．不是一个筒被倒满就是另一个筒被倒光；
3．c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其
它限制。
程序如下:
program
mw;
type
node=array[01]
of
longint;
var
a,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
begin
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
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
a[1]0
then
repeat
if
a[1]=0
then
fill(c,a)
else
if
b[1]=b[0]
then
fill(b,c)
else
fill(a,b);
inc(step);
writeln(step:5,:,a[1]:5,b[1]:5,c[1]:5);
until
c[1]=d
else
repeat
if
b[1]=0
then
fill(c,b)
else
if
a[1]=a[0]
then
fill(a,c)
else
fill(b,a);
inc(step);
writeln(step:5,:,a[1]:5,b[1]:5,c[1]:5);
until
c[1]=d;
end.
1.4
求a^b
mod
n
1.算法8:直接叠代法求a^b
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: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
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
种不同的方法。
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．排列的产生
方法１：（递归，深度优先产生）
程序如下：
program
pailei;
const
m=4;
var
a:array[1m]
of
integer
;
b:array[1m]
of
boolean;
procedure
print;
var
i:integer;
begin
for
i:=1
to
m
do
write(a[i]);
writeln;
end;
procedure
try(dep:integer);
var
i:integer;
begin
for
i:=1
to
m
do
if
b[i]
then
begin
a[dep]:=i;
b[i]:=false;
if
dep=m
then
else
try(dep+1);
b[i]:=true;
end;
end;
begin
fillchar(b,sizeof(b),true);
try(1);
end.
方法２．根据上一个排列产生下一个排列．
程序如下：
program
pailei;
const
m=5;
var
a:array[1m]
of
integer
;
i,j,temp,k,l:integer;
procedure
print;
var
i:integer;
begin
for
i:=1
to
m
do
write(a[i]);
writeln;
end;
begin
for
i:=1
to
m
do
a[i]:=i;
repeat
print;
i:=m-1;
while
(i>0)
and
(a[i]>a[i+1])
do
i:=i-1;
if
i>0
then
begin
j:=m;
while
a[j]0)
and
(a[i]=n-(m-i))
do
dec(i);
if
i>0
then
begin
a[i]:=a[i]+1;
for
j:=i+1
to
m
do
a[j]:=a[j-1]+1;
end;
until
i=0;
end.
练习：
１．已知n（10
则相对坐标原点,点p1在点p2的顺时针方向
若m0
则相对p0点,点p1在点p2的顺时针方向
若m0
则p1点向左拐
若mb
then
max:=a
else
max:=b;
end;
function
min(a,b:real):real;
begin
if
a=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)
or
(t=0)
and
(sqr(p1.x-list[0].x)+sqr(p1.y-list[0].y)1)
and
comp(list[i],list[i-1])
do
begin
swap(list[i],list[i-1]);
dec(i)
end
end;
end
else
begin
x:=list[l+random(r-l+1)];
i:=l;j:=r;
repeat
while
comp(list[i],x)
do
inc(j);
while
comp(x,list[j])
do
dec(j);
if
i=j;
sort(l,j);
sort(j+1,r);
end
end;
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,list[i].x,list[i].y);
if
(list[i].y=0
do
dec(top);
inc(top);
s[top]:=i;
end;
for
i:=1
to
top
do
write(
(,list[s[i]].x:7:2,,,list[s[i]].y:7:2,)
);
writeln
end;
begin
init;
graham;
readln
end.
练习:
1.巳知:平面上有n个点(n=2)fn=fn-1+fn-2
前n项的和Sn=f0+f1+f2+.+fn=fn+2-1
例9:以下是Fibonacci的示例:
1.楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法?
2.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?
3.有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数？
4.错位排列
首先看例题：
例10：在书架上放有编号为1,2,n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能
放在原来的位置上。
例如:n=3时:
原来位置为:123
放回去时只能为:312或231这两种
问题:求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法)
(44)
{1，2，3，,n}错位排列是{1,2,3,,n}的一个排列i1i2.in,使得i11,i22,i33,.inn
错位排列数列为
0,1,2,9,44,265,错位排列的递推公式是:dn=(n-1)(dn-2+dn-1)(n>=3)
=ndn-1+(-1)n-2
5.分平面的最大区域数
1.直线分平面的最大区域数的序列为:
2，4，7，11，,递推公式是:
fn=fn-1+n=n(n+1)/2+1
2.折线分平面的最大区域数的序列为:
2,7,16,29,.,递推公式是:fn=(n-1)(2n-1)+2n;
3.封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为:
2,4,8,14,.,递推公式是:fn=fn-1+2(n-1)=n2-n+2
6.Catalan
数列
先看下面两个例题:
例11:将一个凸多边形区域分成三角形区域的方法数?
令hn表示具有n+1条边的凸多边形区域分成三角形的方法数。同时令h1=1，则hn满足递推关系
hn=h1hn-1+h2hn-2+.+hn-1h1(n>=2)(想一想,为什么?)
该递推关系的解为hn=c(2n-2,n-1)/n
(n=1,2,3,.)
其对应的序列为1,1,2,5,14,42,132,从第二项开始分别是三边形,四边形,.的分法数
即k边形分成三角形的方法数为hk=c(2k-4,k-2)/(k-1)(k>=3)
例12:n个+1和n个-1构成2n项
a1,a2,.,a2n
其部分和满足a1+a2+.+ak>=0(k=1,2,3,,2n)对与n该数列为
Cn=c(2k,k)/(k+1)
(k>=0)
对应的序列为
1,1,2,5,14,42,132,.
序列1,1,2,5,14,42,132,叫Catalan数列。
例13：下列问题都是Catalan数列。
1.有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，
剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？
2.一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他
从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
3.在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
4.n个结点可够造多少个不同的二叉树?
5.一个栈(无穷大)的进栈序列为1,2,3,n,有多少个不同的出栈序列?