信息学之数学基础(38页).doc
-信息学之数学基础-第 37 页第一章 有关数论的算法1.1 最大公约数与最小公倍数1.2 有关素数的算法1.3 方程的整数解及应用1.4 求ab n1.算法1: 欧几里德算法求a，b的最大公约数 (); 0 ( b); 2.算法2:最小公倍数*b ();3.算法3:扩展的欧几里德算法，求出()和满足()的整数x和y ( ); 0 ; 1; 0; ( ); (a b)*y; （理论依据：()1+(a b)y11+(a b)*b)y11(x1-(a b)*y1)1. 2有关素数的算法1.算法4:求前n个素数: ;1000; 1 ; (); ; 1 (pi)< x pi=0 ; ; ; ; ; ; ;0;1;(<n) (x); (x) (); p; ; ; ; 1 n (pi:5)1; t 10=0 ; (n);2.算法5:求不大于n的所有素数 3; 10000;1 ;(n); 1 n ai;a10;2; i<n 2*i; k< ak0; ; ; 1; (ai=0) (i<n) 1;0; 1 n ai<>0 (ai:5); 1; k 10 =0 ; .3.算法6:将整数分解质因数的积 ;1000;1 ; ; ; (),0); (p),0); 0; 1; (n>1) (x); n 0 (); p; (n 0) x; (); ; ; ; ; 1 1 i (pi:5);.1.算法7：求方程的整数解 ( x00); ; (); c d>0 (' '); ; x0*(c d); y0*(c d); 例1：有三个分别装有a升水、b升水和c升水的量筒(a，b)1，c>b>a>0),现c筒装满水，问能否在c筒个量出d升水(c>d>0)。若能，请列出一种方案。算法分析： 量水过程实际上就是倒来倒去，每次倒的时候总有如下几个持点： 1.总有一个筒中的水没有变动； 2不是一个筒被倒满就是另一个筒被倒光； 3c筒仅起中转作用，而本身容积除了必须足够装下a简和b简的全部水外，别无其 它限制。 程序如下: ;0.1 ; ( ); ; 0 10; ( ); (a b)*y ; ( x00); ; (); c d>0 (' '); ; x0*(c d); y0*(c d); ( ); ; a1<b01 1 01; a11; b11; (''); (a000); (a00); 0; a101010; (:5,':'1:51:51:5); x>0 a1=0 () b10 () (); (); (:5,':'1:51:51:5); c1 b1=0 () a10 () (); (); (:5,':'1:51:51:5); c1;.1.4 求ab n 1.算法8:直接叠代法求ab n f(): ; 2 b n*a; n; 2.算法9:加速叠代法 f(); 1; b>0 1 b 2 =1 *t n; 2; *t n; 练习： 1.熟记并默写以上算法.第三章 排列与组合3.1 加法原理与乘法原理3.2 排列与组合概念与计算公式3.3 排列与组合的产生算法1.加法原理： 做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2种不同的方法，在第n类办法中有 种不同的方法。那么完成这件事共有 m12 种不同的方法。 2.乘法原理： 做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有 种不同的方法，那么完成这件事有 1*m2*.* 种不同的方法。 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中的任一个，则点()的不同个数有多少？ 10.一个口袋内装有5个小球另一个口袋内装有4个小球，所有这些小球的颜色各不相同 从两个口袋内任取一个小球，有 种不同的取法； 11.从两个口袋内各取一个小球，有 种不同的取法. 12.乘积（a123）(b1234)(c12345)展开共有 个项。 13. 种不同的安排方法。 (答案: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()表示. p()(1)(2)(1)= ()!(规定01). 2组合及计算公式 从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m c() 表示. c()()()!*m!)；c()(); 其他排列与组合公式 从n个元素中取出r个元素的循环排列数p()()!. n个元素被分成k类，每类的个数分别是n12这n个元素的全排列数为 (n1!*n2!*.*!). k类元素,每类的个数无限,从中取出m个元素的组合数为c(1). 练习： 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个黄球排成一行。例如22可得到以下6种排法:红红黄黄 红黄红黄 红黄黄红 黄红红黄 黄红黄红 黄黄红红问题:当43时有多少种不同排法?(不用列出每种排法)(35)8.用20个不同颜色的念珠穿成一条项链,能做多少个不同的项链.(2020)9在单词 中字母的排列数是(11(1!*4!*4!*2!)10求取自1,2的长为r的非减序列的个数为(c(1)1排列的产生方法：（递归，深度优先产生）程序如下： ; 4; 1 ; 1 ; ; ; 1 m (ai); (); ; 1 m bi a; bi; (1); bi; ;(b);(1);.方法根据上一个排列产生下一个排列程序如下： ; 5; 1 ; ; ; 1 m (ai); 1 m ai; 1; (i>0) (ai>a1) 1; i>0 ; aj<ai 1; iijj; 1; k<l kkll; 11 ; 0;.组合的产生算法算法：（递归，深度优先产生）程序如下： ; 64; 0 ; ; ; 1 m (ai); (); ; 1+1 () a; (1); ;a00;(1);.算法：根据前一个组合产生下一个组合程序如下： ; 64; 1 ; ; ; 1 m (ai); 1 m ai; ; ; (i>0) (ai() (i); i>0 aii+1; 1 m aj1+1; ; 0;.练习：已知n（1<<=20）个整数x12,（1<<=5000000），以及一个整数k（k<n）。从n个整数中任选k个整数相加，可分别得到一系列的和。现在，要求你计算出和为素数共有多少种。n个部件,每个部件必须经过先A后B两道工序。 以知部件i在 机器上的时间分别为，。如何安排加工顺序，总加工时间最短？ 输入： 5 部件123453587106 2149输出：341 5 4 2 3第四章 计算几何4.1 基础知识4.2 线段相交判断4.3 寻找凸包算法4.1 基础知识 1.两点间的距离公式： 已知：平面上的两点的直角坐标分别为P1(x11)，P2(x22)，则P1和P2两点间的距离为 (x12)*(x12)+(y12)*(y12) 2.线段的中点坐标公式： 已知：平面上的两点的直角坐标分别为P1(x11)，P2(x22)，则线段P1P2的中点坐标为 (x12)/2 (y12)/2 3.直线的斜率公式： 已知：平面上的两点的直角坐标分别为P1(x11)，P2(x22),则线段P1P2所在的直线的斜率为 （y21)/(x21) 4.直线的点斜式方程: 已知：直线过点P0(x00)，斜率为k,则该直线所在的方程为 (0)000(与y轴交点的纵坐标:纵截距) 练习 1.已知:矩形上三点的坐标p1(x11)2(x22)3(x33) (1)求矩形另外一点的坐标p4(x44)。 (2)判断点p()是在矩形内、矩形外还是在矩形的边上。 4. 2 线段的相交判断 已知：平面上的两点的直角坐标分别为p1(x11)，p2(x22)则 （1）该两点相对坐标原点(0,0)的叉积为1*y22*y1 若m>0 则相对坐标原点,点p1在点p2的顺时针方向 若m<0 则相对坐标原点,点p1在点p2的逆时针方向 若0 则原点和p1、p2在一条直线上（2）该两点相对点p0(x00)的叉积为(x10)*(y20)-(x20)*(y10) 若m>0 则相对p0点,点p1在点p2的顺时针方向 若m<0 则相对p0点,点p1在点p2的逆时针方向 若0 则p0和p1、p2在一条直线上 (1)计算叉积(x10)*(y20)-(x20)*(y10) （2）判断m 若m>0 则p1点向左拐 若m<0 则p1点向右拐 若0 则点p0、p1、p2在一条直线上 3.确定两条线段p1p2、p3p4是否相交 程序如下： ; x, ; p1234; m(p120); (p10)*(p20)-(p20)*(p10); (); a>b ; (); a<b ; (p1234); (p12)>(p34) (p34)>(p12) (p12)>(p34) (p3, p4)>(p12) (m(p231)*m(p241)<0) (m(p413)*m(p423)<0) ; (p1122); (p3344); (p1234) ('') ('');.一个点集Q（p0121)，它的凸包是一个最小的凸多边形P，且满足Q中的每个点或者在P的边界上，或者在P的内部。在直观上，我们可以把Q中的每个点看作露在板外的铁钉那么凸包就是包含所有铁钉的一个拉紧的橡皮绳所构成的形状如图：算法如下(算法):1)求q中y坐标最小的点p0,若具有最小坐标的点有多个,则取最左边的点作为.2)对q中剩余的点按逆时针相对p0的极角排序,若有数个保留其中距p0最远的点 得到序列(p121);3)p012相继入栈4) 3 1 1) 由次栈顶元素、栈顶元素和所形成角不是向左转栈顶元素出栈s； 2)入栈5)打印按逆时针排列的栈中的各顶点程序如下: ; 500; ; ; ;0 p;1 ; ( ); ; ; m(p120); (p10)*(p20)-(p20)*(p10); (p12); ; (p120); (t>0) (0) (p10)(p10)< (p20)(p20) ; (); ; 1<=5 1 r ; (i>1) (i1) (i1); (i) ; (1); ; (i) (j); (j) (j); i<j (ij) i> (); (1); ; ; ; (f,''); (f); (); 0 1 (ii); (i<0) (i0) (i<0) (0i); ; (11) ; ; 1 3 si1; 3; 3 1 m(iss1)>=0 (); (); s; ; 1 ('('si:7:2,','si:7:2,')'); .练习:1.巳知:平面上有n个点(n<=10000)，用算法找出彼此间最远的两个点.第五章 其它数学知识及算法5.1 鸽巢原理5.2 容斥原理5.3 常见递推关系及应用5.1 鸽巢原理 1.简单形式 如果1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。 例1：在13个人中存在两个人，他们的生日在同一月份里。 例2：设有n对已婚夫妇。为保证有一对夫妇被选出，至少要从这2n个人中选出多少人？（1） 2.加强形式 令q12为正整数。如果将 q121个物体放入n个盒子内,那么或者第一个盒子至少含有q1个物体,或者第二个盒子 至少含有q2个物体,.,或者第n个盒子含有个物体. 例3:一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9 个橘子，则放入篮子中的水果的最小件数是多少？（21件） 5. 2 容斥原理及应用 原理：集S的不具有性质P12,.，的物体的个数由下式给出： 1A2.(-1)1A2. 如3,时上式为： 1A2A3(123|)+(1A21A32A3|)1A2A3| 推论:至少具有性质P12之一的集合S的物体的个数有： | A1A2.1A2. (-1)11A2. 例4：求从1到1000不能被5，6，和8整除的整数的个数？ （1000-（200+166+125）+（33+25+41）-8=600） 5. 常见递推关系及应用1.算术序列 每一项比前一项大一个常数d； 若初始项为h0：则递推关系为 10； 对应的各项为：h0，h0，h0+2d，0; 前n项的和为(1)h0(1)/2 例5: 1,2,3,. 例6: 1,3,5,7.等都是算术序列。 2.几何序列 每一项是前面一项的常数q倍 若初始项为h0：则递推关系为 010； 对应的各项为: h0，h0q1，h0q2，0例7: 1,2,4,8,16,. 例8: 5,15,45,135,.等都是几何序列; 前n项和为(1-1)/(1) )h0 3序列 除第一、第二项外每一项是它前两项的和； 若首项为f0为0,则序列为0，1，1，2，3，5，8.递推关系为(n>=2)12 前n项的和0122-1 例9:以下是的示例: 1.楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法? 2.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子? 3.有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数？ 4.错位排列 首先看例题：例10：在书架上放有编号为1,2的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例如3时:原来位置为:123放回去时只能为:312或231这两种问题:求当5时满足以上条件的放法共有多少种?(不用列出每种放法) (44)1，2，3，错位排列是1,2,3的一个排列i1i2,使得i1<>12<>23<>3<>n 错位排列数列为 0,1,2,9,44,265,. 错位排列的递推公式是(1)(21)(n>=3) 1+(-1)2 2，4，7，11，., 递推公式是: 1(1)/2+1 2.折线分平面的最大区域数的序列为: 2, 7, 16,29, ., 递推公式是(1)(21)+2n; 3.封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为: 2, 4, 8, 14,., 递推公式是1+2(1)22 6 数列 先看下面两个例题: 例11:将一个凸多边形区域分成三角形区域的方法数? 令表示具有1条边的凸多边形区域分成三角形的方法数。同时令h1=1，则满足递推关系 11221h1(n>=2)(想一想,为什么?) 该递推关系的解为(221) (1,2,3,.) 其对应的序列为1,1,2,5,14,42,132,.从第二项开始分别是三边形,四边形,.的分法数 即k边形分成三角形的方法数为(242)/(1)(k>=3)例12个+1和n个-1构成2n项 a122n 其部分和满足a12>=0(1,2,3,.,2n)对与n该数列为 (2)/(1) (k>=0) 对应的序列为 1,1,2,5,14,42,132,. 序列1,1,2,5,14,42,132,.叫数列。 例13：下列问题都是数列。 1.有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票， 剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？ 2.一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他 从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？ 3.在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 4个结点可够造多少个不同的二叉树? 5.一个栈(无穷大)的进栈序列为1,2,3,有多少个不同的出栈序列?
